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 *n

Since the number can be large, output the answer modulo (10

^{th}* number.Since the number can be large, output the answer modulo (10

^{9}+7).Input Format

An integer T, denoting the number of test cases. Each test case contains and integer N.

Output Format

Print the *n

^{th}* 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