Последовательность

Известна рекуррентная формула для последовательности f:

f(n) = 1 + f(1)g(1) + f(2)g(2) + ... + f(n-1)g(n-1),

где g - тоже последовательность со следующей рекуррентной формулой:

g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + ... + 2g(n-1) - g(n-1)g(n-1).

Кроме того, известно: f(1) = 1, g(1) = 1.

Ваша задача - найти f(n) по модулю p.

Входные данные

Во входном файле содержатся несколько тестов. Каждый тест в отдельной строке содержит два числа: n (1 ≤ n ≤ 10000) и p (2 ≤ p ≤ 2·10^9). Тест с n=p=0 завершает входной файл, он не должен обрабатываться. Количество тестов в одном файле не превышает 5000.

Выходные данные

В выходной файл для каждого теста выведите в отдельной строке единственное число - f(n) по модулю p.

Примеры