Counting Binary Palindromes

You are given an integer n representing the length of a binary string. A binary palindrome is a binary string that reads the same backward as forward. Your task is to count the number of binary palindromes of length n modulo \(10^9+7\).

A key observation is that a binary palindrome is completely determined by its first \(\lceil n/2 \rceil\) digits. Therefore, the total number of such binary palindromes is \(2^{\lceil n/2 \rceil}\) modulo \(10^9+7\).

For example:

• For \(n=3\), the number of palindromes is \(2^{\lceil3/2\rceil}=2^2=4\).
• For \(n=4\), the number is \(2^{\lceil4/2\rceil}=2^2=4\).

inputFormat

The first line of input contains a single integer T representing the number of test cases.

Each of the following T lines contains one integer n, the length of the binary string.

outputFormat

For each test case, output a single integer denoting the number of binary palindromes of length n modulo \(10^9+7\>.

Each result should be printed on a new line.

## sample

2
3
4

4
4

</p>