Description

Compute the number of rooted $m$-ary trees (unlabeled) with $n$ nodes, modulo $10\,007$.

Two rooted trees are identical if and only if their roots are identical and, from left to right, each subtree is also identical. In particular, if both rooted trees are empty, they are considered identical.

Input Format

Input two integers $n$, $m$.

Output Format

Output the number of rooted $m$-ary trees (unlabeled) with $n$ nodes, modulo $10\,007$.

2 2

2

Hint

Constraints: $n, m \leq 127$.

Translated by ChatGPT 5