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;

void createPatterns(int m, vector<pair<int,int>> *patterns){
	for(int dlogosc=1; dlogosc<=m;dlogosc++){
		for(int poczatek=0; poczatek<=m-dlogosc; poczatek++){
			patterns->push_back(make_pair(poczatek+1, poczatek+dlogosc));
		}
	}
}

bool noColision(vector<pair<int,int>> *patterns, int a, int b){
	int abeg=(*patterns)[a].first;
	int aend=(*patterns)[a].second;
	int bbeg=(*patterns)[b].first;
	int bend=(*patterns)[b].second;
	
	if(abeg>=bbeg && abeg<=bend)return true;
	if(bbeg>=abeg && bbeg<=aend)return true;
	return false;
}

long long claculate(int currentSztacheta, int n,vector<pair<int,int>> *patterns, int lastPattern,int p){
	
	
	
	long long suma=0;
	for(int i = 0; i<patterns->size();i++){
		if(noColision(patterns, i,lastPattern))//nie ma kolizji z poprzednim
			if(currentSztacheta==n)
				suma+=1;
			else suma+=claculate(currentSztacheta+1,n,patterns,i,p);
	}
	return suma%p;
}

int main(){
	int n,m,p;//n liczba sztachet
	scanf("%d %d %d", &n, &m, &p);
	vector<pair<int,int>> patterns;
	createPatterns(m,&patterns);
	
	
	//cout<<patterns.size()<<endl;
	cout<<claculate(1,n,&patterns,patterns.size()-1,p);
	
	
	return 0;
}