ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1528. Sequence

Time limit: 3.0 second
Memory limit: 64 MB
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·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

Output for each case the answer to the task on a separate line.

Sample

inputoutput
1 2
2 11
0 0
1
2
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007