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
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef vector<int> vint;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

lld dp[5120][5120];
lld p[5120][5120];
lld n, m, mod;

int main(){
	scanf("%lld%lld%lld",&n,&m,&mod);
	
	//puts("dp:");
	for(lld i=1;i<=m;++i){
		for(lld j=1;i+j-1<=m;++j){
			dp[i][j]=1;
			//printf("%lld ",dp[i][j]);
		}
		//puts("");
	}
	//puts("p:");
	for(lld i=1;i<=m;++i){
		p[i][1]=dp[i][1];
		//printf("%lld ",p[i][1]);
	}
	//puts("");
	for(lld j=2;j<=m;++j){ //długość przedziału
		for(lld i=1;i+j-1<=m;i++){ //po początkach
			p[i][j]=(p[i][j-1]+p[i+1][j-1]+mod-p[i+1][j-2]+dp[i][j])%mod;
			//printf("%lld ",p[i][j]);
		}
		//puts("");
	}
	while(--n){
		//puts("dp:");
		for(lld j=1;j<=m;++j){
			for(lld i=1;i+j-1<=m;++i){
				dp[i][j]=(p[1][m]+mod+mod-p[1][i-1]-p[i+j][m+1-i-j])%mod;
				//printf("%lld ",dp[i][j]);
			}
			//puts("");
		}
		//puts("p:");
		for(lld i=1;i<=m;++i){
			p[i][1]=dp[i][1];
			//printf("%lld ",p[i][1]);
		}
		//puts("");
		for(lld j=2;j<=m;++j){ //długość przedziału
			for(lld i=1;i+j-1<=m;i++){ //po początkach
				p[i][j]=(p[i][j-1]+p[i+1][j-1]+mod-p[i+1][j-2]+dp[i][j])%mod;
				//printf("%lld ",p[i][j]);
			}
			//puts("");
		}
				
	}
	printf("%lld",p[1][m]);
	
	
	return 0;
}