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
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

long long int n,k,p,i,j,w,r,c,c1,s,backup[1007];
pair <long long int, long long int> tab[1007];
vector <long long int> v;
int main()
{
	scanf("%lld%lld%lld", &n, &k, &p);
	r=n;
	while(r > 1)
	{
		c++;
		r++;
		r/=2;
	}
//	printf("TEST n=%lld; k=%lld; p=%lld; log(n)=%lld;\n", n, k, p, c);
	if(k > c)
	{
//		printf("EXIT 1\n");
		printf("0");
	}
	else if(k == 1)
	{
//		printf("EXIT 3\n");
		printf("%lld", (2*n-2)%p);
	}
	else
	{
		for(i=1; i<=n; i++)
		{
			tab[i].ff=i;
		}
		while(next_permutation(tab+1, tab+n+1))
		{
			for(i=1; i<=n; i++)
			{
				backup[i]=tab[i].ff;
				tab[i].ss=0;
//				printf("%lld ", tab[i].ff);
			}
//			puts("");
			r=0;
			s=n;
			while(s > 1)
			{
				r++;
				v.clear();
				c1=s;
				for(i=1; i<=c1; i++)
				{
					if(tab[i-1].ff < tab[i].ff && tab[i+1].ff < tab[i].ff)
					{
						tab[i].ss++;
						v.push_back(i);
					}
				}
				s=v.size();
				for(i=0; i<s; i++)
				{
					swap(tab[i+1], tab[v[i]]);
				}
				tab[s+1].ff=0;
			}
			if(r == k)
			{
				w++;
				w%=p;
			}
			for(i=1; i<=n; i++)
			{
				tab[i].ff=backup[i];
			}
		}
//		printf("EXIT 4\n");
		printf("%lld", w);
	}
	return 0;
}