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
#include <iostream>

using namespace std;
int n,m,M;
long long x=0;
long long dp[2][10000007];
long long t[2][10000007];
int id,id2;
int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>M;
    t[0][m]=1;
    for(int i=1;i<=n;i++)
    {
        id=i%2;
        id2=(i+1)%2;
        for(int j=1;j<=m;j++)
        {
            x+=t[id2][j-1];
            dp[id][j]=(j*t[id2][m]-(j*t[id2][m-j])-x);
            dp[id][j]%=M;
            if(dp[id][j]<0)
            {
                dp[id][j]+=M;
            }
            t[id][j]=((dp[id][j])+(t[id][j-1]))%M;
        }
        x=0;
    }
    cout<<t[n%2][m];
    return 0;
}