括号计数

题目描述

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

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

1.空序列是合法的。

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

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

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

输入说明

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

输出说明

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

样例

输入

2
1 
2

输出

1
2

提示

Author: oppsitre