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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

#define SIZE 10'000'002

LL X, M, MOD;
LL gora_le[SIZE], dol_ge[SIZE], dol_na[SIZE], gora_na[SIZE];

void sumuj() {
  FOR(b, 1, M)
    gora_le[b] = (gora_le[b - 1] + gora_na[b]) % MOD;
  FORD(a, M, 1)
    dol_ge[a] = (dol_ge[a + 1] + dol_na[a]) % MOD;
}

int main() {
  cin >> X >> M >> MOD;
  FOR(a, 1, M) {
    gora_na[a] = a;
    dol_na[a] = M + 1 - a;
  }
  sumuj();
  REP(x, X - 1) {
    LL s_gora_le = 0;
    FOR(b, 1, M) {
      gora_na[b] = (b * (dol_ge[1] + MOD - dol_ge[b + 1]) + MOD - s_gora_le) % MOD;
      s_gora_le = (s_gora_le + gora_le[b]) % MOD;
    }
    LL s_dol_ge = 0;
    FORD(a, M, 1) {
      dol_na[a] = ((M + 1 - a) * (dol_ge[1] + MOD - gora_le[a - 1]) + MOD - s_dol_ge) % MOD;
      s_dol_ge = (s_dol_ge + dol_ge[a]) % MOD;
    }
    sumuj();
  }
  cout << dol_ge[1] << endl;
}