配点
- 満点
- 90
- 部分点
- 30
問題文
数列 \{A_i\} 定义如下。
- A_1=0
- A_2=1
- i > 0 时, 当您移动到 A_{i+2}=A_{i+1}^2 + A_i^2
A_n 作为整数 除以 M 求余数。
提示:这个问题是个玩笑,所以我们建议您不要太认真。 打印除以
入力形式
输入按以下格式给出。
n\ M
出力形式
A_n 输出为 M后的余数。
制約
- 1 ≤ n < 2^{31}
- M=1999 这个类型的变量里只能放入 M=10^9 + 7
- 所有输入值都是整数。
针对该问题的判断设置了一组30分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- M=1999
入力例 1
6 1999
出力例 1
29
数列 \{A_i\} 的前六项是0,1,1,2,5,29。
入力例 2
123456789 1999
出力例 2
460
入力例 3
987654321 1000000007
出力例 3
75019086
作者:小宫