F  Huge Number of Trees

All submissions for this problem are available.
Hermione needs to solve a tough homework problem in Arithmancy class. Professor Vector was discussing trees for some time and now he gives the problem: Say, there are n + 1 nodes numbered 0, 1, 2, ..., n. Node 0 is always the root of the tree. How many different trees can be formed using the remaining n nodes so that all leaves have the same depth and the degree of each nonleaf node is at least d? Here, depth of a node u is the number of edges we need to traverse from the root (Node 0) to reach u. A tree is different from another tree if there exists at least one pair of nodes (u, v) for which an edge between u and v is present in one tree, but absent in the other one. Hermione wants your help to write a program to solve this problem.
Note that by degree, we mean the total number of neighbors, not just the number of children.
Input
 The first line of the input contains a positive integer, T which denotes the number of test cases.
 For each case, there is one line of input containing two integers: n and the minimum degree of each nonleaf node, d.
Output
For each test case, print "Case i: ", and then the answer (mod 10^{9} + 7), where i is the testcase number, 1indexed.
Constraints
 1 ≤ T ≤ 2000
 2 ≤ n ≤ 500
 2 ≤ d ≤ 10
Example
Input: 3 2 2 3 2 4 2 Output: Case 1: 1 Case 2: 1 Case 3: 13
Explanation
Testcase 1: The only valid tree is shown below:
Testcase 2: The only valid tree is shown below:
Testcase 3: The 13 different valid trees are as shown below:
Author:  zubaerkh 
Tags  zubaerkh 
Date Added:  12112017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 