Odd Sum List Assignments

You are given an integer n. Your task is to determine the number of ways to assign values to a list of length n such that the sum of any two consecutive integers is odd. Each position in the list can be assigned one of two possible values (which you can think of as representing odd and even). In particular, when n = 1, there are exactly 2 ways. For n > 1, the answer is given by the formula:

$$\text{answer} = 2 \times 2^{\lfloor \frac{n-1}{2} \rfloor} \mod (10^9+7). $$

Make sure to perform the computation modulo $10^9+7$.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer T, the number of test cases. This is followed by T lines, each containing a single integer n representing the length of the list.

outputFormat

Output the answer for each test case on a new line to standard output (stdout). Each answer is the number of valid assignments modulo $10^9+7$.## sample

3
3
4
5

4
4
8

</p>