import sys MOD = 998244353 class Combination: def __init__(self, max_n: int, mod: int): self.max_n = max_n self.mod = mod self.fac = [1] * (max_n + 1) self.finv = [1] * (max_n + 1) self.inv = [1] * (max_n + 1) self._init() def _init(self) -> None: if self.max_n >= 1: self.inv[1] = 1 for i in range(2, self.max_n + 1): self.fac[i] = self.fac[i - 1] * i % self.mod self.inv[i] = ( self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod ) self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod def comb(self, n: int, k: int) -> int: if n < 0 or k < 0 or n < k: return 0 return ( self.fac[n] * self.finv[k] % self.mod * self.finv[n - k] % self.mod ) def solve() -> None: N, M, K = map(int, sys.stdin.buffer.readline().split()) E = N * (N - 1) // 2 R = E - M if N == 2: if M == 1: print(0) else: print(1) return C = Combination(E + 2, MOD) S = N - 1 # dp[j][k]: # 未到達の普通頂点数が j、 # 現在のBFS層のサイズが k である場合の q の多項式 dp = [ [ [0] * (E + 1) for _ in range(S) ] for _ in range(S) ] dp[S - 1][1][0] = 1 # 第1層から第K-1層まで作る for _ in range(1, K): ndp = [ [ [0] * (E + 1) for _ in range(S) ] for _ in range(S) ] for j in range(1, S): for k in range(1, S): # tmp = dp[j][k] * (q^k - 1)^nxt if not dp[j][k]: continue for nxt in range(1, j + 1): # tmp *= q^k - 1 tmpnxt = [(-value) % MOD for value in tmp] for degree in range(E + 1 - k): tmpnxt[degree + k] += tmp[degree] if tmpnxt[degree + k] >= MOD: tmpnxt[degree + k] -= MOD tmp = tmpnxt choose = C.comb(j, nxt) # 次の層内部の自由な辺数 offset = nxt * (nxt - 1) // 2 destination = ndp[j - nxt][nxt] for degree in range(E + 1 - offset): destination[degree + offset] += ( tmp[degree] * choose ) % MOD if destination[degree + offset] >= MOD: destination[degree + offset] -= MOD dp = ndp # 最終的な H(q) answer_polynomial = [0] * (E + 1) for r in range(S): for s in range(1, S): # 以下の自由辺数 # ・残りr頂点どうし # ・頂点Nと残りr頂点 # ・現在の層と残りr頂点 offset = ( r * (r - 1) // 2 + r + s * r ) add = [0] * (E + 1) for degree in range(E + 1 - offset): add[degree + offset] = dp[r][s][degree] # 頂点Nと現在の層の間に1本以上必要 # add *= q^s - 1 tmp = [(-value) % MOD for value in add] for degree in range(E + 1 - s): tmp[degree + s] += add[degree] if tmp[degree + s] >= MOD: tmp[degree + s] -= MOD add = tmp for degree in range(E + 1): answer_polynomial[degree] += add[degree] if answer_polynomial[degree] >= MOD: answer_polynomial[degree] -= MOD # [x^R] H(1+x) answer = 0 for degree in range(E + 1): answer += ( answer_polynomial[degree] * C.comb(degree, R) ) % MOD answer %= MOD print(answer) if __name__ == "__main__": solve()