Description

If every non-leaf node of a tree has exactly $n$ children, we call it a strict $n$-ary tree. If the deepest nodes in the tree have depth $d$ (the root has depth $0$), then we call it a strict $n$-ary tree of depth $d$. For example, there are three strict $2$-ary trees of depth $2$, as shown below:

Given $n, d$, write a program to count the number of strict $n$-ary trees of depth $d$.

Input Format

Contains only two integers $n, d$ ($0 < n \le 32$, $0 \le d \le 16$). The testdata guarantees that you do not need to consider trees with more than $1024$ nodes on any level (i.e., $n^d \le 1024$).

Output Format

Contains only one number, which is the number of strict $n$-ary trees of depth $d$.

2 2

3

2 3

21

3 5

58871587162270592645034001

Hint

The answer is guaranteed to be at most $200$ decimal digits.

Translated by ChatGPT 5