当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1555：入门训练 Fibonacci数列

题目描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入解释
输入包含一个整数n。
输出解释
输出一行，包含一个整数，表示Fn除以10007的余数。
输入样例 
10
输出样例 
55
提示
数据规模与约定
1 <= n <= 1,000,000。
该题目包含在题集 入门训练 中
题目来源 蓝桥杯
共提交 3047 次
通过率 24.06%
时间上限 内存上限
1000 MS 128 MB