Given n, the number of nodes, find the number of different possible binary trees that can be constructed. A tree differs from another tree if its shape looks different.

Input

The first line is an integer t, denoting the number of test cases. Then each test case consists of one integer n, the number of nodes.

Output

For each test case print the number of possible trees that can be constructed using n nodes in a separate line.

Print the answer mod 10⁹+7.

Constraints

1 ≤ t ≤ 100

1 ≤ n ≤ 50

Example

Input:
4
1
2
3
4

Output:
1
2
5
14