Uniformly Branched Trees

题意翻译

题目大意：给定三个数 $n, d, \mathit{mod}$，求有多少种 $n$ 个点的不同构的树满足：除了度数为 $1$ 的结点外，其余结点的度数均为 $d$。答案对质数 $\mathit{mod}$ 取模。 数据范围：$1 \le n \le 1000$，$2 \le d \le 10$，${10}^8 \le \mathit{mod} \le {10}^9$。

题目描述

A tree is a connected graph without cycles. Two trees, consisting of $ n $ vertices each, are called isomorphic if there exists a permutation $ p:{1,...,n}→{1,...,n} $ such that the edge $ (u,v) $ is present in the first tree if and only if the edge $ (p_{u},p_{v}) $ is present in the second tree. Vertex of the tree is called internal if its degree is greater than or equal to two. Count the number of different non-isomorphic trees, consisting of $ n $ vertices, such that the degree of each internal vertex is exactly $ d $ . Print the answer over the given prime modulo $ mod $ .

输入输出格式

输入格式

The single line of the input contains three integers $ n $ , $ d $ and $ mod $ ( $ 1<=n<=1000 $ , $ 2<=d<=10 $ , $ 10^{8}<=mod<=10^{9} $ ) — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

输出格式

Print the number of trees over the modulo $ mod $ .

输入输出样例

输入样例 #1

5 2 433416647

输出样例 #1

1

输入样例 #2

10 3 409693891

输出样例 #2

2

输入样例 #3

65 4 177545087

输出样例 #3

910726