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
// Author: Piotr Grzegorczyk (ud2@interia.eu)
// Task: PA2018/SKW

// rozwiazania tylko dla n<=12 lub k=1 :(

#include <bits/stdc++.h>
using namespace std;

const int skw[16][16] = {
	{0},
	{1,   0},
	{0,   2,   0},
	{0,   4,   2,   0},
	{0,   8,  16,   0,   0},
	{0,  16, 100,   4,   0,   0},
	{0,  32, 616,  72,   0,   0,   0},
	{0,  64, 4024, 952,   0,   0,   0,   0}, 
	{0, 128, 28512, 11680,   0,   0,   0,   0,   0}, 
	{0, 256, 219664, 142800, 160,   0,   0,   0,   0,   0}, 
	{0, 512, 1831712, 1788896, 7680,   0,   0,   0,   0,   0,   0}, 
	{0, 1024, 16429152, 23252832, 233792,   0,   0,   0,   0,   0,   0,   0},
	{0, 2048, 157552000, 315549312, 5898240,   0,   0,   0,   0,   0,   0,   0,   0} 
};

unsigned int powmod(unsigned int x, unsigned int e, unsigned int m) {
	unsigned int r = 1;
	unsigned int t = x;
	while (e) {
		if (e & 1) r = 1ull*r*t % m;
		t = 1ull*t*t % m;
		e >>= 1;
 	}
	return r;
}

int main() {

	//freopen("test01.in", "rb", stdin);

	int N, K, P;
	scanf("%d%d%d", &N, &K, &P);
	
	if (N <= 12) {
		printf("%d\n", skw[N][K] % P);		
	} else if (K==1) {
		printf("%d\n", powmod(2, N-1, P));
	} else {
		printf("%d\n", 0);
	}
	
	return 0;	
}