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
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int max_n = 1000;

unsigned int t[max_n]; //, tc1[max_n], tc2[max_n];
int n;
int k;
int p;

unsigned int powmod(unsigned int y, unsigned int z)
{
    unsigned long long result = 1;
    unsigned long long x = 2;

    while (y > 0) {
        if (y & 1) {
            result = (result * x) % z;
        }
        y = y >> 1;
        x = (x * x) % z;
    }
    return (uint) result;
}


int calc_rounds()
{
        int result = 0;
        int new_len = n;
        int cur_pos;
        int tc1[n];
        int tc2[n];

        for(int i = 0; i < n; ++i) {
                tc1[i] = tc2[i] = t[i];
        }

        while (new_len > 1) {
                result++;
                //print_tab(tc1, new_len, 1);
                for(int i = 1; i < new_len; ++i) {
                        if (tc1[i] < tc1[i-1]) {
                                tc2[i] = 0;
                        } else {
                                tc2[i-1] = 0;
                        }
                }
                //print_tab(tc2, new_len, 1);
                cur_pos = 0;
                for(int i = 0; i < new_len; ++i) {
                        if (tc2[i] != 0) {
                                tc1[cur_pos++] = tc2[i];
                        }
                }
                new_len = cur_pos;
                for(int i = 0; i < new_len; ++i) {
                        tc2[i] = tc1[i];
                }
        }
//        cout << '\n';
        return result;
}

int result_tab[max_n];

int main()
{
        cin >> n;
        cin >> k;
        cin >> p;

        int lg;

        if (k == 1) {
                cout << powmod(n-1, p) << '\n';
                return 0;
        }

        lg = (int) ceil(log2(n));

        if (k > lg) {
                cout << "0\n";
                return 0;
        }

        for(int i = 0; i < n; ++i) {
                t[i] = i+1;
        }

        do {
                int res;
                res = calc_rounds();
                result_tab[res]++;
        } while ( next_permutation(t, t+n) );

        cout << result_tab[k] << '\n';
        
        return 0;
}