Fibonacci numbers are well-known in mathematics. But there is a problem. Your friend keeps asking you the n^th Fibonacci number. He understands that the number can be very big. So, he asks you to modulo it by 10⁸ + 7 before you give your answer to him.

In this case, the first 5 Fibonacci numbers are 1, 1, 2, 3, 5.

Input

First line contains an integer T (0 < T <= 10⁶) defining the number of test case.

Each of next T lines contains n (0 < n <= 5.10⁵).

Output

For every test case, print an n^th Fibonacci number in a line after it has been moduloed by 10⁸ + 7.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
3
5