Counting Rooted m-ary Trees

Given two integers n and m, count the number of distinct rooted m-ary trees with exactly n nodes (the nodes are unlabeled). A rooted m-ary tree is defined recursively as follows:

An empty tree is considered as having 0 nodes. A non‐empty tree consists of a root node and an ordered sequence of m subtrees. Two rooted trees are considered identical if and only if their roots are the same and their subtrees (from left to right) are pairwise identical. In particular, two empty trees are considered identical.

The answer should be computed modulo \(10\,007\). In other words, if \(dp(n)\) denotes the number of trees with exactly \(n\) nodes, then for \(n\ge 1\) an arbitrary tree is constructed by having a root and an ordered m‐tuple of trees, where the total number of nodes in the subtrees sum to \(n-1\). This gives the recurrence \[ \displaystyle dp(0)=1, \quad dp(n)=\sum_{n_1+\cdots+n_m=n-1}dp(n_1)\cdots dp(n_m) \; (n\ge1). \]

For example, when \(m=2\) the sequence begins as \(dp(0)=1,\; dp(1)=1,\; dp(2)=2,\; dp(3)=5, \dots\).

inputFormat

The input consists of two space‐separated integers n and m, where n is the total number of nodes and m is the fixed number of children for the m-ary tree.

outputFormat

Output a single integer which is the number of distinct rooted m-ary trees with exactly n nodes, computed modulo \(10\,007\).

sample

1 2

1