Princess Artapoelc greeted her guests by either kissing on the cheek (K) or hugging (H). From the first guest

she kisses, she has a
compulsion to necessarily kiss every alternate guest from that first kissed guest. That is if the guests are G_{1},

G_{2}, ..., G_{i}, G_{i+1}, ..., G_{n} and if she first kissed G_{i} then she must necessarily kiss

G_{i+2}, G_{i+4}, G_{i+6} ... till the last
possible guest. Your task is to determine in how many ways she can greet N guests.

Input

First line of the input contains T (T ≤ 1000) denoting the number of test cases.

T
lines follow each containing a single integer N (1 ≤ N ≤ 10^{9}) denoting the number of guests.

Output

For each case the output should be a single integer representing the number of ways Artapoelc can greet N guests. As the

answer can be large
print it modulo 1000000007.

----- Sample Input 1 ------
3
1
2
3
----- Sample Output 1 ------
2
4
6
----- explanation 1 ------

In the first case the possible ways are

K, H

Second case:

KH, HK, HH, KK

Third case:

HHH, HHK, HKH, HKK, KHK, KKK

见题面

见题面