Complete Tree Labeling#402
A complete -ary tree is a -ary tree in which all leaves have the same depth and all internal nodes have degree . It is not difficult to determine the number of nodes in such a tree.
Given the depth and branching factor of such a tree, count the number of ways to label the nodes of the tree so that the label of each node is less than the labels of all its descendants. When k=2, this property describes the data structure known as a binary heap (priority queue). When labeling a tree with nodes, assume you can use the labels 1, 2, 3, \ldots, N-1, N.
The input consists of several lines. Each line contains two integers and , where k > 0 is the branching factor of the complete -ary tree, and d > 0 is its depth. Your program should work for all pairs where k \cdot d \le 21.
For each line of input, output one integer — the number of labelings of the -ary tree that satisfy the conditions above.
Example 1