3423 - Fibonacci数列
时间限制 : 1 秒
内存限制 : 128 MB
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
题目输入
输入包含一个组数T,表示有T组测试数据。<span style="font-size:13.3333339691162px;line-height:1.5;"> (0<T<100)</span>
<br />
每组数据包含一个正整数N(0<N<1000)。
题目输出
对于每组数据，输出一行，包含一个整数，表示Fn除以10007的余数。
输入/输出样例
输入格式
2 10 22
输出格式
55 7704