407330: GYM102766 D Regular Bracket Sequence Again?

You have a collection of $$$N$$$ opening brackets '(' and $$$N$$$ closing brackets ')'.

A bracket sequence is $$$N$$$ periodic if it has a period of length $$$N$$$.

Example - ")()(" $$$N=2$$$. It is $$$N$$$ periodic but ")(()" is not.

Your task is to find out how many distinct regular bracket sequence can be formed using these $$$2N$$$ brackets such that sequence is not $$$N$$$ periodic.

As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.

Recall what the regular bracket sequence is:

• "()" is regular bracket sequence.
• if $$$s$$$ is regular bracket sequence then $$$"\texttt{(}" + s + "\texttt{)}"$$$ is regular bracket sequence.
• if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s + t$$$ is regular bracket sequence.

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

The first line contains a single integer $$$T (1 \le T \le 10^3)$$$ — the number of test cases in the input. Then $$$T$$$ test cases follow.

Each query contains one integer $$$N (1 \le N \le 10^3)$$$: the number of opening and closing brackets you have.

For each test from the input print the number of distinct regular bracket sequence we can form using $$$N$$$ opening bracket and $$$N$$$ closing bracket and sequence is not $$$N$$$ periodic modulo $$$1000000007 (10^9 + 7)$$$.

Print the answers to the tests in the order in which the tests are given in the input.

4
1
2
3
4

1
1
5
12

In the first query — The regular bracket sequence which can be formed by $$$1$$$ opening bracket and $$$1$$$ closing bracket is "()".

In the second query — The regular bracket sequence which can be formed by $$$2$$$ opening bracket and $$$2$$$ closing bracket are "(())" and "()()". We discard second one because "()()" is $$$2$$$ periodic.

In the third query — The regular bracket sequence which can be formed by $$$3$$$ opening bracket and $$$3$$$ closing bracket are "((()))" , "(())()" , "()(())" , "()()()" and "(()())". No one is $$$3$$$ periodic.