D - Don't Think Seriously! 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

配点

満点
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 で割った余りを求めよ。

Hint: この問題はネタ枠なので、あまり真剣に考え込まないことをおすすめします。

入力形式

入力は以下の形式で与えられる。 


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\} の最初の6項は、0,1,1,2,5,29である。

入力例 2

123456789 1999

出力例 2

460

入力例 3

987654321 1000000007

出力例 3

75019086
Writer: komiya

出典

Autumn Fest