Okay, so its again the old Fibonacci question. Print the nth Fibonacci number.

Input

First line contains 't', the number of test cases. Each test case contains a number 'n' < 10^8. 

Output

Print the nth Fibonacci number (mod 1000000007)  in one line. 

Example

Input:
3
1
2
3 

Output:
1
1
2