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;

typedef long long int LL;

const int MAXN = 10000005;

LL R[MAXN], S_old[MAXN], SS_old[MAXN];

int main() {
  int n, m, p;
  cin >> n >> m >> p;

  for (int i = 1; i <= m; i++) R[i] = i;

  for (int i = 2; i <= n; i++) {
    S_old[0] = 0;
    SS_old[0] = 0;
    for (int x = 1; x <= m; x++) {
      S_old[x] = (S_old[x-1] + R[x]) % p;
      SS_old[x] = (SS_old[x-1] + S_old[x]) % p;
      R[x] = 0;
    }

    for (int x = 1; x <= m; x++) {
      R[x] = (R[x] + S_old[m] * x) % p;
      R[x] = (R[x] + (p - S_old[m-x]) * x) % p;
      R[x] = (R[x] + (p - SS_old[x-1])) % p;
    }

    //for (int x = 1; x <= m; x++)
    //  cerr << R[x] << " ";
    //cerr << "\n";
  }

  LL result = 0;
  for (int x = 1; x <= m; x++)
    result = (result + R[x]) % p;
  cout << result << "\n";

  return 0;
}