题目描述

数列$\{A_i\}$定义如下:

• $a_1=0$
• $a_2=1$
• 当 $i>0$ 时， $A_{i+2}=A^2_{i+1}+A^2_i$

求 $A_n$ 除以整数 $M$ 的余数。

输入格式

n M

输出格式

输出$A_n$ 除以整数 $M$ 的余数。

数据范围

• $1 \le n \le 2^{31}$
• $M=1999$ 或 $M=10^9+7$
• 输入值都是整数。

对于这个问题的判断，设定了一组30分的测试点。包含在该组中的测试用例除了满足上面的条件之外，还要满足下面的条件。

• $M=1999$

输入输出样例

输入样例1:

6 1999

输出样例1:

29

输入样例2:

123456789 1999

输出样例2:

460

输入样例3:

987654321 1000000007

输出样例3:

75019086