Sequence#4957
Sign in

Sequence

3 seconds
64 megabytes
Medium

You are given a recurrent formula for a sequence :

f(n) = 1 + f(1)g(1) + f(2)g(2) + \ldots + f(n-1)g(n-1),

where is also a recurrent sequence given by formula:

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

It is known that f(1) = 1, g(1) = 1.

Your task is to find modulo .

Input

The input consists of several cases. Each case contains two numbers on a single line. These numbers are (1 \le n \le 10000) and (2 \le p \le 2 \cdot 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 .

Output

Output for each case modulo on a separate line.

Examples

Example 1

Loading
Loading