問題文

以下の漸化式で定められるフィボナッチ数列の第 N 項 a_N を 1000000007 (=10^9+7) で割った余りを求めてください。

• a_1 = 1, a_2 = 1
• a_n = a_{n-1} + a_{n-2} (n \geq 3)

制約

• 3 \le N \le 10^7
• N は整数

入力例 1

6

出力例 1

8

a=(1,1,2,3,5,8,\dots) です。
N=6 なので、第 6 項 である 8 を出力してください。

入力例 2

8691200

出力例 2

922041576

1000000007 で割った余りを求めることに注意してください。