Charles 喜欢学习。他经常访问维基百科来学习计算机科学。最近，Charles 认真研究了一系列表达式，其中代数表达式对他产生了很大的影响。

他很好奇，由 $n$ 个不同的变量、基本算术运算（即加、减、乘、除）以及括号组成的代数表达式有多少种不同的形式，要求每个变量恰好出现一次，且每个运算符都位于一个变量或一对括号之后。你能帮他计算出结果对 $(10^9 + 7)$ 取模的值吗？

在本题中，如果两个代数表达式可以化简为相同的有理表达式，则认为它们是等价的。例如，假设 $a, b, c$ 和 $d$ 是变量，$(a - d)/(b - c)$ 与 $(d - a)/(c - b)$ 等价，$a/(b - c) * d$ 与 $a/((b - c)/d)$ 等价，但 $a/b + c/d$ 与 $d/c + b/a$ 不等价。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行，每行描述一个测试用例，包含一个整数 $n$。 $1 \le T, n \le 60000$。

输出格式

对于每个测试用例，输出结果对 $(10^9 + 7)$ 取模的值，每行输出一个。

样例

样例输入 1

6
1
2
3
4
5
6

样例输出 1

1
6
68
1170
27142
793002