The problem is simple.

Find (a^b) % MOD

where,

a = Nth non-fibonacci number

b = (Nth fibonacci number) % MOD

MOD = 10^9+7

Consider fibonacci series as 1,1,2,3,....

Note: It is guaranteed that Nth non-fibonacci number will always be less than MOD value for every value of N used.

Input

First line contains T, the number of test cases.

Each next T lines contains a number N.

Output

Print T lines of output where each line corresponds to the required answer.

Announcement: Constraints are updated. Sorry for inconvenience occurred.

Example

Input:
3
3
2
1

Output:
49
6
4

Explanation

For N=3 : 3rd non fibo number = 7, 3rd fibo number = 2. ans = (7^2) %MOD = 49

For N=2 : 2nd non fibo number = 6, 2nd fibo number = 1. ans = (6^1) %MOD = 6

For N=1 : 1st non fibo number = 4, 1st fibo number = 1. ans = (4^1) %MOD = 4

For N=1 : 1st non fibo number = 4, 1st fibo number = 1. ans = (4^1) %MOD = 4

Constraints

1<=T<=100000

1<=N<=9*10^8

Note: Test cases have been updated and constraints are changed. Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.