1039 - 数论：矩阵快速幂：求斐波那契数列第n项（大数据）

计算斐波那契中的第n项,其中n很大，n接近 1,000,000,000，注意要对10^9+7求模输出

输入

一个整数n

输出

输出一个整数,注意要对10^9+7求模输出

样例

输入

1000000000

输出

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