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
// Karol Kosinski 2018
#include <cstdio>
#include <algorithm>
#include <list>
#include <iterator>
#include <stack>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOD(i,b,a) for(int i=(b)-1;i>=(a);--i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;
typedef long long LL;

const int NX = 1003;
int Perm[NX], KK[NX][NX];

LL pow2(int a, int p)
{
    LL res = 1, y = 2;
    while(a > 0)
    {
        if((a & 1) == 1) res = (res * y) % p;
        y = (y * y) % p;
        a >>= 1;
    }
    return res;
}

int log2(int x)
{
    int r = -1;
    while(x > 0)
    {
        x >>= 1;
        ++r;
    }
    return r;
}

int main()
{
    KK[3][1] = 4;
    KK[3][2] = 2;
    KK[4][1] = 8;
    KK[4][2] = 16;
    KK[5][1] = 16;
    KK[5][2] = 100;
    KK[5][3] = 4;
    KK[6][1] = 32;
    KK[6][2] = 616;
    KK[6][3] = 72;
    KK[7][1] = 64;
    KK[7][2] = 4024;
    KK[7][3] = 952;
    KK[8][1] = 128;
    KK[8][2] = 28512;
    KK[8][3] = 11680;
    KK[9][1] = 256;
    KK[9][2] = 219664;
    KK[9][3] = 142800;
    KK[9][4] = 160;
    KK[10][1] = 512;
    KK[10][2] = 1831712;
    KK[10][3] = 1788896;
    KK[10][4] = 7680;
    KK[11][1] = 1024;
    KK[11][2] = 16429152;
    KK[11][3] = 23252832;
    KK[11][4] = 233792;
    KK[12][1] = 2048;
    KK[12][2] = 157552000;
    KK[12][3] = 315549312;
    KK[12][4] = 5898240;

    int n = 12, k = log2(n - 1) + 1, p = 100000007;
    scanf("%d%d%d", &n, &k, &p);
    if(k == 1)
    {
        printf("%lld\n", pow2(n - 1, p));
        return 0;
    }
    int nnn = log2(n - 1) + 1;
    if(k > log2(n - 1) + 1)
    {
        printf("0\n");
        return 0;
    }
    //FOR(i,0,n) Perm[i] = i;
    //do {
    //    list<int> L;
    //    FOR(i,0,n)
    //    {
    //        L.push_back(Perm[i]);
    //        //DEBUG("%d ", Perm[i]);
    //    }
    //    int counter = n, iters = 0;
    //    while(counter > 1)
    //    {
    //        auto it = L.begin();
    //        stack<decltype(it)> S;
    //        while(it != L.end())
    //        {
    //            //DEBUG("\n%d", *it);
    //            auto pr = it, nx = it;
    //            if(*it != *L.begin()) advance(pr, -1);
    //            if(*it != *L.rbegin()) advance(nx, 1);
    //            if(*pr > *it or *it < *nx)
    //            {
    //                S.push(it);
    //                --counter;
    //            }
    //            ++it;
    //        }
    //        while(not S.empty())
    //        {
    //            L.erase(S.top());
    //            S.pop();
    //        }
    //        ++iters;
    //    }
    //    ++KK[n][iters];
    //    //DEBUG("\t[%d]\n", iters);
    //}
    //while(next_permutation(Perm, Perm + n));
    //FOR(i,1,k+1) DEBUG("KK[%d][%d] = %d;\n", n, i, KK[n][i]);
    printf("%d\n", KK[n][k] % p);
    return 0;
}