题目描述

有一个由所有长度为 $2n$ 的合法括号（括号序列中只含有 ( 和 )）序列组成的 Trie 树，问在该树上最多可以选取多少条边，使得任意两条边之间都没有公共端点。

因为答案可能很大，所以你只需要输出其对 $10^9+7$ 取模后的结果即可。

输入格式

本题有多组数据。

第一行一个整数 $T$ 表示共有 $T$ 组数据。

对于每组数据：

• 一行一个整数 $n$。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

5
1
2
4
6
9

输出 #1

1
3
27
270
10350

说明/提示

对于 $20\%$ 的分数满足 $n\le 1000$。

对于 $50\%$ 的分数满足 $n\le 2\times 10^5$。

对于全部的分数满足 $1\le T\le 10^5,1\le n\le 10^7$。