| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 512 MB | 4 | 2 | 2 | 100.000% |
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 (109 + 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 (109 + 7) in one line.
6 1 2 3 4 5 6
1 6 68 1170 27142 793002