VECTAR6 - Number of Binary Trees

no tags 

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


hide comments
smso: 2023-12-16 03:30:40

Useful testcases:
7
1 2 3 4 5 6 7
output without modulo division:
1 2 8 96 10368 108615168 11798392572168192

akash25: 2016-07-07 22:55:54

@piyush can u please tell me where i have gone wrong with my last submission...I believe i'm doing it correctly

Last edit: 2016-07-08 05:58:47
azam_9: 2016-07-04 12:28:16

@psetter-is o(1) solution possible??

Re: The intended solution is to answer each query in O(1). Good luck :)

Last edit: 2016-07-04 12:36:46
Piyush Kumar: 2016-07-04 11:42:31

The problem statement has been updated to make things more clear !

pranav_arora: 2016-07-04 09:51:56

@Vipul: I initially took the height as the number of edges from the root to the deepest leaf but in this problem, it is the number of nodes on the path from root to the deepest leaf. :)

Vipul Srivastava: 2016-07-04 07:59:40

@pranav what do you mean by the statement that height is in terms of nodes??

pranav_arora: 2016-07-04 02:32:06

How is the answer 1 for n=1? There are two binary trees that satisfy the condition for n=1. With two nodes, 1-2 and with three nodes, 1-2, 1-3.

EDIT: Height is in terms of nodes. Also, please mention that we have to find the answer modulo 10**9+7.
Re: Updated, thanks :)

Last edit: 2016-07-04 11:00:42

Added by:Piyush Kumar
Date:2016-07-03
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY