#include #include #include #include #include constexpr long long p = 998244353; long long ADD(long long a, long long b) { return a + b >= p ? a + b - p : a + b; } std::vector trim(std::vector a, int n) { std::vector b(n, 0); for (int i = 0; i < std::min(n, (int) a.size()); ++i) b[i] = a[i]; return b; } std::vector shift(std::vector a, int shift) { std::vector b(a.size(), 0); for (int i = 0; i < (int) a.size(); ++i) b[i] = (0 <= i - shift && i - shift < (int) a.size()) ? a[i - shift] : 0; return b; } long long pow_mod(long long a, long long n) { return n == 0 ? 1 : (pow_mod(a * a % p, n / 2) * (n % 2 == 1 ? a : 1)) % p; } long long modinv(long long a) { return pow_mod(a, p - 2); } std::vector add(std::vector a, std::vector b) { int n = std::max(a.size(), b.size()); std::vector c(n); a.resize(n); b.resize(n); for (int i = 0; i < n; ++i) c[i] = ADD(a[i], b[i]); return c; } std::vector subtract(std::vector a, std::vector b) { int n = std::max(a.size(), b.size()); std::vector c(n); a.resize(n); b.resize(n); for (int i = 0; i < n; ++i) c[i] = ADD(a[i], p - b[i]); return c; } void fft(std::vector &a, long long g) { int n = a.size(); g = pow_mod(g, (p - 1) / n); { int i = 0; for (int j = 0; j < n; ++j) { if (i > j) std::swap(a[i], a[j]); for (int k = n / 2; k > (i ^= k); k /= 2); } } for (int len = 1; len <= n / 2; len *= 2) { long mul = pow_mod(g, n / (2 * len)); for (int src = 0; src < n; src += 2 * len) { long long x = 1; for (int pos = src; pos < src + len; ++pos) { long long A = a[pos]; long long B = a[pos + len] * x % p; a[pos] = ADD(A, B); a[pos + len] = ADD(A, p - B); x = x * mul % p; } } } } std::vector mul(std::vector a, std::vector b) { long long g = 3; int n = 1; while (n < (int) (a.size() + b.size() - 1)) n *= 2; a.resize(n); b.resize(n); fft(a, g); fft(b, g); long long inv_n = modinv(n); for (int i = 0; i < n; ++i) a[i] = a[i] * b[i] % p * inv_n % p; fft(a, modinv(g)); return a; } std::vector mul(std::vector a, long long b) { int n = a.size(); std::vector c(n); for (int i = 0; i < n; ++i) c[i] = a[i] * b % p; return c; } std::vector finv(std::vector a) { int n = a.size(); std::vector b = {modinv(a[0])}; for (int len = 1; len < n; len *= 2) { b = subtract(mul(b, 2), trim(mul(mul(b, b), trim(a, 2 * len)), 2 * len)); } return b; } std::vector differentiate(std::vector a) { int n = a.size(); for (int i = 0; i + 1 < n; ++i) a[i] = (i + 1) * a[i + 1] % p; a[n - 1] = 0; return a; } std::vector integrate(std::vector a) { for (int i = a.size() - 1; i >= 1; --i) a[i] = modinv(i) * a[i - 1] % p; a[0] = 0; return a; } std::vector log(std::vector a) { assert(a[0] == 1); return integrate(mul(differentiate(a), finv(a))); } std::vector exp(std::vector a) { assert(a[0] == 0); int n = a.size(); std::vector b = {1}; for (int len = 1; len < n; len *= 2) { std::vector tmp = subtract(trim(a, 2 * len), log(trim(b, 2 * len))); ++tmp[0]; b = trim(mul(b, tmp), 2 * len); } return b; } std::vector pow(std::vector a, int n) { assert(n >= 1); int s = 0; while (s < (int) a.size() && a[s] == 0) ++s; if (s == (int) a.size()) return a; a = shift(a, -s); long long b = modinv(a[0]); for (int i = 0; i < (int) a.size(); ++i) a[i] = b * a[i] % p; a = log(a); for (int i = 0; i < (int) a.size(); ++i) a[i] = n % p * a[i] % p; a = exp(a); b = pow_mod(modinv(b), n % (p - 1)); for (int i = 0; i < (int) a.size(); ++i) a[i] = b * a[i] % p; a = shift(a, s * n); return a; } std::vector pow_exact(std::vector a, int n) { std::vector b = {1}; for (int i = 0; i < n; ++i) b = trim(mul(b, a), a.size()); return b; } void verify() { std::random_device seed_gen; std::mt19937_64 engine(seed_gen()); for (int t = 0; t < 100000; ++t) { int n = engine() % 100 + 1; int k = engine() % 100 + 1;; std::vector a(n); for (int i = 0; i < n; ++i) a[i] = engine() % p; std::vector u = pow(a, k); std::vector v = pow_exact(a, k); for (int i = 0; i < n; ++i) { assert(u[i] == v[i]); } std::cout << "case" << t << ":passed" << std::endl; } } const int MAX = (int) 2e5; long long fac[MAX]; long long ifac[MAX]; long long inv[MAX]; long long comb(int n, int k) { return fac[n] * ifac[n - k] % p * ifac[k] % p; } int main() { int N, M, K; std::cin >> N >> M >> K; fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1; for (int i = 2; i < MAX; ++i) { fac[i] = i * fac[i - 1] % p; inv[i] = p - inv[p % i] * (p / i) % p; ifac[i] = inv[i] * ifac[i - 1] % p; } std::vector f((int) 1e5 + 10); for (int i = 0; i < f.size(); ++i) f[i] = ifac[i]; f[0] = 0; f = pow(f, K); long long ans = 0; for (int i = K; i <= N; ++i) { ans += comb(N, i) * comb(M, K) % p * pow_mod(M, N - i) % p * f[i] % p * fac[i] % p; ans %= p; } std::cout << ans << std::endl; }