7039: Fibonacci数列 

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述

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

输入


  输入包含一个组数T,表示有T组测试数据。 (0<T<100)


  每组数据包含一个正整数N(0<N<1000)。

输出

对于每组数据，输出一行，包含一个整数，表示Fn除以10007的余数。 

样例输入 复制 

2
10
22

样例输出 复制 

55
7704

提示

中国剩余定理  (a+b)%M = (a%M + b%M)%M

来源/分类

提交提交记录统计露一手!