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
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;

#define LL           long long
#define ULL          unsigned long long
#define PII          pair< int, int >
#define PLI          pair< long long, int >
#define VPII         vector< PII >
#define VPLI         vector< PLI >
#define MP           make_pair
#define REP(i,n)     for (int i=0;i<(n);++i)
#define FOR(i,a,b)   for (int i=(a); i<(b); ++i)
#define FORD(i,a,b)  for (int i=(a)-1; i>=(b); --i)
#define EACH(a, x)   for (auto& a : (x))
#define ALL(x)       (x).begin(), (x).end()

#define INF INT_MAX

int n, h;
ULL p;

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> h >> p;
    vector<ULL> res[2];
    res[0].reserve(h + 1);
    res[1].reserve(h + 1);
    REP(i, h + 1) {
        res[0].push_back(0);
        res[1].push_back(0);
    }
    ULL sum1, sum2, sum3 = 0;
    int cur = 0;
    REP(j, h) {
        res[cur][j] = h - j;            
    }
    REP(i, n - 1) {
        cur = 1 - cur;
        sum1 = sum2 = 0;
        FORD(j, h, 0) {
            res[cur][j] = (res[cur][j + 1] + ((h - j - 1) * res[1 - cur][j + 1]) % p) % p;
        }
        REP(j, h) {
            sum1 += res[1 - cur][j];
            sum2 += res[1 - cur][h - j];
            sum1 %= p;
            sum2 %= p;
            res[cur][j] += ((h - j) * ((p + sum1 - sum2) % p)) % p;
        }
    }

    // REP(j, h) {
    //     cout << res[1 - cur][j] << ' ' << res[cur][j] << endl;
    // }
    ULL total = 0;
    REP(j, h) {
        total = (total + res[cur][j]) % p; 
    }
    cout << total << endl;
}