#line 1 "f.cpp" // https://atcoder.jp/contests/abc389/submissions/61843132 #include using namespace std; using ll=long long; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() #include using mint = atcoder::modint998244353; namespace po167{ template struct Binomial{ std::vector fact_vec, fact_inv_vec; void extend(int m = -1){ int n = fact_vec.size(); if (m == -1) m = n * 2; if (n >= m) return; fact_vec.resize(m); fact_inv_vec.resize(m); for (int i = n; i < m; i++){ fact_vec[i] = fact_vec[i - 1] * T(i); } fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1]; for (int i = m - 1; i > n; i--){ fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i); } } Binomial(int MAX = 0){ fact_vec.resize(1, T(1)); fact_inv_vec.resize(1, T(1)); extend(MAX + 1); } T fact(int i){ if (i < 0) return 0; while (int(fact_vec.size()) <= i) extend(); return fact_vec[i]; } T invfact(int i){ if (i < 0) return 0; while (int(fact_inv_vec.size()) <= i) extend(); return fact_inv_vec[i]; } T C(int a, int b){ if (a < b || b < 0) return 0; return fact(a) * invfact(b) * invfact(a - b); } }; } // https://ferin-tech.hatenablog.com/entry/2019/08/11/ラグランジュ補間 // x座標が相異なるn+1点(x_i,y_i)を通るn次以下の多項式f(x)を返す // O(n^2) #define REP(i, a) for (int i = 0; i < a; i++) #define FOR(i, a, b) rep(i, a, b) vector lagrange_interpolation(vector x, vector y) { const ll n = x.size() - 1; REP(i, n+1) { mint t = 1; REP(j, n+1) if(i != j) t *= x[i]-x[j]; y[i] /= t; } ll cur = 0, nxt = 1; vector> dp(2, vector(n+2)); dp[0][0] = -1 * x[0], dp[0][1] = 1; FOR(i, 1, n+1) { REP(j, n+2) { dp[nxt][j] = dp[cur][j] * -1 * x[i]; if(j >= 1) dp[nxt][j] += dp[cur][j-1]; } swap(nxt, cur); } vector xinv(n+1); REP(i, n+1) xinv[i] = x[i].inv(); vector ret(n+1); // f(x) REP(i, n+1) { if(y[i]==0) continue; // 0割り対策の場合分け if(x[i] == 0) { REP(j, n+1) ret[j] += dp[cur][j+1] * y[i]; } else { ret[0] -= dp[cur][0] * xinv[i] * y[i]; mint pre = -1 * dp[cur][0] * xinv[i]; FOR(j, 1, n+1) { ret[j] -= (dp[cur][j] - pre) * xinv[i] * y[i]; pre = -1 * (dp[cur][j] - pre) * xinv[i]; } } } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; po167::Binomial table(N); int D = N * (N - 1) / 2; vector ans(D + 1); rep(rp, 0, D + 1) { vector dp(N + 1, vector(N + 1, vector(N + 1))); dp[1][1][0] = 1; vector p2(N * N + 1, 1); rep(i, 0, N * N) p2[i + 1] = p2[i] * (rp + 2); vector p3(N, vector(N)); rep(i, 0, N){ p3[i][0] = 1; rep(j, 1, N){ p3[i][j] = p3[i][j - 1] * (p2[i] - 1); } } rep(sum, 1, N) rep(fr, 1, N) rep(a, 0, N) if(dp[sum][fr][a].val()){ rep(k, 1, N + 1 - sum) { mint tmp = dp[sum][fr][a] * table.C(N - sum - (a >= K ? 0 : 1), k - (a + 1 == K ? 1 : 0)); tmp *= p3[fr][k]; tmp *= p2[k * (k - 1) / 2]; dp[sum + k][k][a + 1] += tmp; } } rep(i, 0, N + 1) rep(j, 0, N + 1) rep(k, K, N + 1) if (dp[i][j][k].val()) { ans[rp] += dp[i][j][k] * p2[(N - i) * (N - i - 1) / 2]; } } vector X(D + 1); rep(i, 0, D + 1) X[i] = i + 1; auto res = lagrange_interpolation(X, ans); /*rep(i, N - 1, M + 1){ cout << res[i].val() << (i == M ? "\n" : " "); }*/ // for (auto x : res) cout << x.val() << " "; // cout << endl; cout << res[D - M].val() << "\n"; }