331. FAST FIBONACCI
0
Medium
The Fibonacci series is a well-known sequence in which each number (Fibonacci number) is the sum of the two preceding numbers. The series starts with 1, 1, 2, 3, 5, 8.... and continues in the same pattern. Your task is to find the Nth number in the Fibonacci series. Since the numbers can be large, output the answer modulo (10^9+7).
Input Format
An integer T, representing the number of test cases. Each test case consists of an integer N.
Output Format
Print the Nth Fibonacci number modulo (10^9+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