配点 : 1000 点
問題文
由以下递推公式定义的斐波那契数列 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 是一个整数
入力
输入是按以下格式从标准输入给出的。
N
出力
请以整数形式输出答案。
入力例 1
6
出力例 1
8
a=(1,1,2,3,5,8,\dots) 。
N=6 因此, 6 术语
请注意,我们正在寻找除以 8 。
由于它不满足
入力例 2
8691200
出力例 2
922041576
1000000007 时的余数。