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
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<stack>
using namespace std;
int N, K, P, i;
int pierwsze[10001]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
long long wyn = 0;
int p[1002],pp[1002],pb[1002];
bool sprawdz();	
long long nnadk(int n, int k);
void perm(int k);

int main()
{
//ios_base::sync_with_stdio(0);
for(i = 1; i <= 1001;++i) p[i]=i;
cin >> N >> K >> P;
//cout << nnadk(N, K) << endl;
if(N >= (1 << (K- 1)) + 1){
	if(K == 1){
		for(i = 1; i <= N; ++i){wyn += nnadk(N-1, i) % P;	}
	}
	else {
		perm(N);	
		}
}
cout << wyn;
return 0;
}
long long nnadk(int n, int k){
	int tab[1001];
	for(int i = 0; i <= n; ++i) tab[i] = 0;
	long long wyn = 1;
	if(k > (n - k)) {
		for(int j = k + 1; j <= n; ++j){
			int i = 0, liczba = j;
			while(liczba > 1) {
				if(liczba%pierwsze[i] ==0){
					tab[pierwsze[i]]++;
					liczba /= pierwsze[i];
				}
				else i++;
			}
		}
		for(int j = 2; j <= n - k; ++j){
			int i = 0, liczba = j;
			while(liczba > 1) {
				if(liczba%pierwsze[i] ==0){
					tab[pierwsze[i]]--;
					liczba /= pierwsze[i];
				}
				else i++;
			}
		}

	}
	else{
		for(int j = n - k + 1; j <= n; ++j){
			int i = 0, liczba = j;
			while(liczba > 1) {
				if(liczba%pierwsze[i] ==0){
					tab[pierwsze[i]]++;
					liczba /= pierwsze[i];
				}
				else i++;
			}
		}
		for(int j = 2; j <= k; ++j){
			int i = 0, liczba = j;
			while(liczba > 1) {
				if(liczba%pierwsze[i] ==0){
					tab[pierwsze[i]]--;
					liczba /= pierwsze[i];
				}
				else i++;
			}
		}

	}
	//for(int i = 1; i <= n; ++i) cout << tab[i] <<" "; cout << endl;
	for(int i = 2; i <= n; ++i) {
		while(tab[i]--) wyn = wyn*i % P;
	}
return wyn;
}
void perm(int k){
	if (k == 1) {
		if (sprawdz()){
			wyn++;
			//for(int i = 1; i <= N; ++i) cout << p[i] <<" "; cout << endl;
		}			
	}
	else {
		for(int i = 1; i <= k; ++i){
			swap(p[i], p[k]);
			perm(k-1);
			swap(p[i], p[k]);
		}
	}		
}

bool sprawdz(){
	int ile = 0;
	for(int i = 1; i <= N; ++i)  {
		pp[i] = p[i];
		pb[i] = 0;
	}
	int n = N - 1;
	bool w = false;
	while(n){
		for(int i = 1; i <= N; ++i) {
			if(pb[i] == 0){
				int j = i - 1;
				while(pb[j] == 2) j--;
				int z = i + 1;
				while(pb[z] == 2) z++;
			    if (pp[j] > pp[i] || pp[z] > pp[i]) {
					n--;
					pb[i] = 1;
				}
			}
			
		}
		for(int i = 1; i <= N; ++i) {
			if(pb[i] == 1) {
				pp[i] = 0;
				pb[i] = 2;
			}
		}
		ile++;
		if(ile > K) return false;
		}
return ile == K;			
}