新年快乐 。゚・ (⁄ ⁄>⁄ ︿ ⁄<⁄ ⁄) ・゚。

1741. 卡特兰数

在一个无限长的网格上,你最开始在 (0,0) 上,你每个单位时间可以向上走一格,或者向右走一格,在任意一个时刻,你往右走的次数都不能少于往上走的次数,问走到 (n,n) 有多少种不同的合法路径?

输入

一行一个整数 T 代表样例数目;接下来 T 行每行一个整数 n ,含义如上所示

T \le 10^5 + 1, 0 \le n \le 10^5

输出

对于每个 n ,每行输出方案数对 10^9+7 取模的结果

样例

标准输入 复制文本
1
1
标准输出 复制文本
1
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 17
通过 6