You are given a recurrent formula for a sequence f:
f(n) = 1 + f(1)g(1) + f(2)g(2) +
where g is also a recurrent sequence given by formula
g(n) = 1 + 2g(1) + 2g(2) + 2g(3) +
+ 2g(n−1) − g(n−1)g(n−1).
It is known that f(1) = 1, g(1) = 1.
Your task is to find f(n) mod p.
The input consists of several cases. Each case contains two
numbers on a single line. These numbers are n (1 ≤ n ≤ 10000) and
p (2 ≤ p ≤ 2·109).
The input is terminated by the case with n = p = 0 which should not be
processed. The number of cases in the input does not exceed 5000.
Output for each case the answer to the task on a separate line.
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007