转化条件是容易的：贪心后等价于统计所有满足下面条件的树：

• 每个点大于父亲

• 每个点大于前一个儿子

• 每个点小于前一个儿子的最后一个儿子

如果不看第三个条件，那么把整棵树用父亲兄弟表示法转为二叉树即可直接 DP。设新树为 $T$。

带上第三个条件之后，就容斥一下变成 $1-![\#3]$，就是选一些点钦定为大于前一个儿子的最后一个儿子，容斥系数为 $-1$，也就是再把这个点挂到他 $T$ 上的父亲 $v$ 不断跳右儿子的结果。以此建出一个新树 $T'$。

此时我们直接对 $T'$ 做 DP。发现其仍然是一棵二叉树，而边有三种：父子边，兄弟边，和容斥边。每个非叶子节点的左儿子是父子边，右儿子是兄弟边或者容斥边。想要通过 $T'$ 还原原树，先把所有兄弟边的下端向上移动一位，再把所有容斥边的下端向上移动两位。

首先可以发现根只有左儿子，所以我们只考虑根的左儿子。然后此时需要满足把所有后两种边松弛之后的原树合法，计算可得相当于设三种边的权值为 $-1,0,1$，那么需要让所有点的深度非负。注意这里的图论意义是每个点向上松弛的多余次数。所以设一个二维 DP 记录子树大小的最深深度即可。

还有一个要特判的是，叶子不能有兄弟，所以一个左儿子为空的树不能在右儿子是兄弟边。

同时，容斥边跳的时候必须一直挂在右儿子上，所以一个点有右儿子的时候左儿子不能有容斥边跳上来。

注意特判 $n=1$。

复杂度 $O(n^3)$，跑得略微慢。这个做法可以做非质数模数，所以还是有点用的。

#pragma GCC optimize("Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int n,mod,dp[808][808],C[808][808];
inline void ad(int &x,int y){
    x+=y;if(x>=mod)x-=mod;
}
signed main(){
    cin>>n>>mod;
    if(n==1)return cout<<"1\n",0;
    for(int i=C[0][0]=1;i<=n;i++)
        for(int j=C[i][0]=1;j<=i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    int m=n+1>>1;
    for(int i=0;i<=m;i++)dp[1][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=m;j++)ad(dp[i][j],dp[i-1][min(m,j+1)]);
        for(int j=1;j<=m;j++)ad(dp[i][j],mod-dp[i-1][j-1]);
        for(int j=1;j<i-1;j++){
            for(int p=0;p<=m;p++)
                ad(dp[i][p],1ll*dp[j][0]*dp[i-1-j][p]%mod*C[i-1][j]%mod);
            for(int p=1;p<=m;p++)
                ad(dp[i][p],mod-1ll*dp[j][0]*dp[i-1-j][p-1]%mod*C[i-1][j]%mod);
        }
    }
    cout<<dp[n-1][0]<<endl;
    return 0;
}