Fibonacci数列

题目描述

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