问题 1366. -- Fibonacci问题的复仇的复仇

1366: Fibonacci问题的复仇的复仇

时间限制: 1 Sec  内存限制: 128 MB
提交: 45  解决: 17
[提交][状态][讨论版]

题目描述

斐波那契数列是一个非常经典的问题,设f(0) = f(1) = 1且f(x) = f(x - 1) + f(x - 2) (x >= 2)

tsy想当给定一个x时,计算出f(x)的值,当然值可能很大,所以对其取模1e9 + 7即可

输入

第一行一个数T,代表数据组数

之后T行,每行一个数字x,代表所求项数

(1 <= T <= 1e6 , 1 <= N <= 1e18)

输出

输出T行,每行一个数字代表f(x) mod 1e9 + 7

样例输入

5
1
10
100
1000
10000

样例输出

1
89
782204094
107579939
24223428

提示

来源

[提交][状态][讨论版]