Nth Fibonacci Number Modulo $10^9+7$

Given an integer N, your task is to compute the N-th Fibonacci number modulo $10^9+7$. The Fibonacci sequence is defined as follows:

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \ge 2. $$

For N equal to 0 or 1, the answer is simply N. For all other values of N, compute the result using a fast matrix exponentiation algorithm to ensure efficient performance even for large values of N.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer T, indicating the number of test cases.
2. Each of the following T lines contains a single integer N representing the position in the Fibonacci sequence.

outputFormat

For each test case, output the N-th Fibonacci number modulo $10^9+7$ on a new line to stdout.

## sample

4
0
1
2
10

0
1
1
55

</p>