Even Sum Sequence Count

You are given T test cases. For each test case, you are provided a non-negative integer N.

Your task is to determine the number of sequences of length N which are composed only of the integers 1 and 2, such that the sum of the elements in the sequence is even. It can be proven that for N > 0, the number of valid sequences is given by \(2^{N-1} \mod (10^9+7)\). When N = 0, the answer is 1.

For example:

• If N = 1, there is only 1 valid sequence.
• If N = 2, there are 2 valid sequences.
• If N = 3, there are 4 valid sequences.

Print the result for each test case on a separate line.

inputFormat

The first line contains a single integer T (1 \(\leq T \leq 10^5\)), which denotes the number of test cases.

The second line contains T space-separated non-negative integers, where the i-th integer represents N for the i-th test case.

Note: When N = 0, consider the answer as 1.

outputFormat

Output T lines. For each test case, output the number of valid sequences modulo \(10^9+7\>.

## sample

3
1 2 3

1
2
4

</p>