问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
没有看懂说直接算余数不用算原数是什么意思，所以用递归写了这个代码：
def fibonacci(n):
if(n==1 or n==2):
num=1
else:
num=fibonacci(n-1)+fibonacci(n-2)
return num
x=int(input())
num=fibonacci(x)
print(num%10007)
显然，运行超时。
但是直接用递归还是运行超时，所以不能用递归了，要用循环。
x=int(input())
F=[1,1,2]
if(x==1 or x==2):
print(1)
elif(x==3):
print(2)
else:
for i in range(x-3):
F.append(F[i+1]+F[i+2])
print((F[x-2]+F[x-3])%10007)
注意：①第九行那里 append的里面注意是i的加减而不是x的，要循环append的 一开始写错了用的x报了IndexError: list index out of range
问题：这下不是运行超时，是内存不够了。
在参考了一下别人的代码和题目中的红字部分，一个数减去x个10007剩下的除以10007和它直接除以10007得到的余数是一样的 。所以求下一个余数可以简化为：前两个余数相加除以10007。
x=int(input())
F=[1,1,2]
if(x==1 or x==2):
print(1)
elif(x==3):
print(3)
else:
for i in range(x-3):
F.append((F[-1]+F[-2])%10007) #每次新增的都是余数,从最后两个数里面取
print(F[x-1])
注意：第九行用的F里面最后的两个数相加，而不是用x去折腾(虽然上面一个代码用的x-2和x-3是对的)，一个小小的改善。最后打印F里的最后一个数。
