Problem Description

Charles enjoys learning. He often goes to the website Wikipedia to study computer science. Just now Charles seriously studied a series of expressions, in which algebraic expression has a great influence on him.

He is curious about how many different algebraic expressions built up from $n$ distinct variables, elementary arithmetic operations (i.e. addition, subtraction, multiplication and division), and brackets such that each variable appears exactly once and each operation is after a variable or a pair of brackets. Can you help him calculate the answer in modulo $(10^9 + 7)$?

Two algebraic expressions in this problem are considered as equivalent if and only if they can be simplified as the same rational expression. For example, assuming $a$, $b$, $c$ and $d$ are variables, $(a - d) / (b - c)$ is equivalent to $(d - a) / (c - b)$, $a / (b - c) * d$ is equivalent to $a / ((b - c) / d)$ but $a / b + c / d$ is not equivalent to $d / c + b / a$.

Input

The first line contains one integer $T$, indicating the number of test cases.
Each of the following $T$ lines describes a test case and contains only one integer $n$.
$1 \leq T, n \leq 60000$.

Output

For each test case, output the answer modulo $(10^9 + 7)$ in one line.

6
1
2
3
4
5
6

1
6
68
1170
27142
793002