Solve the programming task below in a Python markdown code block.
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