Counting Valid Bracket Sequences

You are given an integer N representing the length of a bracket sequence. Your task is to count the number of well-formed (balanced) bracket sequences of length N.

A well-formed bracket sequence is one in which every opening bracket '(' has a corresponding closing bracket ')' and the brackets are properly nested. If N is odd, then it is impossible to have a balanced sequence, so the answer is 0.

This problem is essentially about calculating the Catalan numbers. The nth Catalan number is given by the formula:

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

However, here n is N/2 when N is even, and if N is odd, you should return 0. All results should be computed modulo \(10^9 + 7\).

inputFormat

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

Each of the following T lines contains a single integer N representing the length of the bracket sequence to be considered.

outputFormat

For each test case, output a single integer denoting the number of well-formed bracket sequences of length N (modulo \(10^9+7\)).

## sample

3
2
4
6

1
2
5

</p>