#1620 FibonacciNumber

32  1 s   128 MB  

Description

f(0)=0, f(1)=1, f(i)=f(i-1)+f(i-2) if i>=2.

Calculate f(n) % 1000000007.

Input

The first line of the input gives the number of test cases, T (1 <= T <= 200).

For each test case integer n, which will be between 0 and 1,000,000,000, is given.

Output

For each test case, print f(n) modular 1,000,000,007 as explained in the problem statement, in one line.

Sample Input

Sample Output

4
0
1
10
50
0
1
55
586268941

HINT

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix: