1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll mod,mod2;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

VI dp[1010][2][2];
int n;
ll inv[1010],fac[1010];

void upd(ll &a,ll b) {
	a+=b; if (a>=mod2) a-=mod2;
}

void gao(int n,int fl,int fr) {
	if (!dp[n][fl][fr].empty()) return;
	int maxd=0;
	for (int l=0;l<n;l++) {
		int r=n-1-l;
		gao(l,1,fr); gao(r,fl,1);
		auto &dl=dp[l][1][fr],&dr=dp[r][fl][1];
		if (fl&&fr) maxd=max(maxd,max(min(SZ(dl),SZ(dr))+1,max(SZ(dl),SZ(dr))));
		if (!fl&&fr) maxd=max(maxd,max(SZ(dl)+1,SZ(dr)));
		if (fl&&!fr) maxd=max(maxd,max(SZ(dl),SZ(dr)+1));
		if (!fl&&!fr) maxd=max(maxd,max(SZ(dl),SZ(dr)));
	}
	vector<ll> tmp(maxd,0);
	for (int l=0;l<n;l++) {
		int r=n-1-l;
		auto &dl=dp[l][1][fr],&dr=dp[r][fl][1];
		if (fl&&fr) {
			rep(j,0,SZ(dl)) rep(k,0,SZ(dr))
				upd(tmp[max(min(j,k)+1,max(j,k))],(ll)dl[j]*dr[k]);
		}
		if (!fl&&fr) {
			rep(j,0,SZ(dl)) rep(k,0,SZ(dr))
				upd(tmp[max(j+1,k)],(ll)dl[j]*dr[k]);
		}
		if (fl&&!fr) {
			rep(j,0,SZ(dl)) rep(k,0,SZ(dr))
				upd(tmp[max(j,k+1)],(ll)dl[j]*dr[k]);
		}
		if (!fl&&!fr) {
			rep(j,0,SZ(dl)) rep(k,0,SZ(dr))
				upd(tmp[max(j,k)],(ll)dl[j]*dr[k]);
		}
	}
	for (auto p:tmp) dp[n][fl][fr].pb(p%mod*inv[n]%mod);
}

int k;
ll ans[1010][1010];
int main() {
	scanf("%d%d%lld",&n,&k,&mod);
	mod2=mod*mod;
	dp[0][0][0]=dp[0][0][1]=dp[0][1][0]=dp[0][1][1]=VI{1};
	fac[1]=inv[1]=1;
	for (int i=2;i<=n;i++) {
		fac[i]=fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for (int i=1;i<=n;i++) {
		gao(i,0,0);
		rep(j,0,SZ(dp[i][0][0])) {
			ans[i][j]=dp[i][0][0][j]*fac[i]%mod;
		}
	}
	printf("%lld\n",ans[n][k]);
}