Fibonacci 数列的递推公式为：Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}Fn=Fn−1+Fn−2，其中 F1=F2=1F_1=F_2=1F1=F2=1。 当 nnn 比较大时，FnF_nFn 也非常大，现在我们想知道，FnF_nFn 除以 100071000710007 的余数是多少。
输入包含一个整数 nnn。
输出一行，包含一个整数，表示 FnF_nFn 除以 100071000710007 的余数。
10
55
22
7704
1≤n≤1,000,0001 \le n \le 1,000,0001≤n≤1,000,000
第 11 届蓝桥杯青少组 C++ 选拔赛中级组
注册一个 核OJ_核桃编程 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 核OJ_核桃编程 通用账户
