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)=1for n==0
f(n) denotes the nth fibonacci number where
f(0)=1
f(1)=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(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

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

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

Sample Cases :
Input:
2
3
5
Output:
4
32