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
#include <bits/stdc++.h>

using namespace std;

const int MAXM = 1e7+10;

long long n, m, mod, wyn;
int dp[MAXM], cp[MAXM], dp2[MAXM], cp2[MAXM], dp3[MAXM], cp3[MAXM], pref[MAXM];

int main()
{
	scanf("%lld%lld%lld", &n, &m, &mod);
	for(long long j=1; j<=m; ++j)
	{
		dp[j]=j;
		//cout<<dp[j]<<" ";
		dp2[j]=1;
		dp3[j]=(j*(m-j+1))%mod;
	}
	//cout<<endl;
	for(long long i=2; i<=n; ++i)
	{
		for(long long j=1; j<=m; ++j)
		{
			cp2[j]=dp3[j];
		}
		for(long long j=1; j<=m; ++j)
		{
			cp[j]=(cp[j-1]+cp2[j]+dp[m-j+1]*(j-1))%mod;
		}
		for(long long j=1; j<=m; ++j)
		{
			pref[j]=(pref[j-1]+dp[j]*j)%mod;
		}
		for(long long j=1; j<=m; ++j)
		{
			cp3[j]=(((dp3[j]*j)%mod)*(m-j+1)+(pref[j-1]*(m-j+1))+(pref[m-j]*j))%mod;
			//cp3[j]+=(pref[j-1]*(m-j+1))%mod;
			/*for(long long k=1; k<=j-1; ++k)
			{
				cp3[j]+=(((dp[k]*k)%mod)*(m-j+1))%mod;
				cp3[j]%=mod;
			}*/
			//cp3[j]+=(pref[m-j]*j)%mod;
			/*for(long long k=1; k<=m-j; ++k)
			{
				cp3[j]+=(((dp[k]*k)%mod)*j)%mod;
				cp3[j]%=mod;
			}*/
			//cp3[j]%=mod;
		}
		//cout<<i<<" --\n";
		for(long long j=1; j<=m; ++j)
		{
			dp[j]=cp[j];
			dp2[j]=cp2[j];
			dp3[j]=cp3[j];
			//cout<<j<<": "<<dp[j]<<" "<<dp2[j]<<" "<<dp3[j]<<endl;
		}
		//cout<<endl;
	}
	for(long long j=1; j<=m; ++j)
	{
		wyn+=dp[j];
	}
	wyn%=mod;
	printf("%lld\n", wyn);
	return 0;
}