描述

众所周知,斐波那契数列就是满足以下规则的数列
\(a_1=1,a_2=1,a_{n+2}=a_{n+1}+a_n\)
所以,我们现在要求该数列的第n项

输入

第一行一个整数T,表示数据组数
接下来的T行,每行一个整数n

T行,每行一个整数,表示\(a_n\)
由于答案可能很大,结果对\(10^9+7\)取模

5
34
911435502

对于30%的数据,\(T\leq100,n\leq200000\)
对于60%的数据,\(T\leq100,n\leq10^8\)
对于100%的数据,\(1\leq T\leq10^5,1\leq n\leq10^{18}\)
时间限制2秒,空间限制256M