#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; // 組み合わせ nCr の事前計算 mint C[500][500]; void init_C() { for (int i = 0; i < 500; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) { C[i][j] = C[i-1][j-1] + C[i-1][j]; } } } int main() { init_C(); int N, M, K; if (!(cin >> N >> M >> K)) return 0; int max_E = N * (N - 1) / 2; int target_E = max_E - M; if (target_E < K) { cout << 0 << endl; return 0; } // Poly[p][c][e] の事前計算 // p: 前の層のサイズ, c: 今の層のサイズ, e: 追加される辺の数 vector Poly(N + 1, vector(N + 1, vector(max_E + 1, 0))); for (int p = 1; p <= N; p++) { for (int c = 1; c <= N; c++) { int max_in = c * (c - 1) / 2; for (int e_in = 0; e_in <= max_in; e_in++) { mint w = C[max_in][e_in]; // ((1+x)^p - 1)^c の x^k の係数を計算 for (int j = 0; j <= c; j++) { mint sign = ((c - j) % 2 == 1) ? -1 : 1; mint ways_j = C[c][j] * sign; for (int k = 0; k <= p * j; k++) { int total_e = e_in + k; if (total_e <= max_E) { Poly[p][c][total_e] += w * ways_j * C[p * j][k]; } } } } } } // dp[v][p][e] vector dp(N - 1, vector(N + 1, vector(max_E + 1, 0))); vector total_valid(N - 1, vector(max_E + 1, 0)); dp[0][1][0] = 1; // v=0(プールから0個), p=1(頂点1のみ), e=0 for (int step = 1; step <= N; step++) { vector next_dp(N - 1, vector(N + 1, vector(max_E + 1, 0))); bool is_K = (step == K); for (int v = 0; v <= N - 2; v++) { for (int p = 1; p <= N; p++) { for (int e = 0; e <= target_E; e++) { if (dp[v][p][e].val() == 0) continue; int remain = N - 2 - v; // ステップKの場合は頂点Nが確定で入るため、プールから選ぶ数は0でもよい int start_c = is_K ? 0 : 1; for (int c_pool = start_c; c_pool <= remain; c_pool++) { int c_real = c_pool + (is_K ? 1 : 0); mint ways = C[remain][c_pool]; int max_add = p * c_real + c_real * (c_real - 1) / 2; for (int e_add = c_real; e_add <= max_add; e_add++) { if (e + e_add > target_E) break; if (Poly[p][c_real][e_add].val() == 0) continue; next_dp[v + c_pool][c_real][e + e_add] += dp[v][p][e] * ways * Poly[p][c_real][e_add]; } } } } } dp = next_dp; // K層目以降に到達したグラフは「有効な到達可能成分」として集計 if (step >= K) { for (int v = 0; v <= N - 2; v++) { for (int p = 1; p <= N; p++) { for (int e = 0; e <= target_E; e++) { total_valid[v][e] += dp[v][p][e]; } } } } } mint ans = 0; // 最後に、到達不能な頂点集合 U の内部の辺の選び方を掛ける for (int v = 0; v <= N - 2; v++) { int U = N - 2 - v; int max_unreach_E = U * (U - 1) / 2; for (int e = 0; e <= target_E; e++) { int e_unreach = target_E - e; if (e_unreach >= 0 && e_unreach <= max_unreach_E) { ans += total_valid[v][e] * C[max_unreach_E][e_unreach]; } } } cout << ans.val() << endl; return 0; }