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
#include <cstdio>
#include <vector>
using namespace std;

int main() {
	int n, m, i, j, k;
	long long p;
	scanf("%d%d%lld", &n, &m, &p);
	// dp_start[i] - suma wynikow dla mal. o dl. 0 <= j < n konczacych sie pomalowaniem o koncu w i-tym segmencie
	// dp_end[i] - suma wynikow dla mal. o dl. 0 <= j < n konczacych sie pomalowaniem o poczatku w i-tym segmencie
	vector<int> dp_start(m), dp_end(m), temp_start(m), temp_end(m);
	for (i = 0; i < m; ++i) {
		dp_start[i] = i + 1;
		dp_end[m - i - 1] = i + 1;
	}	
	for (k = 1; k < n; ++k) {
		long long sum = 0;
		for (i = 0; i < m; ++i)
			sum = (sum + dp_start[i]) % p;
		for (i = 0; i < m; ++i) {
			temp_start[i] = (sum * (i + 1)) % p;
			temp_end[m - i - 1] = (sum * (i + 1)) % p;
		}
		long long sum_dol = sum; // suma dla zaczynajacych sie w j >= i + 1 
		long long sum_gora = sum; // suma dla konczacych sie w j < i 
		long long sum_start = 0;
		long long sum_end = 0;
		long long sum_sum_start = 0;
		long long sum_sum_end = 0;
		for (i = 0; i < m; ++i) {
			sum_dol = (sum_dol - dp_end[i] + p) % p;
			sum_gora = (sum_gora - dp_start[m - i - 1] + p) % p;
			temp_start[i] = ((long long) temp_start[i] - (sum_dol * (i + 1)) % p + p) % p;
			temp_end[m - i - 1] = ((long long) temp_end[m - i - 1] - (sum_gora * (i + 1)) % p + p) % p;
			sum_sum_start = (sum_sum_start + sum_start) % p;
			sum_sum_end = (sum_sum_end + sum_end) % p;
			temp_start[i] = ((long long) temp_start[i] - sum_sum_start + p) % p;
			temp_end[m - i - 1] = ((long long) temp_end[m - i - 1] - sum_sum_end + p) % p;
			sum_start = (sum_start + dp_start[i]) % p;
			sum_end = (sum_end + dp_end[m - i - 1]) % p;
		}
		dp_start = temp_start;
		dp_end = temp_end;
	}
	long long wyn = 0;
	for (i = 0; i < m; ++i)
		wyn = (wyn + dp_start[i]) % p;
	printf("%lld", wyn);
	return 0;
}