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
#include <cstdio>
#include <cstring>
#include <algorithm>

using u64 = unsigned long long;

const int N = 1e7 + 10;

int dp[N], sum[N];
int n, m, mod;

inline void add(int &x, int y) {
  if ((x += y) >= mod) x -= mod;
}

inline void sub(int &x, int y) {
  if ((x -= y) < 0) x += mod;
}

int main() {
  scanf("%d%d%d", &n, &m, &mod);
  int *u = dp;
  for (int i = 0; i < m; ++i) u[i] = (m - i) % mod;
  for (int i = 1; i < n; ++i) {
    int *v = u + m;
    for (int j = m - 2; j >= 0; --j) add(u[j], u[j + 1]);
    for (int j = m - 1; j >= 0; --j) {
      sum[j] = sum[j + 1];
      add(sum[j], u[j]);
    }
    for (int j = 0; j < m; ++j) v[j] = (u64)u[0] * (m - j) % mod;
    for (int j = 1; j < m; ++j) sub(v[j], (u64)u[m - j] * (m - j) % mod);
    for (int j = 0; j < m - 1; ++j) sub(v[j], sum[j + 1]);
    u = v;
  }
  int ret = 0;
  for (int i = 0; i < m; ++i) add(ret, u[i]);
  printf("%d\n", ret);
  return 0;
}