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(n) = 2^f(n-1) for n > 0
• g(0) = 1 for n == 0

f(n) denotes the nth Fibonacci number where

• f(0) = 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.)
• f(1) = 1
• f(n) = f(n-1) + f(n-2) for n > 1

Help Arya to find the nth exponacci number. Since the numbers can be very large take mod 10^9+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 <= 10^15)

Warning: value of n won't fit in int, use long long int instead.

Output

The value of g(n) % (10^9+7)

Sample

Input:
2
3
5
Output:
4
32