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

using namespace std;

struct cell {
	int64_t p;
	int64_t z;
};

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio (false);
	int64_t n, m, p, i, j, w, d;
	cin >> n >> m >> p;

	vector<cell> c[2]={vector<cell>(m), vector<cell>(m)};
	vector<int64_t> b(m);
	int s, ns, tmp;
	s = 0;
	ns = 1;
	for(j = 0; j < m; ++j) {
		c[s][j].p = 1;
	}
	c[s][0].z = 1;
	for (i = 0; i < n; ++i) {
		d = 0;
		for (j = 0; j < m; ++j) {
			d = (d + c[s][j].p + j * c[s][j].z) % p;
			c[ns][j].p = ((m - j) * d) % p;
			c[ns][j].z = ((m - j) * c[s][j].p) % p;
			if (j > 0) {
				b[j - 1] = (((m - j) * c[s][j].z) % p);
			}
		}
		d = 0;
		for (j = m - 2; j >= 0 ; --j) {
			d = (d + b[j]) % p;
			c[ns][j].p = (c[ns][j].p + ((d * (j + 1)) % p)) % p;
			c[ns][j].z = (c[ns][j].z + d) % p;
		}
		tmp = s;
		s = ns;
		ns = tmp;
	}
	int64_t sum = 0;
	for (j = 0; j < m; ++j) {
		sum = (sum + c[s][j].z) % p;
	}

	cout << sum << "\n";
}