1520 - 斐波那契数列 加强版

F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)

输入

一个正整数n。

输出

F(n)的值,答案可能很大,需要对1e9+7取模。

样例

输入

5

输出

5

输入

200

输出

349361645

提示

2 < n \leq 10^{18}

来源

模板

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题