Count Hierarchy Trees

You are given an integer n and are required to compute the number of distinct Hierarchy Trees that can be formed using n distinct integers. A Hierarchy Tree is defined similarly to a unique binary search tree. The answer can be shown to be the n-th Catalan number, but you must compute it modulo \(10^8+7\) (i.e. 100000007).

For example, when n = 3, there are 5 distinct hierarchy trees, and when n = 4, there are 14 distinct trees. You are required to solve multiple test cases.

Note: All formulas must be represented in LaTeX format. The recurrence relation for the Catalan numbers is given by:

[ dp[0] = 1, \quad dp[n] = \sum_{i=0}^{n-1} dp[i] \times dp[n-1-i] \quad \text{for } n \ge 1. ]

All computations are done modulo \(100000007\).

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a single integer n (1 \le n). For each test case, you are required to compute the number of Hierarchy Trees for that value of n.

outputFormat

For each test case, output a single integer in a new line: the number of distinct Hierarchy Trees modulo \(100000007\).

## sample

3
1
2
3

1
2
5

</p>