TREE SHAPES

Problem Statement:

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 it’s shape looks different.

Input Specification:

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 Specification:

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^9+7.

Input Constraints:

1<=t<=100

1<=n<=50

Sample Input:

4
1
2
3
4

Sample Output:

1
2
5
14