Efficient Fibonacci Computation

Given an integer n, compute the nth Fibonacci number modulo \(10^9+7\). The Fibonacci sequence is defined as follows:

\(F(0)=0\), \(F(1)=1\), and \(F(n)=F(n-1)+F(n-2)\) for all \(n \ge 2\).

Your task is to implement an efficient solution using matrix exponentiation to handle large values of \(n\). The input begins with an integer \(T\), representing the number of test cases, followed by \(T\) lines each containing a single integer \(n\). For each test case, output the computed Fibonacci number modulo \(10^9+7\> in a new line.

inputFormat

The first line of input contains a single integer \(T\) (\(1\le T\le 10^5\)), representing the number of test cases. Each of the following \(T\) lines contains an integer \(n\) (\(0\le n\le 10^{18}\)).

outputFormat

For each test case, output the nth Fibonacci number modulo \(10^9+7\) on a separate line.

## sample

1
0

0

</p>