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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int n,k,MOD,C[1005][1005];
int f[1005][13][2],aa[20];
int main()
{
	cin>>n>>k>>MOD;
	if(k>11)
	{
		puts("0");
		return 0;
	}
	for(int i=0;i<=n;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
	f[0][0][0]=f[1][1][0]=1;
	f[0][0][1]=f[1][1][1]=1; f[2][1][1]=2;
	for(int i=2;i<=n;++i)
		for(int j=1;j<=i;++j)
		{
			register int c=C[i-1][j-1];
			auto&Fj=f[j-1],&Fij=f[i-j],&Fi=f[i];
			{
			int s1=0,s2=0;
			for(int p=0;p<=k;++p)
			{
				int X=p?Fij[p-1][1]:0;
				if(i==j) X=(p==0);
				(s1+=Fj[p][0]); if(s1>=MOD) s1-=MOD;
				Fi[p][0]=(Fi[p][0]
				+((ll)s1*X+(ll)s2*Fj[p][0])%MOD*c)%MOD;
				(s2+=X); if(s2>=MOD) s2-=MOD;
			}
			}
			if(i>=3)
			{
			int s1=0,s2=0;
			for(int p=0;p<=k;++p)
			{
				ll u=(ll)s1*Fij[p][1]
				+(ll)s2*Fj[p][1];
				if(p) u+=Fij[p-1][1]*(ll)Fj[p-1][1];
				Fi[p][1]=(Fi[p][1]+u%MOD*c)%MOD;
				(s1+=Fj[p][1]); if(s1>=MOD) s1-=MOD;
				(s2+=Fij[p][1]); if(s2>=MOD) s2-=MOD;
			}
			}
		}
	for(int j=1;j<=n;++j)
	{
		int s1=0,s2=0;
		for(int p=0;p<=k;++p)
		{ 
			(s1+=f[j-1][p][0])%=MOD;
			aa[p]=(aa[p]+((ll)s1*f[n-j][p][0]
			+(ll)s2*f[j-1][p][0])%MOD*C[n-1][j-1])%MOD;
			(s2+=f[n-j][p][0])%=MOD;
		}
	}
	int ans=aa[k];
	ans=(ans%MOD+MOD)%MOD;
	cout<<ans<<"\n";
}