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
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
using i32 = int;

template<typename T> T load() { T x; cin >> x; return x; }
template<typename T> vector<T> loadN(int s) { vector<T> vt(s); for(auto& el : vt) el = load<T>(); return vt; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vt) { for(auto& el : vt) os << el << ' '; return os; }

template<typename T> T fastPow(T x, i32 W) { if(W == 0) return T(1); return fastPow(x * x, W / 2) * (W & 1 ? x : T(1)); }
struct Hash {
	Hash(i32 val = 0):val(val % MOD) {}
	Hash(i64 val):val(val % LMOD) {}
	Hash operator+(const Hash& el) const { return Hash(*this) += el; }
	Hash operator*(const Hash& el) const { return Hash(*this) *= el; }
	Hash operator+=(const Hash& el) { val += el.val; val %= MOD; return *this; }
	Hash operator*=(const Hash& el) { val = (1ll * val * el.val) % LMOD; return *this; }
	Hash inv() const { return fastPow(*this, MOD - 2); }
	Hash operator/(const Hash& el) const { return *this * el.inv(); }
	static void mutate(i32 val) { LMOD = MOD = val; }
	friend ostream& operator<<(ostream& os, const Hash& el) { return os << el.val; }
	static i32 MOD;
	static i64 LMOD;
	i32 val;
};
i64 Hash::LMOD = 0;
i32 Hash::MOD = 0;

struct Calculator {
	Calculator(i32 size):fact(size + 1), inv(size + 1) {
		fact[0] = 1;
		for(i32 i = 1 ; i <= size ; ++i) fact[i] = fact[i - 1] * i;
		inv[size] = fact[size].inv();
		for(i32 i = size - 1 ; i >= 0 ; --i) inv[i] = inv[i + 1] * (i + 1);
	}
	Hash choose(i32 k, i32 n) const { return fact[n] * inv[k] * inv[n - k];}
	Hash factorial(i32 n) const { return fact[n]; }
	vector<Hash> fact;
	vector<Hash> inv;
};

bool checkLifeTime(list<i32>&& world, i32 desire, i32 size) {
	while(desire --> 0) {
		if(size <= 1) return false;
		auto it = world.begin();
		auto previous = -1;
		while(it != world.end()) {
			auto future = next(it);
			auto surrounding = max(previous, (future == world.end() ? -1 : *future));
			previous = *it;
			if(*it < surrounding) {
				world.erase(it);
				--size;
			}
			it = future;
		}
	}
	if(size != 1) return false;
	return true;
}

i32 main() {
	ios::sync_with_stdio(false);
	auto seqSize = load<i32>();
	auto lifeTime = load<i32>();
	Hash::mutate(load<i32>());
	//auto calc = Calculator(seqSize);
	auto all = vector<i32>(seqSize);
	iota(all.begin(), all.end(), 1);
	if(lifeTime > ceil(log2(seqSize)) + 1) {
		cout << "0\n";
		return 0;
	}
	auto result = Hash(0);
	do {
		auto curr = list<i32>(all.begin(), all.end());
		if(checkLifeTime(move(curr), lifeTime, seqSize))
			result += 1;
	} while(next_permutation(all.begin(), all.end()));
	cout << result << '\n';
}