← 返回题目列表

AtCoder · autumn_fest_04

D. 别认真思考!

中文机器翻译题面 查看原题

配点

満点
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

作者:小宫