← 返回题目列表

AtCoder · math_and_algorithm_ap

049. 斐波那契简单 (mod 1000000007)

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

配点 : 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 时的余数。