问题描述
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行,包含一个整数,表示Fn除以10007的余数。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
————————————————
from collections import deque
def Fibonacci(n):
a = deque([1,1])
if n > 2:
for i in range(n - 2):
b = a[-1] + a[-2]
a.append(b % 10007)
a.popleft()
return a[-1]
else:
return a[n-1]
n = eval(input())
print(Fibonacci(n))