13158: Fibonacci数列
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：2
Solved：0
Description
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
Input
输入包含一个组数T,表示有T组测试数据。 (0<T<100)
每组数据包含一个正整数N(0<N<1000)。
Output
对于每组数据，输出一行，包含一个整数，表示Fn除以10007的余数。
Sample Input Copy
2
10
22
Sample Output Copy
55
7704
HINT
中国剩余定理 (a+b)%M = (a%M + b%M)%M