#ifndef LOCAL #define FAST_IO #endif // ============ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; template using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64)x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64)x; return os; } #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; // ============ #ifdef DEBUGF #else #define DBG(x) (void)0 #endif // ============ // ============ // ============ #include #include #include namespace poly { using Mint = atcoder::modint998244353; using Poly = std::vector; Poly add(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] += g[i]; } return f; } Poly sub(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] -= g[i]; } return f; } Poly mul(const Poly &f, const Poly &g) { return atcoder::convolution(f, g); } void dft(Poly &f) { atcoder::internal::butterfly(f); } void idft(Poly &f) { atcoder::internal::butterfly_inv(f); int ctz = __builtin_ctz((int)f.size()); Mint inv = Mint::raw(Mint::mod() - (Mint::mod() >> ctz)); for (Mint &cf : f) { cf *= inv; } } } // namespace poly // ============ namespace poly { Poly fps_inv(const Poly &f, int sz = -1) { assert(!f.empty() && f[0] != Mint()); if (sz == -1) { sz = (int)f.size(); } assert(sz >= 0); Poly g(1, f[0].inv()); while ((int)g.size() < sz) { Poly fg; if (2 * g.size() <= f.size()) { fg = Poly(f.begin(), f.begin() + 2 * g.size()); } else { fg = f; fg.resize(2 * g.size()); } dft(fg); Poly dft_g = g; dft_g.resize(2 * g.size()); dft(dft_g); for (int i = 0; i < (int)dft_g.size(); ++i) { fg[i] *= dft_g[i]; } idft(fg); std::fill(fg.begin(), fg.begin() + g.size(), Mint()); dft(fg); for (int i = 0; i < (int)dft_g.size(); ++i) { fg[i] *= dft_g[i]; } idft(fg); g.resize(2 * g.size()); for (int i = (int)g.size() / 2; i < (int)g.size(); ++i) { g[i] = -fg[i]; } } g.resize(sz); return g; } } // namespace poly // ============ // ============ // ============ // ============ namespace poly { class Factorial { std::vector fac; std::vector ifac; public: Factorial() : fac(1, Mint::raw(1)), ifac(1, Mint::raw(1)) {} void reserve(int n) { int m = (int)fac.size() - 1; if (n <= m) { return; } fac.resize(n + 1); for (int i = m + 1; i <= n; ++i) { fac[i] = fac[i - 1] * Mint::raw(i); } ifac.resize(n + 1); ifac[n] = fac[n].inv(); for (int i = n - 1; i >= m; --i) { ifac[i] = ifac[i + 1] * Mint::raw(i + 1); } } Mint fact(int n) const { assert(n < (int)fac.size()); return fac[n]; } Mint inv_fact(int n) const { assert(n < (int)fac.size()); return ifac[n]; } Mint inv_n(int n) const { assert(n < (int)fac.size()); return ifac[n] * fac[n - 1]; } Mint binom(int n, int r) const { assert(n < (int)fac.size()); return fac[n] * ifac[r] * ifac[n - r]; } } factorial; } // namespace poly // ============ namespace poly { // for each 1 <= k <= max_k, compute 1^k + 2^k + ... + n^k std::vector enumerate_sums_of_powers(Mint x, int max_k) { assert(max_k >= 0); factorial.reserve(max_k + 1); x += Mint(1); std::vector f(max_k + 1), g(max_k + 1); Mint p = x; for (int i = 0; i <= max_k; ++i) { f[i] = p * factorial.inv_fact(i + 1); g[i] = factorial.inv_fact(i + 1); p *= x; } std::vector ret = mul(f, fps_inv(g)); ret.resize(max_k + 1); for (int i = 1; i <= max_k; ++i) { ret[i] *= factorial.fact(i); } ret[0] -= Mint(1); return ret; } } // namespace poly // ============ using namespace poly; int main() { i32 h, w, n, k; cin >> h >> w >> n >> k; factorial.reserve(n + 10); Mint sum; i32 h_max = min({(h + 1) / 2, h - k + 1, k}); i32 w_max = min({(w + 1) / 2, w - k + 1, k}); i32 h_max_cnt = h - 2 * (h_max - 1); i32 w_max_cnt = w - 2 * (w_max - 1); Mint tot = Mint(h - k + 1) * Mint(w - k + 1); Vec pow_tot(n + 1, Mint(1)), pow_h_max(n + 1, Mint(1)), pow_w_max(n + 1, Mint(1)); REP(i, n) { pow_tot[i + 1] = pow_tot[i] * tot; pow_h_max[i + 1] = pow_h_max[i] * Mint(h_max); pow_w_max[i + 1] = pow_w_max[i] * Mint(w_max); } Vec h_side = enumerate_sums_of_powers(Mint(h_max - 1), n); Vec w_side = enumerate_sums_of_powers(Mint(w_max - 1), n); DBG(h_side); { Mint cur_sum; REP(i, n + 1) { Mint tmp = factorial.binom(n, i) * pow_tot[i] * h_side[n - i] * w_side[n - i]; if ((n - i) % 2 == 0) { cur_sum += tmp; } else { cur_sum -= tmp; } } sum += cur_sum * Mint(4); } { Mint cur_sum; REP(i, n + 1) { Mint tmp = factorial.binom(n, i) * pow_tot[i] * h_side[n - i] * pow_w_max[n - i] * Mint(w_max_cnt); if ((n - i) % 2 == 0) { cur_sum += tmp; } else { cur_sum -= tmp; } } sum += cur_sum * Mint(2); } { Mint cur_sum; REP(i, n + 1) { Mint tmp = factorial.binom(n, i) * pow_tot[i] * w_side[n - i] * pow_h_max[n - i] * Mint(h_max_cnt); if ((n - i) % 2 == 0) { cur_sum += tmp; } else { cur_sum -= tmp; } } sum += cur_sum * Mint(2); } { Mint si = tot - Mint(h_max) * Mint(w_max); sum += si.pow(n) * Mint(h_max_cnt) * Mint(w_max_cnt); DBG(sum); } sum /= (Mint(h - k + 1) * Mint(w - k + 1)).pow(n); Mint ans = Mint(h) * Mint(w) - sum; cout << ans.val() << '\n'; }