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

vector<long long> poc, kon, poc1;

int main()
{
    long long n,m,p,a,b,c,d,e;
    scanf("%lld%lld%lld", &n, &m, &p);
    poc.resize(m + 9, 0);
    kon.resize(m + 9, 0);
    poc1.resize(m + 9, 0);
    for(int i=1; i<=m; i++)
    {
        poc[i] = (poc[i-1] + i) % p;
        kon[m - i + 1] = (kon[m - i + 2] + i) % p;
    }
    for(int k=2; k<=n; k++)
    {
        a = poc[m];
        b = 0;
        for(long long i=1; i<=m; i++)
        {
            d = kon[i + 1];
            e = poc1[i - 1];
            c = (i * a) + e - (i * d) - b;
            c %= p;
            while(c < 0) c += p;
            poc1[i] = c;
            b = (b + poc[i]) % p;
        }

        for(int i=1; i<=m; i++)
        {
            poc[i] = poc1[i];
            kon[m - i + 1] = poc1[i];
        }
    }
    a = poc[m];
    printf("%lld", a);
    return 0;
}