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.

Input

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

Output

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

Example

Input:
2
1
2
Output:
1
2

Constraints

T = 100000
1 <= N <= 10000000