Nth Fibonacci Number Problem Statement

Given an integer 'N', the task is to compute the N'th Fibonacci number using matrix exponentiation. Implement and return the Fibonacci value for the provided 'N'.

Note:

Since the calculated Fibonacci number can be large, return the result modulo 10⁹ + 7.

Formula:

The Fibonacci number is calculated by the formula: F(n) = F(n-1) + F(n-2)
where F(1) = F(2) = 1.

Example:

Input:

N = 5

Output:

5

Explanation:

The Fibonacci sequence up to N=5 is [1, 1, 2, 3, 5]. Thus, the output is 5.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10⁹

Input:

The first line contains an integer 'T', denoting the number of test cases. For each test case, a single integer 'N' is given, representing the integer for which the corresponding Fibonacci number is to be found.

Output:

Output a single integer for each test case, representing the N'th Fibonacci number modulo 109 + 7, with each test case's output on a new line.

Note:

You are not required to print anything; implement the function as specified.

Follow Up:

Can you optimize your solution to achieve a time complexity better than O(N)?