Problem 1069 --A Math Problem

1069: A Math Problem

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 150  Solved: 24
[Submit][Status][Web Board][Creator:]

Description

已知函数f(n)的定义域和值域均为正整数域,并且还知道以下信息:

 f(1) = 1 
 3 × f(n) × f(2n + 1) = f(2n) × (1 + 3 × f(n)) 
 f(2n) < 6 × f(n) 


且后两个式子对于任意的n恒成立,现在请你求出 f(n)%p

Input

多组输入数据,不超过1000000组。

每组数据一行两个整数 n 和 p ,如上所述。

1 <= n, p <= 232 

Output

每组数据输出一行,即 f(n)%p

Sample Input

1 2

Sample Output

1

HINT

p不一定是个质数

Source

[Submit][Status]