斐波那契数列 加强版

题目描述

斐波那契数列定义如下：

• 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) 的值。

样例

提示

数据范围与约定

• 2 < n \le 10^{18}