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
#include <cstdio>
#include <cstdint>
#include <vector>

int main () {
	int n;
	int64_t H, p;
	scanf("%d %lld %lld", &n, &H, &p);
	std::vector<int64_t> F(H + 2, 0), D(H + 2, 0), S(H + 2, 0), SS(H + 2, 0);
	int64_t mul = (H * (H + 1) / 2) % p;
	int64_t pwr = 1;
	for (int i = 1; i <= n; ++i) {
		int64_t sum = 0;
		for (int x = 1; x <= H; ++x) {
			D[x] = (pwr * x - F[x] + p) % p;
			sum = (sum + F[x]) % p;
			S[x] = (S[x - 1] + D[x]) % p;
			SS[x] = (SS[x - 1] + S[x]) % p;
		}
		for (int x = 1; x <= H; ++x) {
			F[x] = ((sum * x) % p + (x * S[H - x]) % p + SS[x - 1]) % p;
		}
		pwr = (pwr * mul) % p;
	}
	printf("%lld\n", S[H]);
	return 0;
}