Structurally Unique Binary Trees of Dragon Balls

Goku has ‘N’ Dragon Balls, where each Dragon Ball is unique. The ith Dragon Ball has ‘i’ stars on it, meaning the first Dragon Ball has 1 star, the second has 2 stars, and so on.

Gohan needs to arrange these ‘N’ Dragon Balls in a binary tree format, ensuring the following conditions are met:

• The left subtree of any Dragon Ball ‘D’ should only have Dragon Balls with fewer stars than ‘D’.
• The right subtree of any Dragon Ball ‘D’ should only have Dragon Balls with more stars than ‘D’.

Objective:

Determine how many structurally unique binary trees can be constructed following the conditions provided. Return the count of these trees modulo 10⁹ + 7.

Input:

First line contains an integer 'T', the number of test cases.
Then, for each test case, a single integer ‘N’ is given, denoting the number of Dragon Balls.

Output:

Output the number of structurally unique binary trees for each test case on a new line.

Example:

Input:
2
2
3

Output:

2
5

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• Time Limit: 1 second

Note:

You do not need to print anything; it has been managed for you. Implement the function provided.