yyf最近在学习线性代数。他发现可以用矩阵乘法来求解递推式。例如求解斐波那契数列。

先构造一个矩阵A

1 1

1 0

再用斐波那契数列的前两项f2 ，f1 构造一个矩阵B

1

1

A*B

可得

2

1

即

f3

f2

易知

(A^n)*B

可以得到一个

f（n+2）

f（n+1）

构成的矩阵

那么问题来了。

斐波那契数列第n项的值为多少

输入第一个数字为样例组数T（T<=10000）

每组样例为一个数字n（n<=100000000）

输出斐波那契数列的第n项值(输出的数字可能会比较大，输出结果对10007取余)