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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,m,mod;
int p[30000010];
int pp[30000010];
inline int f(int x,int y)
{
	return x*(m+1)+y;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int i,j;
	cin>>n>>m>>mod;
	p[f(0,m)]=pp[f(0,m)]=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			long long tmp=(long long)j*(p[f(i-1,m)]-p[f(i-1,m-j)])-pp[f(i-1,j-1)];
			p[f(i,j)]=(tmp+p[f(i,j-1)])%mod;
		}
		for(j=1;j<=m;j++)
			pp[f(i,j)]=(pp[f(i,j-1)]+p[f(i,j)])%mod;
	}
	cout<<(p[f(n,m)]+mod)%mod<<"\n";
	return 0;
}