配点

満点

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

---

Source Name

Autumn Fest

---