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

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

Input

一个整数n

Output

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

Examples

Input

1000000000

Output

21
Time Limit 1 second
Memory Limit 256 MB
Discuss Stats
上一题 下一题