Counting Unique Binary Search Trees

You are given an integer n. Your task is to calculate the number of unique binary search trees (BSTs) that can be constructed using n distinct nodes labeled from 1 to n. It is known that the answer is given by the nth Catalan number. In mathematical terms, the Catalan numbers can be defined as follows:

\( C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i} \)

Alternatively, the explicit formula is: \( C_n = \frac{1}{n+1} \binom{2n}{n} \).

Since the numbers grow very rapidly, compute the number modulo \(10^9+7\) (i.e., 1000000007).

inputFormat

The first line contains an integer T, the number of test cases. Each of the following T lines contains a single integer n representing the number of nodes.

outputFormat

For each test case, output the number of unique BSTs that can be formed using the given n nodes, modulo \(10^9+7\). Each result should be printed on a separate line.

## sample

3
3
5
10

5
42
16796

</p>