ソースコード
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#pragma warning (disable: 4996)
vector<pair<int, long long>>x[1024];
int N, K, P, S, F[1024], dp[44][444][1024], dp2[44][44], mod = 1000000007;
vector<int>calc(int pos) {
if (pos == 0) { return vector<int>{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; }
int len = 0, sz = 1;
while (sz * 2 <= pos) { sz *= 2; len++; }
int t = pos - sz, cx = 0; vector<int>A(11, 0); A[0]++;
for (int i = 0; i < len; i++) {
if ((t / (1 << i)) % 2 == 1) cx++;
A[cx]++;
}
return A;
}
long long ncr(int n, int r) {
if (n < 0 || n < r) return 0;
return dp2[n - r][r];
}
void init() {
for (int i = 0; i < 44; i++) {
for (int j = 0; j < 44; j++) {
if (i == 0 || j == 0) dp2[i][j] = 1;
else dp2[i][j] = dp2[i - 1][j] + dp2[i][j - 1];
}
}
for (int i = 0; i < P; i++) {
vector<int>L1 = calc(i);
for (int j = 0; j < L1.size(); j++) { if (L1[j] == 0) { F[i] = j; break; } }
for (int j = 1; j < P; j++) {
vector<int>L2 = calc(j); bool OK = false;
for (int k = 0; k < 10; k++) {
if (L1[k] != L2[k + 1] && L2[k + 1] != 0) OK = true;
}
if (OK == true) continue;
long long res = 0, LA = 0, LB = 0, s1 = S;
for (int k = 0; k < 10; k++) { if (L2[k + 1] == 0) { if (LA == 0) LA = L1[k]; else LB += L1[k]; } }
for (int k = 0; k <= 10; k++) s1 -= L1[k];
for (int k = 0; k <= LA; k++) {
// k : LA の値
if (LA >= 1 && k == 0) continue;
for (int l = 0; l <= LB; l++) {
// l : LB の値
if (k + l > L2[0]) break;
res += ncr(LA, k) * ncr(LB, l) * ncr(s1, L2[0] - k - l);
}
}
x[i].push_back(make_pair(j, res));
}
}
}
int main() {
cin >> N >> K >> P; for (int i = 0; i < 11; i++) { if ((1 << i) == P) S = i; }
init();
if (K > 360) { cout << "0" << endl; return 0; }
dp[0][0][0] = 1;
for (int i = 0; i < N; i++) {
int SS = 0;
for (int j = i; j < N; j++) SS += min(S, N - j);
for (int j = max(0, K - SS); j <= K; j++) {
for (int k = 0; k < 1024; k++) {
if (dp[i][j][k] == 0) continue;
for (int l = 0; l < x[k].size(); l++) {
long long to = x[k][l].first, cost = x[k][l].second;
dp[i + 1][j + F[to]][to] += (1LL * dp[i][j][k] * cost) % mod;
if (dp[i + 1][j + F[to]][to] >= mod) dp[i + 1][j + F[to]][to] -= mod;
}
}
}
}
long long res = 0;
for (int i = 0; i < 1024; i++) res += dp[N][K][i];
cout << res % mod << endl;
return 0;
}