Arya is very fond of Fibonacci numbers. He claimed he can solve any problem on Fibonacci number. His clever friend Golu gave him a challenge.

To prove his skills, he gave him a sequence which he called exponacci. The sequence is given by:

• g(0) = 1,
• g(n) = 2^{f(n - 1)} for n > 0.

f(n) denotes the nth Fibonacci number where

• f(0) = 1,
• f(1) = 1,
• f(n) = f(n - 1) + f(n - 2) for n > 1.

(Obviously Golu is not as good as Arya in Fibonacci numbers so he believes f(0) = 1, anyways we have chosen not to disturb him.)

Help Arya to find the nth exponacci number. Since the numbers can be very large take mod 10⁹ + 7.

Input

The first line of the input will be the number of test cases (T ≤ 2000). For each test case first line contains one integers n 0 ≤ n ≤ 1000000

Output

The value of g(n) % (10⁹+7)

Example

Input:
2
3
5

Output:
4
32