The problem is simple - find (a^b) % MOD, where:

• a = Nth non-Fibonacci number.
• b = (Nth Fibonacci number) % MOD.
• MOD = 10⁹+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 Fibonacci number = 7, 3rd Fibonacci number = 2. answer = 7² % MOD = 49
• For N=2 : 2nd non Fibonacci number = 6, 2nd Fibonacci number = 1. answer = 6¹ % MOD = 6
• For N=1 : 1st non Fibonacci number = 4, 1st Fibonacci number = 1. answer = 4¹ % MOD = 4

Constraints

1 ≤ T ≤ 100000

1 ≤ N ≤ 9×10⁸

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