MAIN75 - BST again

no tags 

 

N nodes are labled with integers from 1 to N. Now these N nodes are inserted in a empty binary search tree. But the constraint is that
we have to build this tree such that height of the tree is exactly equal to H. Your tast is to find how many distict binary search trees exists 
of these nodes such that their height is exactly equal to H ?

N nodes are labled with integers from 1 to N. Now these N nodes are inserted in a empty binary search tree. But the constraint is that we have to build this tree such that height of tree is exactly equal to H. Your tast is to find how many distict binary search trees exists of these nodes such that their height is exactly equal to H ?

Two BSTs are considered to be different if there exist a node whose parent is different in both trees.

Input

Input First line contains 1<=T<=10 the number of test cases. Follwomg T lines contains 2 integers each. N and H. 1<=N<=500, 0<=H<=500.

Output

For each test case print the required answer modulo 1000000007.

Example

Input:
1
2 1
Output:
2

hide comments
Min_25: 2016-12-08 09:02:05

Probably, intended solutions have the complexity of O(n^3), because the difference of the running time between O(n^(2 + epsilon)) solutions and O(n^3) solutions would be almost negligible for small N.

Last edit: 2016-12-08 12:58:46
Piyush Kumar: 2016-12-08 06:29:27

Is the intended solution better than O(N^3)?

VISHAL DEEPAK AWATHARE: 2015-01-29 09:20:35

is there a possibilty of like nodes are 3 and height is 20 ? then should we output 0?

Ravi Kiran: 2011-03-16 20:39:55

Just to clarify again -
1. Height of a BST with *only* root is 0.
2. *All* the nodes from 1..N *have* to be inserted into the BST.

Nice problem! :-)


Added by:Mahesh Chandra Sharma
Date:2011-03-13
Time limit:0.969s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA main contest #7