You are given a recurrent formula for a sequence f:
f(n) = 1 + f(1)g(1) + f(2)g(2) + … + f(n−1)g(n−1),
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.
Input
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·10^{9}).
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
Output for each case the answer to the task on a separate line.
Sample
input  output 

1 2
2 11
0 0
 1
2

Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007