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