SP27313 VECTAR6 - Number of Binary Trees

Changu has to deal with a very simple problem. He has to find the number of binary trees of height **n** where for each node the left subtree is at least as high as the right subtree. **NOTE**: The height of the binary tree here is in terms of the nodes, i.e, number of nodes in the path from the root to the deepest leaf node. Hence, the height of a tree with only root node is 1.

The first line contains **T**, the number of test cases. The following **T** lines contain a number **N**.

For each **N** output the number of binary trees of height **N** where for each node the left subtree is at least as high as the right subtree. As the answer can be large, you have to print answer modulus 1000000007