#include #include #include using namespace std; const long long MOD = 998244353; // 組み合わせ nCr の事前計算 (最大 1000 まで確保して配列外参照を防ぐ) long long C[1005][1005]; void init_C() { for (int i = 0; i <= 1000; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) { C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } } int main() { // 入出力の高速化 ios_base::sync_with_stdio(false); cin.tie(NULL); 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; // 構成すべき最短距離 K が残すべき辺の数より大きい場合、到達不可能 if (target_E < K) { cout << 0 << "\n"; return 0; } // Poly[p][c][e] の事前計算 // p: 前の層のサイズ, c: 今の層のサイズ, e: 追加される辺の数 vector>> Poly(N + 1, vector>(N + 1, vector(target_E + 1, 0))); for (int p = 1; p <= N; p++) { for (int c = 1; c <= N; c++) { // ((1+x)^p - 1)^c の x^k の係数を B[k] として先に計算 (O(c * target_E)に落とす) vector B(target_E + 1, 0); for (int k = 0; k <= target_E; k++) { for (int j = 0; j <= c; j++) { // p * j < k の場合は組み合わせが0になるためスキップ if (p * j < k) continue; long long sign = ((c - j) % 2 == 1) ? -1 : 1; long long ways_j = (C[c][j] * sign) % MOD; if (ways_j < 0) ways_j += MOD; long long term = (ways_j * C[p * j][k]) % MOD; B[k] = (B[k] + term) % MOD; } } // (1+x)^{c(c-1)/2} と B(x) を畳み込む int max_in = c * (c - 1) / 2; for (int total_e = 0; total_e <= target_E; total_e++) { for (int e_in = 0; e_in <= min(total_e, max_in); e_in++) { int k = total_e - e_in; long long ways_in = C[max_in][e_in]; long long term = (ways_in * B[k]) % MOD; Poly[p][c][total_e] = (Poly[p][c][total_e] + term) % MOD; } } } } // dp[v][p][e] // v: プール(N-2個の頂点)から使った数, p: 直前の層のサイズ, e: 使った辺の総数 vector>> dp(N - 1, vector>(N + 1, vector(target_E + 1, 0))); vector> total_valid(N - 1, vector(target_E + 1, 0)); dp[0][1][0] = 1; // 頂点1のみの層 (v=0, p=1, e=0) for (int step = 1; step <= N; step++) { vector>> next_dp(N - 1, vector>(N + 1, vector(target_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] == 0) continue; int remain = N - 2 - v; // ステップKの時は、プールからの頂点が0個でも「頂点N」が含まれるため有効 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); long long ways = C[remain][c_pool]; // 辺の追加数の範囲を絞って遷移 for (int e_add = c_real; e_add <= target_E - e; e_add++) { if (Poly[p][c_real][e_add] == 0) continue; long long add_val = (dp[v][p][e] * ways) % MOD; add_val = (add_val * Poly[p][c_real][e_add]) % MOD; next_dp[v + c_pool][c_real][e + e_add] = (next_dp[v + c_pool][c_real][e + e_add] + add_val) % MOD; } } } } } 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] = (total_valid[v][e] + dp[v][p][e]) % MOD; } } } } } long long 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) { long long ways = C[max_unreach_E][e_unreach]; long long add_val = (total_valid[v][e] * ways) % MOD; ans = (ans + add_val) % MOD; } } } cout << ans << "\n"; return 0; }