斐波那契数列第n项除以10007的余数

问题描述

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

斐波那契数列是一个比较简单的数列，此问题要求斐波那契数列除以10007的余数。
相信大家一看到就会觉得这题不是小学生做的吗，但是真的那么简单吗？
大部分人会这么写

n = eval(input())
a = 0
b = 1
for i in range(n):
    a,b = a+b, a
print(a%10007)

这样写没有任何问题，但如果需要求第10000000项对10007取余时，
我试了一下，三分钟都没有得出答案，电脑风扇狂转。
有没有更简洁的办法
答案是有的
我们这样想，a%10007，是否等于(a+10007*n)%10007：(n为正整数)
答案是相等的
那(a+10008)%10007和(a+1)%10007取余有区别吗，当然也是没有。

也就是说(a+b)%10007 = (a+b%10007)%10007
那么我们的程序改写成这样

n = eval(input())
a = 0
b = 1
for i in range(n+1):
    a,b = a+b, a%10007
print(b)

再试试第10000000项，三秒得出答案。
效率提升了不少。