#O1017. 斐波那契数列

斐波那契数列

题目描述

定义 f1=f2=1f_1 = f_2 = 1,fi=fi−1+fi−2 (i≥3)f_i = f_{i-1} + f_{i-2}\ (i \ge 3)。求 fn mod (109+7)f_n \bmod (10^9+7)。

题目类型

递推、取模运算

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示 fn mod (109+7)f_n \bmod (10^9+7)。

样例 #1

样例输入 #1

5

样例输出 #1

5

数据规模与约定

数据范围 说明
1≤n≤1061 \le n \le 10^6 项数
  • 边递推边取模,结果不会溢出。