405813: GYM102114 L Lost In The Echo

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 that can be built up from n distinct variables, elementary arithmetic operations (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⁹ + 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.

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 ≤ T, n ≤ 60 000.

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

6
1
2
3
4
5
6

1
6
68
1170
27142
793002