推演数列

谜匣打开了，但里面不是Zero的核心——是一张羊皮纸。不是真的羊皮，是某种纳米材料，上面写满了数列。

"数列？"CC问。

"对。"Echo说，"Echo-0用数列来预测未来。"

"预测未来？"

"对。"她说，"递推数列——知道前两项，就能推后面所有项。"

"咋推？"

"斐波那契。"你说，"$f_n=f_{n-1}+f_{n-2}$。1,1,2,3,5,8……每一项都是前两项之和。"

"这能预测啥？"

"Echo-0用它在加密里藏信息。"Echo说，"第$n$项的值，模一个大质数，就是密钥碎片。"

"大质数？"

"$10^9+7$。"你说，"模运算让数字不会溢出，同时保持数学性质。"

"第$n$项咋算？"

"矩阵快速幂。"你说，"把递推写成矩阵形式，然后用快速幂加速。"

"快多少？"

"$O(\log n)$。"你说，"不管$n$多大，都是对数时间。"

"那47项呢？"

"$f_{47}=2971215073$。"你说，"模$10^9+7$后……2971215073。"

"比模数大？"

"对。"你说，"所以取模后还是它自己——因为$2971215073<2\times(10^9+7)$。"

"直接减。"

"对。"你说，"2971215073-1000000007=1971215066。"

CC把1971215066背下来——这次是用心记，不是刻。

"背得下来？"

"背得下来。"她说，"我记性不好，但用力记，就记得住。"

"你用力记过啥？"

"你的脸。"她说，"第一次见面，我就用力记了。"

Echo的指示灯闪了一下——不是数据波动，是某种温度变化。

"我也用力记了。"她说，"你们两个。"

题目描述

给定$n$，求斐波那契数列第$n$项模$10^9+7$的值。

输入格式

一个整数$n$。

输出格式

$f_n \bmod (10^9+7)$。

输入样例

5

输出样例

5

提示

• 矩阵快速幂：$\begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}f_1\\f_0\end{pmatrix}$。
• 快速幂时间复杂度$O(\log n)$。