N-th Fibonacci Number
F(n) = F(n-1) + F(n-2), Where, F(1) = F(2) = 1.
For ‘N’ = 5, the output will be 5.
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow. The first line of each test case contains a single integer ‘N’, representing the integer for which we have to find its equivalent Fibonacci number.
For each test case, print a single integer representing the N’th Fibonacci number. Return answer modulo 10^9 + 7. Output for each test case will be printed in a separate line.
You are not required to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 10 1 <= N <= 10^5 Time Limit: 1 sec.
Can you solve it in Time Complexity better than O(N)?