/ ep / 题库 /

斐波那契数列

斐波那契数列

描述

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

输入

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

输出

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

输入样例

3
5
9
100000

输出样例

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

信息

ID
1009
难度
7
分类
Fibonacci数列矩阵乘法数学 点击显示
标签
(无)
递交数
43
已通过
2
通过率
5%
上传者