18568번 - 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 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.