Problems
Sequence
Sequence
You are given a recurrent formula for a sequence \textbf{f}:
\textbf{f(n) = 1 + f(1)g(1) + f(2)g(2) + ... + f(n-1)g(n-1)},
where \textbf{g} is also a recurrent sequence given by formula
\textbf{g(n) = 1 + 2g(1) + 2g(2) + 2g(3) + ... + 2g(n-1) - g(n-1)g(n-1)}.
It is known that \textbf{f(1) = 1}, \textbf{g(1) = 1}.
Your task is to find \textbf{f(n)} \textbf{mod} \textbf{p}.
\InputFile
The input consists of several cases. Each case contains two numbers on a single line. These numbers are \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000}) and \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{2·10^9}). The input is terminated by the case with \textbf{n=p=0} which should not be processed. The number of cases in the input does not exceed \textbf{5000}.
\OutputFile
Output for each case the answer to the task on a separate line.
Input example #1
1 2 2 11 0 0
Output example #1
1 2