如题，我用的方法和题解不同，无法通过这组数据。

35 4 10007

159

具体是设 $s_i$ 表示大小为 $i$ 的树，子树中根节点度数为 $d-1$，其余点度数为 $d$ 或 $1$ 的方案数。

$f_{i,j}$ 表示大小为 $i$ 的树，子树中根节点度数为 $d-1$，其余点度数为 $d$ 或 $1$，最深层有 $j$ 个节点的方案数。$s$ 可由 $f$ 直接得到。

最后对重心做个背包即可。

求大佬证明或证伪。

#include"bits/stdc++.h"
using namespace std;
const int maxn = 1010;
int f[maxn][maxn],g[maxn][maxn],n,d,mo,pw[maxn],ip[maxn],s[maxn],v[maxn];
int ksm(int b,int t){
	int ret=1;
	while(t){
		if(t&1)ret=(1ll*ret*b)%mo;
		b=(1ll*b*b)%mo;
		t>>=1;
	}
	return ret;
}
int inv(int x){
	return ksm(x,mo-2);
}
int C(int u,int d){
	return 1ll*(1ll*ip[d]*ip[u-d]%mo)*pw[u]%mo;
}
int Cc(int u,int d){
	int ans=1;
	for(int i=1;i<=d;i++)
		ans=1ll*ans*(u-i+1)%mo;
	for(int i=1;i<=d;i++)
		ans=1ll*ans*inv(i)%mo;
	return ans;
}
int main(){
	cin>>n>>d>>mo;
	f[1][1]=1,pw[0]=ip[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=1ll*pw[i-1]*i%mo,ip[i]=inv(pw[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			int b=(d-1);
			for(int k=b;k<=j*b;k+=b){
				f[i+k][k]=(f[i+k][k]+f[i][j])%mo;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			s[i]=(s[i]+f[i][j])%mo;
	g[0][0]=1;
	int Lim=(n)/2;
	for(int lf=1;lf<=Lim;lf++){
		for(int i=d;i>=1;i--)
			for(int j=n;j>=1;j--)
				for(int v=1;v<=i;v++)
					if(j>=lf*v){
						g[i][j]=(g[i][j]+1ll*g[i-v][j-lf*v]*Cc(s[lf]+v-1,v)%mo)%mo;
					}
	}
	cout<<g[d][n-1]%mo<<endl;
}