from collections import deque import math import sys readline=sys.stdin.readline _fft_mod = 998244353 _fft_sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0) _fft_sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0) def _butterfly(a): n = len(a) h = (n - 1).bit_length() for ph in range(1, h + 1): w = 1 << (ph - 1) p = 1 << (h - ph) now = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] * now % _fft_mod a[i + offset] = (l + r) % _fft_mod a[i + offset + p] = (l - r) % _fft_mod now *= _fft_sum_e[(~s & -~s).bit_length() - 1] now %= _fft_mod def _butterfly_inv(a): n = len(a) h = (n - 1).bit_length() for ph in range(h, 0, -1): w = 1 << (ph - 1) p = 1 << (h - ph) inow = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] a[i + offset] = (l + r) % _fft_mod a[i + offset + p] = (l - r) * inow % _fft_mod inow *= _fft_sum_ie[(~s & -~s).bit_length() - 1] inow %= _fft_mod def _convolution_naive(a, b): n = len(a) m = len(b) ans = [0] * (n + m - 1) if n < m: for j in range(m): for i in range(n): ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod else: for i in range(n): for j in range(m): ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_mod return ans def _convolution_fft(a, b): a = a.copy() b = b.copy() n = len(a) m = len(b) z = 1 << (n + m - 2).bit_length() a += [0] * (z - n) _butterfly(a) b += [0] * (z - m) _butterfly(b) for i in range(z): a[i] = a[i] * b[i] % _fft_mod _butterfly_inv(a) a = a[:n + m - 1] iz = pow(z, _fft_mod - 2, _fft_mod) for i in range(n + m - 1): a[i] = a[i] * iz % _fft_mod return a def _convolution_square(a): a = a.copy() n = len(a) z = 1 << (2 * n - 2).bit_length() a += [0] * (z - n) _butterfly(a) for i in range(z): a[i] = a[i] * a[i] % _fft_mod _butterfly_inv(a) a = a[:2 * n - 1] iz = pow(z, _fft_mod - 2, _fft_mod) for i in range(2 * n - 1): a[i] = a[i] * iz % _fft_mod return a def convolution(a, b): """It calculates (+, x) convolution in mod 998244353. Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1], it calculates the array c of length n + m - 1, defined by > c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353. It returns an empty list if at least one of a and b are empty. Complexity ---------- > O(n log n), where n = len(a) + len(b). """ n = len(a) m = len(b) if n == 0 or m == 0: return [] if min(n, m) <= 100: return _convolution_naive(a, b) if a is b: return _convolution_square(a) return _convolution_fft(a, b) # Reference: https://opt-cp.com/fps-fast-algorithms/ def inv(a): """It calculates the inverse of formal power series in O(n log n) time, where n = len(a). """ n = len(a) assert n > 0 and a[0] != 0 res = [pow(a[0], _fft_mod - 2, _fft_mod)] m = 1 while m < n: f = a[:min(n, 2 * m)] g = res.copy() f += [0] * (2 * m - len(f)) _butterfly(f) g += [0] * (2 * m - len(g)) _butterfly(g) for i in range(2 * m): f[i] = f[i] * g[i] % _fft_mod _butterfly_inv(f) f = f[m:] + [0] * m _butterfly(f) for i in range(2 * m): f[i] = f[i] * g[i] % _fft_mod _butterfly_inv(f) f = f[:m] iz = pow(2 * m, _fft_mod - 2, _fft_mod) iz *= -iz iz %= _fft_mod for i in range(m): f[i] = f[i] * iz % _fft_mod res.extend(f) m *= 2 res = res[:n] return res def integ_inplace(a): n = len(a) assert n > 0 if n == 1: return [] a.pop() a.insert(0, 0) inv = [1, 1] for i in range(2, n): inv.append(-inv[_fft_mod%i] * (_fft_mod//i) % _fft_mod) a[i] = a[i] * inv[i] % _fft_mod def deriv_inplace(a): n = len(a) assert n > 0 for i in range(2, n): a[i] = a[i] * i % _fft_mod a.pop(0) a.append(0) def log(a): a = a.copy() n = len(a) assert n > 0 and a[0] == 1 a_inv = inv(a) deriv_inplace(a) a = convolution(a, a_inv)[:n] integ_inplace(a) return a def exp(a): a = a.copy() n = len(a) assert n > 0 and a[0] == 0 g = [1] a[0] = 1 h_drv = a.copy() deriv_inplace(h_drv) m = 1 while m < n: f_fft = a[:m] + [0] * m _butterfly(f_fft) if m > 1: _f = [f_fft[i] * g_fft[i] % _fft_mod for i in range(m)] _butterfly_inv(_f) _f = _f[m // 2:] + [0] * (m // 2) _butterfly(_f) for i in range(m): _f[i] = _f[i] * g_fft[i] % _fft_mod _butterfly_inv(_f) _f = _f[:m//2] iz = pow(m, _fft_mod - 2, _fft_mod) iz *= -iz iz %= _fft_mod for i in range(m//2): _f[i] = _f[i] * iz % _fft_mod g.extend(_f) t = a[:m] deriv_inplace(t) r = h_drv[:m - 1] r.append(0) _butterfly(r) for i in range(m): r[i] = r[i] * f_fft[i] % _fft_mod _butterfly_inv(r) im = pow(-m, _fft_mod - 2, _fft_mod) for i in range(m): r[i] = r[i] * im % _fft_mod for i in range(m): t[i] = (t[i] + r[i]) % _fft_mod t = [t[-1]] + t[:-1] t += [0] * m _butterfly(t) g_fft = g + [0] * (2 * m - len(g)) _butterfly(g_fft) for i in range(2 * m): t[i] = t[i] * g_fft[i] % _fft_mod _butterfly_inv(t) t = t[:m] i2m = pow(2 * m, _fft_mod - 2, _fft_mod) for i in range(m): t[i] = t[i] * i2m % _fft_mod v = a[m:min(n, 2 * m)] v += [0] * (m - len(v)) t = [0] * (m - 1) + t + [0] integ_inplace(t) for i in range(m): v[i] = (v[i] - t[m + i]) % _fft_mod v += [0] * m _butterfly(v) for i in range(2 * m): v[i] = v[i] * f_fft[i] % _fft_mod _butterfly_inv(v) v = v[:m] i2m = pow(2 * m, _fft_mod - 2, _fft_mod) for i in range(m): v[i] = v[i] * i2m % _fft_mod for i in range(min(n - m, m)): a[m + i] = v[i] m *= 2 return a def pow_fps(a, k): a = a.copy() n = len(a) l = 0 while l < len(a) and not a[l]: l += 1 if l * k >= n: return [0] * n ic = pow(a[l], _fft_mod - 2, _fft_mod) pc = pow(a[l], k, _fft_mod) a = log([a[i] * ic % _fft_mod for i in range(l, len(a))]) for i in range(len(a)): a[i] = a[i] * k % _fft_mod a = exp(a) for i in range(len(a)): a[i] = a[i] * pc % _fft_mod a = [0] * (l * k) + a[:n - l * k] return a def Extended_Euclid(n,m): stack=[] while m: stack.append((n,m)) n,m=m,n%m if n>=0: x,y=1,0 else: x,y=-1,0 for i in range(len(stack)-1,-1,-1): n,m=stack[i] x,y=y,x-(n//m)*y return x,y class MOD: def __init__(self,p,e=None): self.p=p self.e=e if self.e==None: mod=self.p else: mod=self.p**self.e def Pow(self,a,n): a%=mod if n>=0: return pow(a,n,mod) else: assert math.gcd(a,mod)==1 x=Extended_Euclid(a,mod)[0] return pow(x,-n,mod) def Build_Fact(self,N): assert N>=0 self.factorial=[1] if self.e==None: for i in range(1,N+1): self.factorial.append(self.factorial[-1]*i%mod) else: self.cnt=[0]*(N+1) for i in range(1,N+1): self.cnt[i]=self.cnt[i-1] ii=i while ii%self.p==0: ii//=self.p self.cnt[i]+=1 self.factorial.append(self.factorial[-1]*ii%mod) self.factorial_inve=[None]*(N+1) self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1) for i in range(N-1,-1,-1): ii=i+1 while ii%self.p==0: ii//=self.p self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%mod def Fact(self,N): if N<0: return 0 retu=self.factorial[N] if self.e!=None and self.cnt[N]: retu*=pow(self.p,self.cnt[N],mod)%mod retu%=mod return retu def Fact_Inve(self,N): if self.e!=None and self.cnt[N]: return None return self.factorial_inve[N] def Comb(self,N,K,divisible_count=False): if K<0 or K>N: return 0 retu=self.factorial[N]*self.factorial_inve[K]%mod*self.factorial_inve[N-K]%mod if self.e!=None: cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K] if divisible_count: return retu,cnt else: retu*=pow(self.p,cnt,mod) retu%=mod return retu N,M,K=map(int,readline().split()) mod=998244353 MD=MOD(mod) MD.Build_Fact(N) P=[None]*(N-K+1) for i in range(N-K+1): P[i]=MD.Fact_Inve(i+1) P=pow_fps(P,K) ans=0 for n in range(K,N+1): ans+=P[n-K]*MD.Pow(M,N-n)%mod*MD.Fact_Inve(N-n)%mod ans*=MD.Comb(M,K)*MD.Fact(N)%mod ans%=mod print(ans)