724. FAST FIBONACCI
0
Medium
Fibonacci series is well-known series in which in which each number (Fibonacci number) is the sum of the two preceding numbers. The series looks like *1, 1, 2, 3, 5, 8....* and so on. Your task is to find *nth* number.
Since the number can be large, output the answer modulo (109+7).
Since the number can be large, output the answer modulo (109+7).
Input Format
An integer T, denoting the number of test cases. Each test case contains and integer N.
Output Format
Print the *nth* Fibonacci number modulo (109+7).
Example
Input
4
3
4
5
6
Output
2
3
5
8
Constraints
1<=T<=10^5
1<=N<=10^9
1<=N<=10^9
Loading...
View Submissions
Console