AT_autumn_fest_04 Don't Think Seriously!

数列$\{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 ```