众所周知,fibonacci数列的表达式如下所示
f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2
现在请你求fibonacci数列的前 n 项之和 S_n ,即:
\sum_{i=1}^{n} f_n = S_n
因为答案可能会很大,所以你需要将答案对 10^9 + 7 取模。
输入
输入共一行,为一个整数 n
对于30%的数据, 1 \leq n \leq 20
对于60%的数据, 1 \leq n \leq 10^5
对于100%的数据, 1 \leq n \leq 2 \cdot 10^9
输出
输出共一个数,为 S_n 取模后的结果
样例
| 标准输入 复制文本 |
5 |
| 标准输出 复制文本 |
12 |
| 标准输入 复制文本 |
10000 |
| 标准输出 复制文本 |
295719787 |