#157. [中级组] Fibonacci 斐波那契数列

[中级组] Fibonacci 斐波那契数列

题目描述

Fibonacci 数列的递推公式为:Fn=Fn1+Fn2F_n=F_{n-1}+F_{n-2},其中 F1=F2=1F_1=F_2=1
nn 比较大时,FnF_n 也非常大,现在我们想知道,FnF_n 除以 1000710007 的余数是多少。

输入格式

输入包含一个整数 nn

输出格式

输出一行,包含一个整数,表示 FnF_n 除以 1000710007 的余数。

样例

10
55
22
7704

数据规模与约定

1n1,000,0001 \le n \le 1,000,000

题目来源

第 11 届蓝桥杯青少组 C++ 选拔赛中级组