32 1 s 128 MB

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

Calculate f(**n**) % 1000000007.

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.

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 |

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: