import sys def solve(): # 入力の一括読み込み input_data = sys.stdin.read().split() if not input_data: return N = int(input_data[0]) M = int(input_data[1]) K = int(input_data[2]) MOD = 998244353 # グラフに残すべき辺の数 E_target = N * (N - 1) // 2 - M # K本の辺がなければ距離Kのパスは作れない if E_target < K: print(0) return # パスカルの三角形による組み合わせ計算の事前構築 MAX_COMB = 610 COMB = [[0] * MAX_COMB for _ in range(MAX_COMB)] for i in range(MAX_COMB): COMB[i][0] = 1 for j in range(1, i + 1): COMB[i][j] = (COMB[i-1][j-1] + COMB[i-1][j]) % MOD # W[p][s][k]: サイズ p のレイヤーとサイズ s のレイヤーの間に、 # 各 s 側の頂点が少なくとも1本の辺を持つようにちょうど k 本の辺を張る組み合わせ W = [[[0 for _ in range(p * s + 1)] for s in range(N + 1)] for p in range(N + 1)] for p in range(1, N + 1): poly1 = [0] * (p + 1) for j in range(1, p + 1): poly1[j] = COMB[p][j] W[p][1] = poly1 + [0] * 0 for s in range(2, N + 1): prev = W[p][s-1] curr = [0] * (p * s + 1) for j in range(s - 1, p * (s - 1) + 1): if prev[j] == 0: continue for k in range(1, p + 1): curr[j + k] = (curr[j + k] + prev[j] * poly1[k]) % MOD W[p][s] = curr # Cost_nonzero[p][s]: p -> s の遷移において、内部辺も含めて e_add 本の辺を張る組み合わせ数 # (計算の高速化のため、組み合わせが 0 より大きいものだけを保持) Cost_nonzero = [[[ ] for _ in range(N + 1)] for _ in range(N + 1)] for p in range(1, N + 1): for s in range(1, N + 1): max_j = s * (s - 1) // 2 temp_cost = [0] * (max_j + p * s + 1) for j in range(max_j + 1): ways_in = COMB[max_j][j] if ways_in == 0: continue for k in range(s, p * s + 1): ways_between = W[p][s][k] if ways_between == 0: continue temp_cost[j + k] = (temp_cost[j + k] + ways_in * ways_between) % MOD for e_add, ways in enumerate(temp_cost): if ways > 0: Cost_nonzero[p][s].append((e_add, ways)) # DPテーブル: dp[使用した"その他の頂点"の数][直前レイヤーのサイズ][これまでに使った辺の数] dp = [[[0] * (E_target + 1) for _ in range(N + 1)] for _ in range(N - 1)] dp[0][1][0] = 1 # 初期状態:レイヤー0(頂点1のみ)、使用辺0 active_states = [(0, 1, 0)] ans_states = [[0] * (E_target + 1) for _ in range(N - 1)] # 距離 1 から N-1 までのレイヤーを順番に構築 for i in range(1, N): next_dp = [[[0] * (E_target + 1) for _ in range(N + 1)] for _ in range(N - 1)] for v, p, e in active_states: count = dp[v][p][e] limit_c = N - 2 - v # c: レイヤー i に配置する "その他の頂点" の数 for c in range(limit_c + 1): # i == K のときは頂点 N が必ず入るためサイズが +1 される s = c + 1 if i == K else c # レイヤーのサイズが 0 になった場合は探索打ち切り if s == 0: # 距離 K を超えていれば有効な終了状態として保存 if i > K: ans_states[v][e] = (ans_states[v][e] + count) % MOD continue comb_v = COMB[limit_c][c] base_ways = (count * comb_v) % MOD nxt_v = v + c p_s_nonzero = Cost_nonzero[p][s] # 今回のレイヤー構築で消費する辺の数の遷移 for idx in range(len(p_s_nonzero)): e_add, ways = p_s_nonzero[idx] nxt_e = e + e_add if nxt_e > E_target: break # e_addは昇順なので、超過したら終了 next_dp[nxt_v][s][nxt_e] = (next_dp[nxt_v][s][nxt_e] + base_ways * ways) % MOD dp = next_dp active_states = [] for _v in range(N - 1): for _p in range(N + 1): for _e in range(E_target + 1): if dp[_v][_p][_e] > 0: active_states.append((_v, _p, _e)) # N-1番目のレイヤーまで到達した(もしくはそこで終わった)状態を合流させる for v, p, e in active_states: ans_states[v][e] = (ans_states[v][e] + dp[v][p][e]) % MOD final_ans = 0 # 未到達レイヤー( L_infty ) 内での辺の張り方の組み合わせを計算 for v in range(N - 1): U = N - 2 - v # 未到達となる "その他の頂点" の数 max_U_edges = U * (U - 1) // 2 for e in range(E_target + 1): if ans_states[v][e] == 0: continue rem_e = E_target - e # L_infty 内で張るべき残り辺の数 if 0 <= rem_e <= max_U_edges: ways = COMB[max_U_edges][rem_e] final_ans = (final_ans + ans_states[v][e] * ways) % MOD print(final_ans) if __name__ == '__main__': solve()