时间限制： 1.0 秒

空间限制： 256 MB

题目描述

定义 Fibonacci 数列：

$$fib(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ fib(n - 1) + fib(n - 2), & n \ge 2 \end{cases} $$

给定正整数 $n$，求 $fib(n) \pmod {10^9 + 7}$。

输入格式

从标准输入读入数据。

输入只有一行，为正整数 $n~(1 \le n \le 10 ^ 5)$。

输出格式

输出到标准输出。

输出一行一个整数，为 $fib(n)$ 的值。

10

55

1000

517691607

提示

Chap 01 绪论，Fibonacci 数，线性递归策略。

暴力递归的复杂度为 $O(2^n)$，可以考虑对递归过程做记忆化搜索，或者使用动态规划递推。