说明

斐波那契数列定义如下： F_1 = 1, \quad F_2 = 1 对于 n \ge 3： F_n = F_{n-1} + F_{n-2} 前几项：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots 这种从已知推未知的方法叫**递推**。三要素：初始值、递推公式、目标值。 给定 n，输出 F_n \bmod (10^9+7)。

输入格式

一行，一个整数 n（1 \le n \le 80）。

输出格式

一行，F_n \bmod (10^9+7)。

10

55

提示

MOD = 10**9 + 7 f = [0] * (n + 1) f[1] = 1 if n >= 2: f[2] = 1 for i in range(3, n + 1): f[i] = (f[i-1] + f[i-2]) % MOD print(f[n]) 进阶：用两个变量滚动，空间 O(1)。