10829: 括号计数

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

给定一个合法的括号长度n,一对左右括号的长度算是1,请计算满足的这个长度的合法括号序列的个数为多少。括号只包括‘(’,‘)’两种。

定义一下合法的括号序列:

1.空序列是合法的。

2.如果S是合法的,那么(S)也是合法的。

3.如果AB都是合法,那么AB也是合法的。

举个例子 (),()(),(())都是合法的序列,长度分别为1,2,2.


Input

会有多组查询,第一行的数为查询的个数q,后面q行,每一个为要查询的括号长度。

Output

每一行输出一个答案对1000,000,007取模。(1 <=n,q<= 1000)

Sample Input Copy

2
1 
2

Sample Output Copy

1
2

HINT

Author: oppsitre