MAIN75  BST again
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:
20161208 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: 20161208 12:58:46 

Piyush Kumar:
20161208 06:29:27
Is the intended solution better than O(N^3)? 

VISHAL DEEPAK AWATHARE:
20150129 09:20:35
is there a possibilty of like nodes are 3 and height is 20 ? then should we output 0? 

Ravi Kiran:
20110316 20:39:55
Just to clarify again 

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