Kisses & Hugs CKISSHUG

All submissions for this problem are available.<div> <p> 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₁,

G₂, …, 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. </p> <p> Input </p> <p>First line of the input contains T (T ≤ 1000) denoting the number of test cases.</p> <p> T lines follow each containing a single integer N (1 ≤ N ≤ 10^9) denoting the number of guests. </p> <p> </p> <p> Output </p> <p> 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. </p> <p> </p> <p> Example </p> <p> </p> <p> Input </p> <pre> 3 1 2 3 </pre> <p> </p> <p> Output </p> <pre> 2 4 6 </pre> <p> Explanation: </p> <p> In the first case the possible ways are </p> <p> K, H </p> <p> Second case: </p> <p> KH, HK, HH, KK </p> <p> Third case: </p> <p> HHH, HHK, HKH, HKK, KHK, KKK </p> </div>