14105 - 斐波那契数列 加强版
时间限制 : 1 秒
内存限制 : 128 MB
斐波那契数列定义如下：
- F(1) = 1
- F(2) = 1
- 对于 n \ge 3 ， F(n) = F(n-1) + F(n-2)
给定一个正整数 n ，请计算 F(n) 的值。由于结果可能非常大，你只需要输出它对 10^9 + 7 取模后的结果。
输入
输入只有一行，包含一个整数 n （ 2 < n \le 10^{18} ）。
输出
输出一个整数，表示 F(n) \bmod (10^9+7) 的值。
样例
输入
5
输出
5
输入
200
输出
349361645
提示
数据范围与约定
- 2 < n \le 10^{18}