Description

令\(f(n)\)为斐波那契数列第𝑛项，其中\(f(0) = 0\), \(f(1) = 1\) , \(f(n) = f(n − 1) + f(n − 2)\)。
所以要干啥呢？
求\(f(f(n))\)。

Format

Input

第一行一个整数\(T\)代表数据组数。
接下来\(T\)行每行一个整数\(n\)。

Output

\(T\)行每行一个整数代表答案对\(10^9 + 7\)取模的值。

Sample 1

Input

4
0
1
2
6

Output

0
1
1
21

Limitation

1s, 512MiB for each test case.

Hint

样例解释

无。

数据规模与约定

对于20%的数据，\(1 ≤ n ≤ 15\)。
对于40%的数据，\(1 ≤ n ≤ 90\)。
对于70%的数据，\(1 ≤ n ≤ 10^5\)。
对于100%的数据，\(1 ≤ T ≤ 10^3\), \(1 ≤ n ≤ 10^{100}\)。

Source

csp2019模拟题七