1708: 对称括号序列
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：17
解决：27
题目描述
小锋非常痴迷对称括号序列，现在给你n (1<=n<=1e6 ) 对括号，要求你算出按照以下方法最多能构造出多少种不同的合法对称括号序列：
<1. 空序列合法；
<2. 若序列P合法，则 ( P ) 也合法；
<3. 若序列P合法，则 ( ) P 或 P ( ) 也合法；
由于答案可能会很大，你需要将结果取余1e9+7后再输出。
输入
一行一个正整数t，代表有t组数据；
随后t行每行一个正整数n，代表你有n对括号可以使用；
测试数据保证t组数据n的和<=1e6。
输出
一行一个正整数代表由n对括号可以构造出多少种不同的合法对称括号序列。
样例输入 复制
3
1
2
3
样例输出 复制
1
2
3提示
按照题目描述的规则，由3对括号构成的合法的对称序列共有以下三组：
()()()
((()))
(()())