AtCoder Beginner Contest 167 - Colorful Blocks

There are N blocks arranged in a row. Let us paint these blocks.
We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.
Find the number of ways to paint the blocks under the following conditions:
 - For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.
 - There may be at most K pairs of adjacent blocks that are painted in the same color.
Since the count may be enormous, print it modulo 998244353.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 2 \times 10^5
 - 0 \leq K \leq N - 1

-----Input-----
Input is given from Standard Input in the following format:
N M K

-----Output-----
Print the answer.

-----Sample Input-----
3 2 1

-----Sample Output-----
6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.

Source: atcoder | Difficulty: MEDIUM


Solutions:
mod = 998244353
(N, M, K) = map(int, input().split())
f = 1
f_list = [1]
for m in range(1, N + 1):
	f *= m
	f %= mod
	f_list.append(f)
inv = pow(f, mod - 2, mod)
inv_list = [1] * (N + 1)
inv_list[N] = inv
for m in range(N, 1, -1):
	inv *= m
	inv %= mod
	inv_list[m - 1] = inv
ans = 0
for i in range(K + 1):
	color = pow(M - 1, N - 1 - i, mod)
	order = f_list[N - 1] * inv_list[i] * inv_list[N - i - 1] % mod
	ans += color * order * M % mod
	ans = ans % mod
print(ans % mod)


(N, M, K) = map(int, input().split())
MOD = 998244353
fact = [1]
rfact = [1]
for i in range(1, N + 1):
	fact.append(fact[i - 1] * i % MOD)
	rfact.append(pow(fact[i], MOD - 2, MOD))

def C(n, m):
	return fact[n] * rfact[m] * rfact[n - m] % MOD
res = 0
for k in range(K + 1):
	res = (res + C(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(res)


(n, m, k) = [int(x) for x in input().split()]
if m == 1:
	if k == n - 1:
		print(1)
	else:
		print(0)
	exit()
sumi = 0
mod = 998244353
prodi = pow(m - 1, n - 1, mod)
invi = pow(m - 1, mod - 2, mod)
for j in range(n - 1, n - 1 - k - 1, -1):
	sumi += prodi
	sumi %= mod
	prodi *= j
	prodi %= mod
	prodi *= pow(n - j, mod - 2, mod)
	prodi %= mod
	prodi *= invi
	prodi %= mod
sumi *= m
sumi %= mod
print(sumi)


(N, M, K) = map(int, input().split())
mod = 998244353
m = 2 * 10 ** 5 + 10
fac = [1] * m
ninv = [1] * m
finv = [1] * m
for i in range(2, m):
	fac[i] = fac[i - 1] * i % mod
	ninv[i] = -(mod // i) * ninv[mod % i] % mod
	finv[i] = finv[i - 1] * ninv[i] % mod

def comb(n, k):
	return fac[n] * finv[k] % mod * finv[n - k] % mod
ans = 0
for i in range(K + 1):
	ans += comb(N - 1, i) * M % mod * pow(M - 1, N - i - 1, mod)
	ans %= mod
print(ans)


def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % mod
mod = 998244353
(n, m, k) = map(int, input().split())
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, n):
	g1.append(g1[-1] * i % mod)
	inverse.append(-inverse[mod % i] * (mod // i) % mod)
	g2.append(g2[-1] * inverse[-1] % mod)
ans = m * (m - 1) ** (n - 1)
for i in range(k):
	ans += m * pow(m - 1, n - 2 - i, mod) * cmb(n - 1, i + 1, mod)
	ans %= mod
print(ans % mod)


def power_func(a, n, p):
	bi = str(format(n, 'b'))
	res = 1
	for i in range(len(bi)):
		res = res * res % p
		if bi[i] == '1':
			res = res * a % p
	return res
(n, m, k) = map(int, input().split())
w = 998244353
t = 0
c = 1
b = m * (m - 1) ** (n - 1) % w
g = power_func(m - 1, w - 2, w)
for i in range(k + 1):
	t += c * b
	t %= w
	if i < k:
		c *= n - 1 - i
		c *= power_func(i + 1, w - 2, w)
		c %= w
		b *= g
		b %= w
if m == 1 and k == n - 1:
	print(1)
else:
	print(t)


def mod_pow(a, n, mod):
	result = 1
	a_n = a
	while n > 0:
		if n & 1:
			result = result * a_n % mod
		a_n = a_n * a_n % mod
		n >>= 1
	return result

class ModCombination:

	def __init__(self, mod, n_max):
		self.mod = mod
		self.n_max = n_max
		self.facts = [1, 1]
		self.inverses = [None, 1]
		self.fact_inverses = [1, 1]
		for i in range(2, self.n_max + 1):
			self.facts.append(self.facts[i - 1] * i % self.mod)
			self.inverses.append(self.mod - self.inverses[self.mod % i] * (self.mod // i) % self.mod)
			self.fact_inverses.append(self.fact_inverses[i - 1] * self.inverses[i] % self.mod)

	def mod_combination(self, n, k):
		if k == 0:
			return 1
		if n == 0:
			return 0
		denominator = self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
		return self.facts[n] * denominator % self.mod
MOD = 998244353
(N, M, K) = list(map(int, input().split(' ')))
ans = 0
comb = ModCombination(mod=MOD, n_max=N)
for k in range(0, K + 1):
	ans += M * comb.mod_combination(N - 1, k) % MOD * mod_pow(M - 1, N - 1 - k, MOD)
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
s = m - 1
S = 1
ans = 0
fact = [1] * (n + 1)
fact_inv = [0] * (n + 1)
for i in range(1, n + 1):
	fact[i] = fact[i - 1] * i % mod
	fact_inv[i] = pow(fact[i], mod - 2, mod)
fact_inv[0] = fact_inv[1]
for t in range(n):
	if t >= n - k - 1:
		b = fact[n - 1] * fact_inv[t] * fact_inv[n - t - 1]
		ans += S * b % mod
	S = S * s % mod
print(m * ans % mod)


(n, m, k) = map(int, input().split())
(fact, factinv, mod) = ([1] * n, [1] * n, 998244353)
for i in range(2, n):
	fact[i] = fact[i - 1] * i % mod
factinv[n - 1] = pow(fact[n - 1], mod - 2, mod)
for i in range(n - 2, 0, -1):
	factinv[i] = factinv[i + 1] * (i + 1) % mod
ncr = lambda n, r: fact[n] * factinv[r] % mod * factinv[n - r] % mod
ans = pow(m, n, mod)
for i in range(k + 1, n):
	ans += mod - m * pow(m - 1, n - i - 1, mod) * ncr(n - 1, i) % mod
print(ans % mod)


from functools import reduce
mod = 998244353
(N, M, K) = map(int, input().split())
C = 1
ans = M * pow(M - 1, N - 1, mod) % mod
k = 1
while k <= K and k < N:
	C *= (N - k) * pow(k, mod - 2, mod)
	C %= mod
	a = C * M * pow(M - 1, N - k - 1, mod) % mod
	ans = (ans + a) % mod
	k += 1
print(ans)


import sys
readline = sys.stdin.readline

def main():
	(N, M, K) = map(int, readline().split())
	p = 998244353
	cnt = 0
	c = 1
	for i in range(K + 1):
		cnt += c * M * pow(M - 1, N - 1 - i, p)
		cnt %= p
		c *= (N - i - 1) * pow(i + 1, p - 2, p)
		c %= p
	print(cnt)
main()


F = 2 * 10 ** 5 + 5
mod = 998244353
fact = [1] * F
inv = [1] * F
for i in range(2, F):
	fact[i] = fact[i - 1] * i % mod
inv[F - 1] = pow(fact[F - 1], mod - 2, mod)
for i in range(F - 2, 1, -1):
	inv[i] = inv[i + 1] * (i + 1) % mod
(n, m, k) = map(int, input().split())

def comb(n, k):
	ans = fact[n] * inv[n - k] % mod
	return ans * inv[k] % mod
ans = 0
for i in range(k + 1):
	tmpans = m * comb(n - 1, i)
	tmpans = tmpans * pow(m - 1, n - i - 1, mod) % mod
	ans += tmpans
	ans %= mod
print(ans)


def main():
	MOD = 998244353
	if 'get_ipython' in globals():
		(n, m, k) = (60522, 114575, 7559)
	else:
		(n, m, k) = map(int, input().split())
	fac = [1] * (n + 1)
	inv = [1] * (n + 1)
	for i in range(n):
		fac[i + 1] = fac[i] * (i + 1) % MOD
		inv[i + 1] = pow(fac[i + 1], MOD - 2, MOD)

	def nCr(n, r):
		if 2 * r > n:
			nCr(n, n - r)
		return fac[n] * inv[r] * inv[n - r] % MOD
	ans = 0
	for i in range(k + 1):
		tmp = nCr(n - 1, i) * m * pow(m - 1, n - 1 - i, MOD)
		ans += tmp
		ans %= MOD
	print(ans)
main()


M = 998244353
(n, m, k) = map(int, input().split())
(p, c) = ([m], [1])
for i in range(1, n):
	p += [p[-1] * (m - 1) % M]
	c += [c[-1] * (n - i) * pow(i, M - 2, M) % M]
print(sum((p[n - i - 1] * c[i] for i in range(k + 1))) % M)


(N, M, K) = map(int, input().split())
mod = 998244353
factorial = [1 for i in range(N + 1)]
for i in range(1, N + 1):
	if i == 1:
		factorial[i] = 1
	else:
		factorial[i] = factorial[i - 1] * i % mod

def comb(n, k):
	return factorial[n] * pow(factorial[n - k] * factorial[k], -1, mod) % mod

def count(n, m, k):
	return m * comb(n - 1, k) * pow(m - 1, n - k - 1, mod) % mod
print(sum([count(N, M, i) for i in range(K + 1)]) % mod)


(n, m, k) = map(int, input().split())
mod = 998244353
fac = [1] * (n + 1)
per = [1] * (n + 1)
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
	per[i] = pow(fac[i], mod - 2, mod)

def nCk(n, k):
	return fac[n] * per[k] % mod * per[n - k] % mod
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - 1 - i, mod) % mod * nCk(n - 1, i) % mod
	ans %= mod
print(ans)


import sys
l = sys.stdin.readline().strip()
(N, M, K) = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N - 1) // 2 + 2):
	next = C[-1] * (N - i) * pow(i, mod - 2, mod)
	C.append(next % mod)
res = 0
for x in range(K + 1):
	crt = pow(M - 1, N - x - 1, mod) * M % mod
	crt %= mod
	idx = min(x, N - 1 - x)
	crt *= C[idx]
	crt %= mod
	res += crt
	res %= mod
print(res)


class Factorial:

	def __init__(self, mod=10 ** 9 + 7):
		self.mod = mod
		self._factorial = [1]
		self._size = 1
		self._factorial_inv = [1]
		self._size_inv = 1

	def __call__(self, n):
		return self.fact(n)

	def fact(self, n):
		if n >= self.mod:
			return 0
		self._make(n)
		return self._factorial[n]

	def _make(self, n):
		if n >= self.mod:
			n = self.mod
		if self._size < n + 1:
			for i in range(self._size, n + 1):
				self._factorial.append(self._factorial[i - 1] * i % self.mod)
			self._size = n + 1

	def fact_inv(self, n):
		if n >= self.mod:
			raise ValueError('Modinv is not exist! arg={}'.format(n))
		if self._size_inv < n + 1:
			self._factorial_inv += [-1] * (n + 1 - self._size_inv)
			self._size_inv = n + 1
		if self._factorial_inv[n] == -1:
			self._factorial_inv[n] = self.modinv(self.fact(n))
		return self._factorial_inv[n]

	def _make_inv(self, n, r=2):
		if n >= self.mod:
			n = self.mod - 1
		if self._size_inv < n + 1:
			self._factorial_inv += [-1] * (n + 1 - self._size_inv)
			self._size_inv = n + 1
		self._factorial_inv[n] = self.modinv(self.fact(n))
		for i in range(n, r, -1):
			self._factorial_inv[i - 1] = self._factorial_inv[i] * i % self.mod

	@staticmethod
	def xgcd(a, b):
		(x0, x1, y0, y1) = (0, 1, 1, 0)
		while a != 0:
			((q, a), b) = (divmod(b, a), a)
			(y0, y1) = (y1, y0 - q * y1)
			(x0, x1) = (x1, x0 - q * x1)
		return (b, x0, y0)

	def modinv(self, n):
		(g, x, _) = self.xgcd(n, self.mod)
		if g != 1:
			raise ValueError('Modinv is not exist! arg={}'.format(n))
		return x % self.mod

	def comb(self, n, r):
		if r > n:
			return 0
		t = self(n) * self.fact_inv(n - r) % self.mod
		return t * self.fact_inv(r) % self.mod

	def comb_(self, n, r):
		c = 1
		for i in range(1, r + 1):
			c *= (n - i + 1) * self.fact_inv(i)
			c %= self.mod
		return c

	def comb_with_repetition(self, n, r):
		t = self(n + r - 1) * self.fact_inv(n - 1) % self.mod
		return t * self.fact_inv(r) % self.mod

	def perm(self, n, r):
		if r > n:
			return 0
		return self(n) * self.fact_inv(n - r) % self.mod
(n, m, k) = map(int, input().split())
mod = 998244353
f = Factorial(mod)
f._make_inv(n - 1)
comb = f.comb
s = 0
for i in range(k + 1, n):
	t = comb(n - 1, i) * m % mod
	t = t * pow(m - 1, n - 1 - i, mod) % mod
	s = (s + t) % mod
ans = (pow(m, n, mod) - s) % mod
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
fac = [1 for i in range(N + 1)]
for n in range(1, N + 1):
	fac[n] = n * fac[n - 1] % MOD
fac_inv = [1 for i in range(n + 1)]
fac_inv[N] = pow(fac[N], MOD - 2, MOD)
for n in range(N - 1, -1, -1):
	fac_inv[n] = fac_inv[n + 1] * (n + 1) % MOD

def C(n, k):
	global MOD
	return fac[n] * fac_inv[k] * fac_inv[n - k] % MOD
print(sum([C(N - 1, b) * M * pow(M - 1, N - 1 - b, MOD) % MOD for b in range(K + 1)]) % MOD)


(N, M, K) = list(map(int, input().split()))
P = 998244353
(t, c) = (M * pow(~-M, ~-N, P), 1)
for k in range(1, K + 1):
	c = c * (N - k) * pow(k, P - 2, P) % P
	t = (t + M * c * pow(~-M, ~-N - k, P)) % P
print(t % P)


(N, M, K) = list(map(int, input().split()))
MOD = 998244353
if M == 1:
	print(1 if K == N - 1 else 0)
	return
MAXN = N + 5
fac = [1, 1] + [0] * MAXN
finv = [1, 1] + [0] * MAXN
inv = [0, 1] + [0] * MAXN
for i in range(2, MAXN + 2):
	fac[i] = fac[i - 1] * i % MOD
	inv[i] = -inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def comb(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD
cs = []
ms = [M * pow(M - 1, N - 1 - K, MOD) % MOD]
for i in range(K + 1):
	cs.append(comb(N - 1, i))
	if i:
		ms.append(ms[-1] * (M - 1) % MOD)
ans = 0
for (c, m) in zip(cs, ms[::-1]):
	ans += c * m
print(ans % MOD)


def Pow(a, n):
	if n == 0:
		return 1
	if n % 2 == 0:
		return Pow(a, n // 2) ** 2 % mod
	else:
		return Pow(a, n - 1) * a % mod
mod = 998244353
(N, M, K) = map(int, input().split())
x = [1] * N
for i in range(1, N):
	x[i] = Pow(i, mod - 2)
cmb = [1] * N
for i in range(N - 2):
	cmb[i + 1] = cmb[i] * (N - 1 - i) % mod * x[i + 1] % mod
ans = 0
for i in range(K + 1):
	num = Pow(M - 1, N - 1 - i)
	ans = (ans + M * num % mod * cmb[i] % mod) % mod
print(ans)


import math
(N, M, K) = list(map(int, input().split()))
MOD = 998244353

def getInvs(n, MOD):
	invs = [1] * (n + 1)
	for x in range(2, n + 1):
		invs[x] = -(MOD // x) * invs[MOD % x] % MOD
	return invs
invs = getInvs(N + 3, MOD)
num = M
nums = []
for i in reversed(list(range(1, N))):
	nums.append(num)
	num *= i * (M - 1)
	num *= invs[N - i]
	num %= MOD
nums.append(num)
nums.reverse()
ans = sum(nums[:K + 1])
ans %= MOD
print(ans)


import sys
readline = sys.stdin.readline
MOD = 998244353
(N, M, K) = map(int, readline().split())
f = [1]
for i in range(N):
	f.append(f[i] * (i + 1) % MOD)
f_inv = [1] * N
f_inv[N - 1] = pow(f[N - 1], MOD - 2, MOD)
for i in range(N - 1)[::-1]:
	f_inv[i] = f_inv[i + 1] * (i + 1) % MOD

def comb_mod(n, r, p):
	return f[n] * f_inv[r] * f_inv[n - r] % p
ans = 0
for i in range(K + 1):
	ans = (ans + M * pow(M - 1, N - 1 - i, MOD) * comb_mod(N - 1, i, MOD)) % MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
nCi = [1]
for i in range(n):
	next = nCi[i] * (n - 1 - i) * pow(i + 1, mod - 2, mod)
	next %= mod
	nCi.append(next)
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - i - 1, mod) * nCi[i]
	ans %= mod
print(ans)


def main():
	(N, M, K) = map(int, input().split())
	MOD = 998244353
	fac = [0] * 10 ** 6
	inv = [0] * 10 ** 6
	finv = [0] * 10 ** 6

	def COM_init():
		fac[0] = 1
		fac[1] = 1
		inv[1] = 1
		finv[0] = 1
		finv[1] = 1
		for i in range(2, 2 * 10 ** 5 + 10):
			fac[i] = fac[i - 1] * i % MOD
			inv[i] = -inv[MOD % i] * (MOD // i) % MOD
			finv[i] = finv[i - 1] * inv[i] % MOD

	def COM(n, k):
		if n < k:
			return 0
		if n < 0 or k < 0:
			return 0
		return fac[n] * (finv[n - k] * finv[k] % MOD) % MOD
	COM_init()
	ans = 0
	for i in range(K + 1):
		ans += M * pow(M - 1, N - i - 1, MOD) * COM(N - 1, i)
		ans %= MOD
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, m, k) = map(int, input().split())
mod = 998244353
fact = [1] * (n + 1)
ifact = [1] * (n + 1)
for i in range(n):
	fact[i + 1] = fact[i] * (i + 1) % mod
	ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)

def comb(x, y):
	if y < 0 or y > x:
		return 0
	return fact[x] * ifact[x - y] * ifact[y] % mod
mm = [1]
for _ in range(n + 1):
	mm.append(mm[-1] * (m - 1) % mod)
ans = 0
for i in range(k + 1):
	ans += m * comb(n - 1, i) * mm[n - 1 - i]
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
factorials = []
current = 1
for i in range(n):
	factorials.append(current)
	current = (i + 1) * current % 998244353
inverselist = []
for i in range(n):
	inverselist.append(pow(factorials[i], 998244351, 998244353))
ans = 0
for i in range(0, k + 1):
	ans = (ans + m * pow(m - 1, n - i - 1, 998244353) * factorials[n - 1] * inverselist[i] * inverselist[n - 1 - i]) % 998244353
print(ans)


mod = 998244353
(n, m, k) = map(int, input().split(' '))
F = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	F[i] = F[i - 1] * i % mod
I = [1 for i in range(n + 1)]
for i in range(2, n + 1):
	I[i] = (mod - int(mod / i)) * I[mod % i] % mod
for i in range(2, n + 1):
	I[i] = I[i] * I[i - 1] % mod

def binom(n, k):
	return F[n] * I[k] % mod * I[n - k] % mod
pw = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	pw[i] = pw[i - 1] * (m - 1) % mod
ans = 0
for i in range(k + 1):
	sz = n - i
	ans += binom(n - 1, i) * m % mod * pw[sz - 1] % mod
	ans %= mod
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
ans = 0
NCi = 1
for i in range(0, K + 1, 1):
	ans = (ans + M * pow(M - 1, N - 1 - i, MOD) * NCi) % MOD
	NCi = NCi * (N - 1 - i) * pow(i + 1, MOD - 2, MOD) % MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
res = 0
pat = 1
for i in range(0, k + 1):
	res += pat * pow(m - 1, n - 1 - i, mod)
	pat *= (n - 1 - i) * pow(i + 1, mod - 2, mod)
	pat %= mod
print(m * res % mod)


(n, m, k) = map(int, input().split())
mod = 998244353
f = [1] * (n + 1)
revf = [1] * (n + 1)
for i in range(2, n + 1):
	f[i] = f[i - 1] * i % mod
revf[n] = pow(f[n], mod - 2, mod)
for i in range(n - 1, 0, -1):
	revf[i] = revf[i + 1] * (i + 1) % mod

def C(x, y):
	return f[x] * revf[y] * revf[x - y] % mod
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - i - 1, mod) * C(n - 1, i)
	ans %= mod
print(ans)


def main():
	(n, m, k) = map(int, input().split())
	mod = 998244353
	comb = 1
	c = 0
	for i in range(k + 1):
		if i > 0:
			comb = comb * (n - i) * pow(i, mod - 2, mod) % mod
		c = (c + m * comb * pow(m - 1, n - 1 - i, mod)) % mod
	print(c)
main()


import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal

class Scanner:

	@staticmethod
	def int():
		return int(sys.stdin.readline().rstrip())

	@staticmethod
	def string():
		return sys.stdin.readline().rstrip()

	@staticmethod
	def map_int():
		return [int(x) for x in Scanner.string().split()]

	@staticmethod
	def string_list(n):
		return [Scanner.string() for i in range(n)]

	@staticmethod
	def int_list_list(n):
		return [Scanner.map_int() for i in range(n)]

	@staticmethod
	def int_cols_list(n):
		return [Scanner.int() for i in range(n)]
MOD = 998244353
INF = int(1000000000000000.0)

def solve():
	MAX = 200010
	fac = [0] * MAX
	finv = [0] * MAX
	inv = [0] * MAX
	fac[0] = fac[1] = 1
	finv[0] = finv[1] = 1
	inv[1] = 1
	for i in range(2, MAX):
		fac[i] = fac[i - 1] * i % MOD
		inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
		finv[i] = finv[i - 1] * inv[i] % MOD
	(N, M, K) = Scanner.map_int()
	ans = 0
	for k in range(K + 1):
		tmp = M * pow(M - 1, N - 1 - k, MOD)
		tmp %= MOD
		cmb = fac[N - 1] * (finv[k] * finv[N - 1 - k] % MOD) % MOD
		tmp *= cmb
		tmp %= MOD
		ans += tmp
		ans %= MOD
	print(ans)

def main():
	solve()

def __starting_point():
	main()
__starting_point()


(n, m, k) = map(int, input().split())
mod = 998244353
ans = 0
fact = [1, 1]
finv = [1, 1]
for i in range(2, n + 1):
	fact += [fact[i - 1] * i % mod]
	finv += [pow(fact[i], mod - 2, mod)]

def comb(n, k, mod):
	return fact[n] * finv[k] * finv[n - k] % mod
for i in range(0, k + 1):
	ans += m * pow(m - 1, n - i - 1, mod) * comb(n - 1, i, mod)
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
inv = [0, 1]
for i in range(2, N):
	inv.append(-inv[mod % i] * (mod // i) % mod)
if N == 1:
	print(M)
	return
m = [1]
s = 1
for _ in range(N - 1):
	s = s * (M - 1) % mod
	m.append(s)
ncombi = [1]
c = 1
for k in range(K):
	c = c * (N - 1 - k) * inv[k + 1]
	c %= mod
	ncombi.append(c)
ans = 0
for k in range(K + 1):
	ans = ans + m[-k - 1] * ncombi[k]
	ans %= mod
ans = ans * M % mod
print(ans)


import sys, math, itertools
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 998244353

def I():
	return int(input())

def F():
	return float(input())

def S():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LS():
	return input().split()

def factorialMod(n, p):
	fact = [0] * (n + 1)
	fact[0] = fact[1] = 1
	factinv = [0] * (n + 1)
	factinv[0] = factinv[1] = 1
	inv = [0] * (n + 1)
	inv[1] = 1
	for i in range(2, n + 1):
		fact[i] = fact[i - 1] * i % p
		inv[i] = -inv[p % i] * (p // i) % p
		factinv[i] = factinv[i - 1] * inv[i] % p
	return (fact, factinv)

def combMod(n, r, fact, factinv, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p

def resolve():
	(N, M, K) = LI()
	ans = 0
	(fact, factinv) = factorialMod(N, MOD)
	for i in range(K + 1):
		ans += combMod(N - 1, i, fact, factinv, MOD) * M * pow(M - 1, N - 1 - i, MOD)
		ans %= MOD
	print(ans)

def __starting_point():
	resolve()
__starting_point()


(n, m, k) = map(int, input().split())
(mod1, mod2) = (10 ** 9 + 7, 998244353)
mod = mod2
MAX = n - 1
fact = [1] * (MAX + 1)
inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
	fact[i] = i * fact[i - 1] % mod
inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(MAX, 1, -1):
	inv[i - 1] = inv[i] * i % mod

def comb(x, y):
	return fact[x] * inv[y] % mod * inv[x - y] % mod if x >= y >= 0 else 0
ans = 0
cor = pow(m - 1, n - 1 - k, mod)
for i in range(k, -1, -1):
	ans = (ans + comb(n - 1, i) * cor) % mod
	cor = cor * (m - 1) % mod
print(m * ans % mod)


import numpy as np
MAX = 200002
MOD = 998244353
fac = np.zeros(MAX)
finv = np.zeros(MAX)
inv = np.zeros(MAX)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
	fac[i] = int(fac[i - 1]) * i % MOD
	inv[i] = MOD - int(inv[MOD % i]) * (MOD // i) % MOD
	finv[i] = int(finv[i - 1]) * int(inv[i]) % MOD

def COM(N, K):
	return int(fac[N]) * (int(finv[K]) * int(finv[N - K]) % MOD) % MOD

def resolve():
	(N, M, K) = map(int, input().split())
	ans = 0
	for i in range(K + 1):
		ans_k = M * COM(N - 1, i)
		ans_k = ans_k * pow(M - 1, N - 1 - i, MOD) % MOD
		ans = (ans + ans_k) % MOD
	print(ans)
resolve()


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy
import heapq
m = 2 * 10 ** 5
mod = 998244353
(N, M, K) = map(int, input().split())
ans = 0
A = [0] * (m + 5)
A_inv = [0] * (m + 5)
inv = [0] * (m + 5)
A[0] = A[1] = 1
A_inv[0] = A_inv[1] = 1
inv[1] = 1
for j in range(2, m + 5):
	A[j] = A[j - 1] * j % mod
	inv[j] = mod - inv[mod % j] * (mod // j) % mod
	A_inv[j] = A_inv[j - 1] * inv[j] % mod

def cmb(n, k, mod):
	return A[n] * (A_inv[k] * A_inv[n - k] % mod) % mod
for i in range(K + 1):
	ans = (ans + cmb(N - 1, i, mod) * M % mod * pow(M - 1, N - 1 - i, mod) % mod) % mod
print(ans)


(N, M, K) = map(int, input().split())
m = 998244353
result = 0
n = 1
k = 1
for i in range(K + 1):
	result += n * pow(k, m - 2, m) * pow(M - 1, N - 1 - i, m)
	result %= m
	n *= N - 1 - i
	n %= m
	k *= i + 1
	k %= m
result *= M
result %= m
print(result)


(N, M, K) = map(int, input().split())
mod = 998244353
facm = 200500
fac = [1] * facm
facinv = [1] * facm
for i in range(facm - 1):
	fac[i + 1] = fac[i] * (i + 1) % mod
	facinv[i + 1] = facinv[i] * pow(i + 1, -1, mod) % mod

def nCk(n, k):
	return fac[n] * facinv[k] * facinv[n - k] % mod
ans = 0
for i in range(K + 1):
	ans = (ans + nCk(N - 1, i) * pow(M - 1, N - i - 1, mod) * M) % mod
print(ans)


MOD = 998244353
lim = 200000
inv_t = [-1 for i in range(lim + 1)]
factrial = [-1 for i in range(lim + 1)]
factrial_inv = [-1 for i in range(lim + 1)]

def set_inv(max=lim):
	inv_t[0] = 0
	for i in range(1, max):
		inv_t[i] == mod_inv(i)

def mod_inv(x, mod=MOD):
	(y, u, v, _x) = (mod, 1, 0, x)
	while y:
		t = _x // y
		_x -= t * y
		(_x, y) = (y, _x)
		u -= t * v
		(u, v) = (v, u)
	u %= mod
	if u < 0:
		u += mod
	return u

def mod_pow(a, n, mod=MOD):
	res = 1
	while n:
		if n & 1:
			res = res * a % mod
		a = a * a % mod
		n >>= 1
	return res

def set_factrial(max=lim, mod=MOD):
	c = 1
	factrial[0] = factrial_inv[0] = 1
	for i in range(1, max):
		c *= i
		c %= mod
		factrial[i] = c
		factrial_inv[i] = mod_inv(c, mod)

def comb(a, b, mod=MOD):
	if factrial[0] == -1:
		set_factrial()
	return factrial[a] * factrial_inv[b] * factrial_inv[a - b] % mod
(n, m, k) = [int(_) for _ in input().split()]
ans = 0
for i in range(k + 1):
	ans += m * comb(n - 1, i) * mod_pow(m - 1, n - 1 - i)
	ans %= MOD
print(ans)


import math
from operator import mul
from functools import reduce
(n, m, k) = map(int, input().split())
mod = 998244353

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n + 1):
	fact.append(fact[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	factinv.append(factinv[-1] * inv[-1] % mod)
ans = 0
for i in range(k + 1):
	ans += m * cmb(n - 1, i, mod) * pow(m - 1, n - 1 - i, mod) % mod
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
fact = [0] * 220000
invfact = [0] * 220000
fact[0] = 1
for i in range(1, 220000):
	fact[i] = fact[i - 1] * i % mod
invfact[220000 - 1] = pow(fact[220000 - 1], mod - 2, mod)
for i in range(220000 - 2, -1, -1):
	invfact[i] = invfact[i + 1] * (i + 1) % mod

def nCk(n, k):
	if k < 0 or n < k:
		return 0
	return fact[n] * invfact[k] * invfact[n - k] % mod
ans = 0
for i in range(K + 1):
	ans += M * pow(M - 1, N - i - 1, mod) * nCk(N - 1, i) % mod
print(ans % mod)


(n, m, k) = map(int, input().split())
mod = 998244353
if m == 1:
	if k == n - 1:
		print(1)
	else:
		print(0)
	exit()

def inv(x):
	y = 1
	while x != 1:
		y *= mod // x + 1
		y %= mod
		x -= mod % x
	return y
now = int(m)
for _ in range(n - 1):
	now *= m - 1
	now %= mod
ans = int(now)
for i in range(k):
	now *= inv(m - 1)
	now *= n - 1 - i
	now *= inv(i + 1)
	now %= mod
	ans += now
	ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
p = 998244353
comb = 1
res = 0
for n in range(K + 1):
	res = (res + comb * M * pow(M - 1, N - 1 - n, p)) % p
	comb = comb * (N - 1 - n) * pow(n + 1, p - 2, p) % p
print(res)


MOD = 998244353
(n, m, k) = map(int, input().split())
fact = [0 for _ in range(n)]
invfact = [0 for _ in range(n)]
fact[0] = 1
for i in range(1, n):
	fact[i] = fact[i - 1] * i % MOD
invfact[n - 1] = pow(fact[n - 1], MOD - 2, MOD)
for i in range(n - 2, -1, -1):
	invfact[i] = invfact[i + 1] * (i + 1) % MOD

def nCk(n, k):
	if k < 0 or n < k:
		return 0
	else:
		return fact[n] * invfact[k] * invfact[n - k] % MOD
ans = 0
for i in range(0, k + 1):
	ans += m * pow(m - 1, n - i - 1, MOD) * nCk(n - 1, i) % MOD
print(ans % MOD)


(N, M, K) = map(int, input().split(' '))
mod = 998244353
ans = 0
fac = [0] * (N + 1)
inv = [0] * (N + 1)
finv = [0] * (N + 1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N + 1):
	fac[i] = fac[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	finv[i] = finv[i - 1] * inv[i] % mod

def COM(n, k):
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
for i in range(K + 1):
	ans += M * pow(M - 1, N - 1 - i, mod) * COM(N - 1, i)
	ans %= mod
print(ans)


mod = 998244353
(n, m, k) = map(int, input().split())
framod = [0] * (2 * 10 ** 5 + 1)
framod[0] = 1

def xframod(n, mod, a=1):
	for i in range(1, n + 1):
		a = a * i % mod
		framod[i] = a
xframod(2 * 10 ** 5, mod)

def combmod(n, k, mod):
	a = framod[n]
	b = framod[k]
	c = framod[n - k]
	return a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod) % mod
ans = 0
for i in range(0, k + 1):
	tmp = combmod(n - 1, i, mod)
	tmp *= m * pow(m - 1, n - 1 - i, mod)
	tmp %= mod
	ans += tmp
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
ans = m * pow(m - 1, n - 1, mod)
ans %= mod
if k == 0:
	print(ans)
	exit()
lst = [1] + [1]
for i in range(2, n + 10):
	lst.append(lst[-1] * i % mod)

def combinations(n, r):
	xxx = lst[n]
	xxx *= pow(lst[n - r], mod - 2, mod)
	xxx %= mod
	xxx *= pow(lst[r], mod - 2, mod)
	xxx %= mod
	return xxx
for i in range(1, k + 1):
	ans += m * pow(m - 1, n - 1 - i, mod) * combinations(n - 1, i) % mod
	ans %= mod
print(ans)


MOD = 998244353
MAXN = 200000 + 10
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, MAXN + 1):
	g1.append(g1[-1] * i % MOD)
	inverse.append(-inverse[MOD % i] * (MOD // i) % MOD)
	g2.append(g2[-1] * inverse[-1] % MOD)

def comb(n, r):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % MOD
(N, M, K) = map(int, input().split())
ans = 0
for i in range(K + 1):
	tmp = M * pow(M - 1, N - 1 - i, MOD)
	ans += comb(N - 1, i) * tmp
	ans %= MOD
print(ans)


import math

def main():
	(N, M, K) = list(map(int, input().split()))
	MOD = 998244353
	fact = [1] * (N + 1)
	factinv = [1] * (N + 1)
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % MOD
		factinv[i] = pow(fact[i], MOD - 2, MOD)

	def comb(n, k):
		return fact[n] * factinv[k] * factinv[n - k] % MOD
	ans = 0
	for k in range(K + 1):
		ans += comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD) % MOD
	print(ans % MOD)
main()


MOD = 998244353
(N, M, K) = map(int, input().split())
Mp = [0] * (K + 1)
nck = [0] * (K + 1)
nck[0] = 1
ans = 0
comb = 1
for i in range(K + 1):
	t = 1
	t *= M
	t %= MOD
	t *= pow(M - 1, N - 1 - i, MOD)
	t %= MOD
	t *= comb
	t %= MOD
	ans += t
	ans %= MOD
	comb *= N - 1 - i
	comb %= MOD
	comb *= pow(i + 1, MOD - 2, MOD)
	comb %= MOD
print(ans)


def main():
	(n, m, k) = list(map(int, input().split()))
	mod = 998244353

	def cmb(n, r, mod):
		if r < 0 or r > n:
			return 0
		r = min(r, n - r)
		return g1[n] * g2[r] * g2[n - r] % mod
	N = 10 ** 6
	g1 = [1, 1]
	g2 = [1, 1]
	inverse = [0, 1]
	for i in range(2, N + 1):
		g1.append(g1[-1] * i % mod)
		inverse.append(-inverse[mod % i] * (mod // i) % mod)
		g2.append(g2[-1] * inverse[-1] % mod)
	s = 0
	for i in range(k + 1):
		s += cmb(n - 1, i, mod) * m * pow(m - 1, n - 1 - i, mod) % mod
	print(s % mod)

def __starting_point():
	main()
__starting_point()


(N, M, K) = map(int, input().split())
mod = 998244353
ans = 0
facts = [1 for i in range(N + 1)]
invs = [1 for i in range(N + 1)]

def inv(x):
	return pow(x, mod - 2, mod)
for i in range(1, N + 1):
	facts[i] = facts[i - 1] * i % mod
	invs[i] = inv(facts[i])

def comb(n, r):
	return facts[n] * invs[r] * invs[n - r] % mod
for i in range(K + 1):
	d = M * pow(M - 1, N - i - 1, mod) * comb(N - 1, i)
	ans = (ans + d % mod) % mod
print(ans)


(N, M, K) = map(int, input().split())
m = 998244353
ans = M * pow(M - 1, N - 1, m) % m
alpha = 1
for k in range(1, K + 1):
	alpha = alpha * (N - k) * pow(k, m - 2, m) % m
	ans = (ans + M * alpha * pow(M - 1, N - k - 1, m)) % m
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
fac = [1] * N
for i in range(1, N):
	fac[i] = fac[i - 1] * i % MOD
pow_mmm = [1] * N
for i in range(1, N):
	pow_mmm[i] = pow_mmm[i - 1] * (M - 1) % MOD
ans = 0
for i in range(K + 1):
	t = M * pow_mmm[N - 1 - i] % MOD
	comb = fac[N - 1] * pow(fac[N - 1 - i], MOD - 2, MOD) * pow(fac[i], MOD - 2, MOD) % MOD
	t = t * comb % MOD
	ans = (ans + t) % MOD
print(ans)


mod = 998244353
(n, m, k) = map(int, input().split())
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
inv[n] = pow(fac[n], mod - 2, mod)
for i in range(n, 0, -1):
	inv[i - 1] = inv[i] * i % mod

def nCr(n, r):
	if r < 1:
		return 1
	return fac[n] * inv[r] % mod * inv[n - r] % mod
ans = 0
for i in range(k + 1):
	tmp = m * pow(m - 1, n - i - 1, mod) * nCr(n - 1, i) % mod
	ans = (ans + tmp) % mod
print(ans)


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import heapq
import decimal
import queue
INF = 10 ** 16
MOD = 998244353

def ni():
	return int(sys.stdin.readline())

def ns():
	return list(map(int, sys.stdin.readline().split()))

def na():
	return list(map(int, sys.stdin.readline().split()))

class ModCombination:

	def __init__(self, maxN, MOD):
		self._maxN = maxN
		self._MOD = MOD
		self.facts = [1]
		self.invs = [1] * (self._maxN + 1)
		fact = 1
		for i in range(1, self._maxN + 1):
			fact *= i
			fact %= self._MOD
			self.facts.append(fact)
		inv = pow(fact, self._MOD - 2, self._MOD)
		self.invs[self._maxN] = inv
		for i in range(self._maxN, 1, -1):
			inv *= i
			inv %= self._MOD
			self.invs[i - 1] = inv

	def nCr(self, n, r):
		return self.facts[n] * self.invs[r] * self.invs[n - r] % self._MOD

def main():
	(n, m, k) = ns()
	mc = ModCombination(n, MOD)
	result = 0
	for ki in range(k + 1):
		ans = 1
		ans *= m % MOD
		ans *= pow(m - 1, n - 1 - ki, MOD)
		ans %= MOD
		ans *= mc.nCr(n - 1, ki)
		ans %= MOD
		result += ans
		result %= MOD
	print(result)

def __starting_point():
	main()
__starting_point()


(N, M, K) = list(map(int, input().split()))
MOD = 998244353
ans = 0
comb = 1
for k in range(K + 1):
	ans += M * comb * pow(M - 1, N - k - 1, MOD)
	ans %= MOD
	comb *= (N - k - 1) * pow(k + 1, MOD - 2, MOD)
	comb %= MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
f = [0] * (n + 1)
p = [0] * (n + 1)
f[0] = 1
p[0] = 1
for i in range(1, n + 1):
	f[i] = f[i - 1] * i % mod
	p[i] = pow(f[i], mod - 2, mod)

def nCk(n, k):
	return f[n] * p[k] * p[n - k] % mod
ans = 0
for i in range(k + 1):
	if i == 0:
		ans += m * pow(m - 1, n - 1 - i, mod)
	else:
		ans += m * pow(m - 1, n - 1 - i, mod) * nCk(n - 1, i)
	ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
mod = 998244353

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
p = 998244353
N1 = 2 * 10 ** 5 + 10
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N1 + 1):
	fact.append(fact[-1] * i % p)
	inv.append(-inv[p % i] * (p // i) % p)
	factinv.append(factinv[-1] * inv[-1] % p)
ans = 0
mem = 1
mem = pow(M - 1, N - K - 1, p)
for i in range(K, -1, -1):
	wk = M * mem
	wk %= p
	wk *= cmb(N - 1, i, p)
	mem *= M - 1
	mem %= p
	ans += wk
	ans %= p
print(ans)


M = 998244353
(n, m, k) = map(int, input().split())
a = 0
c = 1
for i in range(k + 1):
	a += c * m * pow(m - 1, n - i - 1, M)
	c = c * (n - i - 1) * pow(i + 1, M - 2, M) % M
print(a % M)


(n, m, k) = map(int, input().split())
MOD = 998244353
ans = 0
c = 1
for i in range(k + 1):
	ans = (ans + m * pow(m - 1, n - i - 1, MOD) * c) % MOD
	c = c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD) % MOD
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
factorials = [1]
fact_invs = [1]
for i in range(1, N + 1):
	factorials.append(factorials[-1] * i % MOD)
	fact_invs.append(pow(factorials[-1], MOD - 2, MOD))
ans = 0
for k in range(K + 1):
	tmp = factorials[N - 1]
	tmp *= fact_invs[k]
	tmp %= MOD
	tmp *= fact_invs[N - 1 - k]
	tmp %= MOD
	tmp *= M * pow(M - 1, N - 1 - k, MOD)
	ans += tmp
	ans %= MOD
print(ans)


mod = 998244353
MAX = 2 * 10 ** 5 + 100
inv = [0] * (MAX + 1)
inv[1] = 1
for i in range(2, MAX + 1):
	inv[i] = -(mod // i) * inv[mod % i] % mod
g1 = [1, 1]
g2 = [1, 1]
for i in range(2, MAX + 1):
	num_1 = g1[-1] * i % mod
	g1.append(num_1)
	g2.append(g2[-1] * inv[i] % mod)

def cmb(n, r):
	return g1[n] * g2[r] * g2[n - r] % mod
(N, M, K) = map(int, input().split())
ans = 0
for i in range(K + 1):
	num = M * pow(M - 1, N - i - 1, mod) % mod
	num = num * cmb(N - 1, i) % mod
	ans = (ans + num) % mod
print(ans)


import sys
(N, M, K) = list(map(int, input().rstrip().split()))
if M == 1 and K == N - 1:
	print(1)
	return
elif M == 1 and K < N - 1:
	print(0)
	return
mod = 998244353
a = M * pow(M - 1, N - 1, mod)
inv_M1 = pow(M - 1, mod - 2, mod)
comb = 1
ans = 0
for i in range(K + 1):
	ans += comb * a
	ans %= mod
	a *= inv_M1
	a %= mod
	inv_i1 = pow(i + 1, mod - 2, mod)
	comb *= (N - 1 - i) * inv_i1
	comb %= mod
print(ans)


def pre_combi1(n, p):
	fact = [1] * (n + 1)
	factinv = [1] * (n + 1)
	inv = [0] * (n + 1)
	inv[1] = 1
	for i in range(2, n + 1):
		fact[i] = fact[i - 1] * i % p
		inv[i] = -inv[p % i] * (p // i) % p
		factinv[i] = factinv[i - 1] * inv[i] % p
	return (fact, factinv)

def combi1(n, r, p, fact, factinv):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
p = 998244353
(fact, finv) = pre_combi1(2 * 10 ** 5 + 1, p)
(n, m, k) = map(int, input().split())
ans = 0
dup = [0] * n
dup[0] = 1
for j in range(1, n):
	dup[j] = dup[j - 1] * (m - 1) % p
for i in range(k + 1):
	ans += m * combi1(n - 1, i, p, fact, finv) * dup[n - i - 1]
	ans %= p
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n + 1):
	g1.append(g1[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	g2.append(g2[-1] * inv[-1] % mod)

def comb(n, r):
	if r < 0 or r > n:
		return 0
	return g1[n] * g2[r] * g2[n - r] % mod
ans = 0
for i in range(k + 1):
	ans += comb(n - 1, i) * m * pow(m - 1, n - i - 1, mod)
	ans %= mod
print(ans)


mod = 998244353
(N, M, K) = map(int, input().split())
list_size = 2 * 10 ** 5 + 4
f_list = [1] * list_size
f_r_list = [1] * list_size
for i in range(list_size - 1):
	f_list[i + 1] = f_list[i] * (i + 1) % mod
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
for i in range(list_size - 2, -1, -1):
	f_r_list[i] = f_r_list[i + 1] * (i + 1) % mod

def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return f_list[n] * f_r_list[n - r] * f_r_list[r] % mod
ans = 0
for k in range(K + 1):
	ans += comb(N - 1, k, mod) * M * pow(M - 1, N - k - 1, mod) % mod
ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
mod = 998244353
com = 1
ans = 0
for i in range(K + 1):
	ans += M * com * pow(M - 1, N - 1 - i, mod)
	ans %= mod
	com *= (N - 1 - i) * pow(i + 1, mod - 2, mod)
	com %= mod
print(ans)


(n, m, k) = map(int, input().split())
MOD = 998244353
ans = 0
p = 1
px = 1
py = 1
for i in range(k + 1):
	x = m * pow(m - 1, n - 1 - i, MOD) % MOD
	ans += p * x % MOD
	ans %= MOD
	px *= pow(i + 1, MOD - 2, MOD)
	py *= n - i - 1
	px %= MOD
	py %= MOD
	p = px * py % MOD
print(ans)


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

class Combination:

	def __init__(self, n, p):
		self.n = n
		self.p = p
		self.note = [1, 1]
		self.noteinv = [1, 1]
		self.inv = [0, 1]
		self.calc()

	def calc(self):
		for i in range(2, self.n + 1):
			self.note.append(self.note[-1] * i % self.p)
			self.inv.append(-self.inv[self.p % i] * (self.p // i) % self.p)
			self.noteinv.append(self.noteinv[-1] * self.inv[-1] % self.p)

	def nCr(self, n, r):
		n = self.n
		if r < 0 or n < r:
			return 0
		r = min(r, n - r)
		return self.note[n] * self.noteinv[r] * self.noteinv[n - r] % self.p

def Main():
	(n, m, k) = read_ints()
	p = 998244353
	modm = [1]
	for _ in range(1, n):
		modm.append(modm[-1] * (m - 1) % p)
	cmb = Combination(n - 1, p)
	ans = 0
	for i in range(k + 1):
		ans += cmb.nCr(n - 1, i) * m * modm[n - 1 - i] % p
		ans %= p
	print(ans)

def __starting_point():
	Main()
__starting_point()


(n, m, k) = list(map(int, input().split()))
p = 998244353

def prepare(n):
	fact = [1, 1]
	factinv = [1, 1]
	inv = [0, 1]
	for i in range(2, n + 1):
		fact.append(fact[-1] * i % p)
		inv.append(-inv[p % i] * (p // i) % p)
		factinv.append(factinv[-1] * inv[-1] % p)
	return (fact, factinv)

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	return f[n] * v[r] * v[n - r] % p
(f, v) = prepare(n)
ans = 0
for i in range(k + 1):
	a = cmb(n - 1, i, p) * m * pow(m - 1, n - i - 1, p) % p
	ans += a
	ans %= p
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
MAXN = N + 5
fac = [1, 1] + [0] * MAXN
finv = [1, 1] + [0] * MAXN
inv = [0, 1] + [0] * MAXN
for i in range(2, MAXN + 2):
	fac[i] = fac[i - 1] * i % MOD
	inv[i] = -inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def comb(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD
ans = 0
for i in range(K + 1):
	if i == N:
		break
	n = N - i
	ans += M * pow(M - 1, n - 1, MOD) * comb(N - 1, i)
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
ans = 0
mod = 998244353
p = [0 for i in range(n)]
p[0] = 1
for i in range(n - 1):
	p[i + 1] = p[i] * (i + 2) % mod
p.append(1)
for i in range(k + 1):
	u = pow(m - 1, n - 1 - i, mod)
	s = p[n - 2] * pow(p[i - 1], mod - 2, mod) * pow(p[n - i - 2], mod - 2, mod)
	ans = (ans + m * u * s) % mod
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
ans = 0
fact = [1] * (N + 1)
factinv = [1] * (N + 1)
for i in range(N):
	fact[i + 1] = fact[i] * (i + 1) % MOD
	factinv[i + 1] = pow(fact[i + 1], MOD - 2, MOD)

def nCk(n, k):
	return fact[n] * factinv[n - k] * factinv[k] % MOD

def solve(k):
	r = M * pow(M - 1, N - 1 - k, MOD) * nCk(N - 1, k)
	return r
for k in range(K + 1):
	ans += solve(k)
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
n = N
fac = [1] * (n + 1)
rev = [1] * (n + 1)
for i in range(1, n + 1):
	fac[i] = i * fac[i - 1] % MOD
	rev[i] = pow(fac[i], MOD - 2, MOD)
comb = lambda a, b: fac[a] * rev[a - b] * rev[b] % MOD
ans = 0
for i in range(K + 1):
	ans += comb(N - 1, N - 1 - i) * M * pow(M - 1, N - 1 - i, MOD)
	ans %= MOD
print(ans)


import numpy as np
(N, M, K) = [int(_) for _ in input().split()]
mod = 998244353

class Factorial:

	def __init__(self, max_fact, mod):
		f = [1] * (max_fact + 1)
		for idx in range(2, max_fact + 1):
			f[idx] = f[idx - 1] * idx
			f[idx] %= mod
		if mod > max_fact:
			fi = [pow(f[-1], mod - 2, mod)]
			for idx in range(max_fact, 0, -1):
				fi += [fi[-1] * idx % mod]
			fi = fi[::-1]
		else:
			fi = [pow(n, mod - 2, mod) for n in f]
		self.mod = mod
		self.f = f
		self.fi = fi

	def factorial(self, n):
		return self.f[n]

	def factorial_inverse(self, n):
		return self.fi[n]

	def combination(self, n, r):
		f = self.f
		fi = self.fi
		return f[n] * fi[r] * fi[n - r] % self.mod

	def permutation(self, n, r):
		return self.f[n] * self.fi[n - r] % self.mod

	def homogeneous_product(self, n, r):
		f = self.f
		fi = self.fi
		return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod
max_fact = N
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
ans = 0
for r in range(K + 1):
	ans += comb(N - 1, r) * M * pow(M - 1, N - r - 1, mod)
	ans %= mod
print(ans)


p = 998244353
(N, M, K) = map(int, input().split())
power = [0 for i in range(N)]
power[0] = 1
for i in range(1, N):
	power[i] = power[i - 1] * (M - 1) % p
ans = M * power[N - 1]
ans %= p
pre_compute = [0 for i in range(K + 1)]
num = den = 1
for i in range(1, K + 1):
	num *= N - i
	den *= i
	num %= p
	den %= p
	pre_compute[i] = num * pow(den, p - 2, p) % p
for i in range(1, K + 1):
	ans += M * power[N - 1 - i] * pre_compute[i]
	ans %= p
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
mod = 998244353
(N, M, K) = mapint()
pos = {}
neg = {}
pos[0] = 1
neg[0] = 1
for i in range(1, N + 1):
	pos[i] = i * pos[i - 1] % mod
	neg[i] = pow(pos[i], mod - 2, mod)
ans = 0
for i in range(K + 1):
	ans += M * pow(M - 1, N - i - 1, mod) * pos[N - 1] * neg[i] * neg[N - i - 1]
	ans %= mod
print(ans)


C = 998244353
(N, M, K) = map(int, input().split())
U = max(N + 1, K)
F = [0] * U
G = [0] * U
F[0] = 1
for i in range(1, U):
	F[i] = F[i - 1] * i % C
G[i] = pow(F[-1], C - 2, C)
for j in range(U - 2, -1, -1):
	G[j] = G[j + 1] * (j + 1) % C

def nCr(n, r):
	if r < 0 or n < r:
		return 0
	else:
		return F[n] * G[r] * G[n - r]
S = 0
for k in range(0, K + 1):
	S = (S + M * pow(M - 1, N - k - 1, C) * nCr(N - 1, k)) % C
print(S % C)


(n, m, k) = map(int, input().split())
wari = 998244353
basum = 0
for i in range(k + 1):
	if i == 0:
		kumiawase = 1
	else:
		kumiawase = kumiawase * (n - i) * pow(i, wari - 2, wari)
		kumiawase %= wari
	basum += m * pow(m - 1, n - i - 1, wari) * kumiawase
	basum %= wari
print(basum)


def main():
	MAX = 998244353
	(n, m, k) = map(int, input().split())
	cnt = 0
	cmb = 1
	for ik in range(k + 1):
		ncp = m * pow(m - 1, n - ik - 1, MAX)
		ncp %= MAX
		if ik == 0:
			cmb = 1
		else:
			cmb *= (n - ik) * pow(ik, MAX - 2, MAX)
		cmb %= MAX
		cnt += ncp * cmb
		cnt %= MAX
	print(cnt % MAX)
main()


from sys import stdin
input = stdin.readline
(N, M, K) = map(int, input().split())
mod = 998244353
C = [-1] * (N + 1)

def comb(n, r):
	if r > n - r:
		C[r] = C[n - r]
	if r == 0:
		C[0] = 1
	if C[r] != -1:
		return C[r]
	else:
		C[r] = comb(n, r - 1) * (n + 1 - r) * pow(r, mod - 2, mod)
		C[r] %= mod
		return C[r]
ans = 0
for i in range(K + 1):
	ans += M * pow(M - 1, N - 1 - i, mod) * comb(N - 1, i)
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
MOD = 998244353
frac = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
	frac[i] = i * frac[i - 1] % MOD
inv[n] = pow(frac[n], MOD - 2, MOD)
for i in range(n - 1, 0, -1):
	inv[i] = inv[i + 1] * (i + 1) % MOD

def nCr(n, r):
	res = frac[n] * inv[n - r] % MOD
	res = res * inv[r] % MOD
	return res
ans = 0
for i in range(k + 1):
	num_pair_block = i + 1
	num_seg = n - i
	ans += m * pow(m - 1, num_seg - 1, MOD) * nCr(n - 1, i) % MOD
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
ans = 0
mod = 998244353

def modinv(a, mod=998244353):
	return pow(a, mod - 2, mod)
fac = [0] * (N + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, N + 1):
	fac[i] = fac[i - 1] * i % mod

def combi(n, r, mod=998244353):
	return fac[n] * modinv(fac[r]) % mod * modinv(fac[n - r]) % mod
z = M * pow(M - 1, N - K - 1, mod) % mod
for k in range(K, -1, -1):
	c = z * combi(N - 1, k) % mod
	ans += c
	z = z * (M - 1) % mod
print(ans % mod)


def solve(*args: str) -> str:
	(n, m, k) = map(int, args[0].split())
	mod = 998244353
	if m == 1 and n - 1 == k:
		return str(1)
	ncr = 1
	p = m * pow(m - 1, n - 1, mod) % mod
	ret = p
	inv = pow(m - 1, mod - 2, mod)
	for i in range(1, k + 1):
		ncr = ncr * (n - i) * pow(i, mod - 2, mod) % mod
		p = p * inv % mod
		ret += p * ncr % mod
	return str(ret % mod)
print(solve(*open(0).read().splitlines()))


(n, m, k) = map(int, input().split())
p = 998244353
(fct, inv) = ([1], [1])
for i in range(1, n):
	fct.append(fct[-1] * i % p)
	inv.append(inv[-1] * pow(i, p - 2, p) % p)
ans = 0
for i in range(k + 1):
	cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
	ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)


(n, m, k) = list(map(int, input().split()))
MOD = 998244353
fact = [1] * (n + 1)
factinv = [1] * (n + 1)
for i in range(n):
	fact[i + 1] = fact[i] * (i + 1) % MOD
	factinv[i + 1] = pow(fact[i + 1], MOD - 2, MOD)

def nCk(n, k):
	return fact[n] * factinv[n - k] * factinv[k] % MOD
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - 1 - i, MOD) * nCk(n - 1, i) % MOD
print(ans % MOD)


def main():
	(n, m, k) = map(int, input().split())
	f = [1]
	p = 998244353
	for i in range(1, n):
		f.append(f[-1] * i % p)
	ans = 0

	def nCk(n, k):
		return f[n] * pow(f[n - k], p - 2, p) * pow(f[k], p - 2, p) % p
	for i in range(k + 1):
		ans += m * nCk(n - 1, i) * pow(m - 1, n - 1 - i, p) % p
	print(ans % p)

def __starting_point():
	main()
__starting_point()


class Combination:

	def __init__(self, max_n, _mod):
		self.mod = _mod
		self.fac = [0 for _ in range(max_n + 10)]
		self.finv = [0 for _ in range(max_n + 10)]
		self.inv = [0 for _ in range(max_n + 10)]
		(self.fac[0], self.fac[1]) = (1, 1)
		(self.finv[0], self.finv[1]) = (1, 1)
		self.inv[1] = 1
		for i in range(2, max_n + 10):
			self.fac[i] = self.fac[i - 1] * i % self.mod
			self.inv[i] = self.mod
			self.inv[i] -= self.inv[self.mod % i] * (self.mod // i) % self.mod
			self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod

	def mod_comb(self, n, k):
		if n < k or n < 0 or k < 0:
			return 0
		res = self.fac[n] * (self.finv[k] * self.finv[n - k] % self.mod)
		res %= self.mod
		return res

def main():
	mod = 998244353
	(N, M, K) = map(int, input().split())
	comb = Combination(N, mod)
	ans = 0
	for i in range(K + 1):
		add_v = M * pow(M - 1, N - i - 1, mod) % mod
		add_v = add_v * comb.mod_comb(N - 1, i) % mod
		ans = (ans + add_v) % mod
	print(ans)
main()


(N, M, K) = map(int, input().split())
mod = 998244353
FACT = [1]
for i in range(1, 2 * 10 ** 5 + 1):
	FACT.append(FACT[-1] * i % mod)
FACT_INV = [pow(FACT[-1], mod - 2, mod)]
for i in range(2 * 10 ** 5, 0, -1):
	FACT_INV.append(FACT_INV[-1] * i % mod)
FACT_INV.reverse()

def Combi(a, b):
	if 0 <= b <= a:
		return FACT[a] * FACT_INV[b] * FACT_INV[a - b] % mod
	else:
		return 0
ANS = 0
for i in range(K + 1):
	ANS += Combi(N - 1, i) * pow(M - 1, N - 1 - i, mod)
	ANS %= mod
print(ANS * M % mod)


(N, M, K) = map(int, input().split())
MOD = 998244353
fact = [0] * (N + 1)
inv = [0] * (N + 1)
fact[0] = fact[1] = 1
inv[1] = 1
for i in range(2, N + 1):
	fact[i] = fact[i - 1] * i % MOD
	inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD

def main():
	if N == 1:
		print(M)
		return
	num = M
	nums = [M]
	for i in reversed(range(1, N)):
		num *= i * (M - 1)
		num *= inv[N - i]
		num %= MOD
		nums.append(num)
	nums.reverse()
	print(sum(nums[:K + 1]) % MOD)

def __starting_point():
	main()
__starting_point()


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import heapq
import decimal
import queue
import numpy as np
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 998244353
ni = lambda : int(sys.stdin.readline())
ns = lambda : list(map(int, sys.stdin.readline().split()))
na = lambda : list(map(int, sys.stdin.readline().split()))

def main():

	def fast_pow(num, kata, mod):
		if kata == 0:
			return 1
		res = 1
		while kata > 0:
			if kata & 1 == 1:
				res = res * num % mod
			num = num * num % mod
			kata >>= 1
		return res

	def prepare(n, MOD):
		f = 1
		factorials = [1]
		for m in range(1, n + 1):
			f *= m
			f %= MOD
			factorials.append(f)
		inv = pow(f, MOD - 2, MOD)
		invs = [1] * (n + 1)
		invs[n] = inv
		for m in range(n, 1, -1):
			inv *= m
			inv %= MOD
			invs[m - 1] = inv
		return (factorials, invs)
	(n, m, k) = ns()
	(p, i) = prepare(n, MOD)
	result = 0
	for ki in range(k + 1):
		ans = 1
		ans *= m % MOD
		ans *= fast_pow(m - 1, n - 1 - ki, MOD)
		ans %= MOD
		ans *= p[n - 1] * i[ki] * i[n - 1 - ki]
		ans %= MOD
		result += ans
		result %= MOD
	print(result)

def __starting_point():
	main()
__starting_point()


(N, M, K) = map(int, input().split())
mod = 998244353
l_lis = [1]
r_lis = [1]
(l, r) = (1, 1)
for j in range(K + 1):
	l = l * (j + 1) % mod
	r = r * (N - j - 1) % mod
	l_lis.append(l)
	r_lis.append(r)

def comb(a, b):
	global mod
	l = l_lis[b]
	r = r_lis[b]
	return r * pow(l, mod - 2, mod) % mod
ans = 0
for i in range(K + 1):
	ans += comb(N - 1, i) * M * pow(M - 1, N - 1 - i, mod) % mod
print(ans % mod)


import math
(n, m, k) = map(int, input().split())
num = 210000
mod = 998244353
fact = [0] * num
invfact = [0] * num
fact[0] = 1
for i in range(1, num):
	fact[i] = fact[i - 1] * i % mod
invfact[num - 1] = pow(fact[num - 1], mod - 2, mod)
for i in range(num - 2, -1, -1):
	invfact[i] = invfact[i + 1] * (i + 1) % mod

def nck(n, k):
	if n < k or k < 0:
		return 0
	return fact[n] * invfact[k] * invfact[n - k]
ans = 0
for i in range(k + 1):
	ans += nck(n - 1, i) * m * pow(m - 1, n - i - 1, mod) % mod
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
if M == 1 and K == N - 1:
	print(1)
	exit()
A = [0] * (K + 1)
A[0] = M * pow(M - 1, N - 1, mod) % mod
for i in range(K):
	A[i + 1] = A[i] * (N - 1 - i) * pow(M - 1, mod - 2, mod) * pow(i + 1, mod - 2, mod) % mod
ans = A[0]
for i in range(K):
	ans = (ans + A[i + 1]) % mod
print(ans)


M = 998244353
(n, m, k) = map(int, input().split())
k = n - k - 1
p = n - 1
F = [1]
for i in range(n + 1091):
	F.append(F[-1] * (i + 1) % M)

def C(k, n):
	return F[n] * pow(F[k] * F[n - k], M - 2, M)
ans = pow(m, n, M)
for x in range(k):
	ans -= C(x, p) * m * pow(m - 1, x, M)
	ans %= M
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
l = [0] * N
l[0] = 1
for i in range(1, N):
	l[i] = l[i - 1] * (M - 1)
	l[i] = l[i] % MOD
fact = [0] * N
fact[0] = 1
for i in range(1, N):
	fact[i] = fact[i - 1] * i % MOD
fact_inv = [0] * N
for i in range(N):
	fact_inv[i] = pow(fact[i], MOD - 2, MOD)
ans = 0
for i in range(K + 1):
	ans += M * l[N - 1 - i] % MOD * fact[N - 1] * fact_inv[i] % MOD * fact_inv[N - 1 - i] % MOD
	ans %= MOD
print(ans % MOD)


def combi(y, x, p=998244353):
	s = fac[y]
	t = fac[x]
	u = fac[y - x]
	ans = s * pow(t, p - 2, p) * pow(u, p - 2, p) % p
	return ans
(N, M, K) = map(int, input().split())
p = 998244353
fac = [1, 1]
for i in range(2, N + 1):
	fac.append(fac[-1] * i % p)
ans = 0
for i in range(0, K + 1):
	R = M % p * pow(M - 1, N - 1 - i, p) % p
	L = combi(N - 1, i)
	ans = (ans + R * L % p) % p
print(ans)


MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
	fact[i] = fact[i - 1] * i % MOD

def comb(n, r):
	return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
(N, M, K) = map(int, input().split())
total = 0
for k in range(K + 1):
	total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)


(n, m, k) = map(int, input().split())
mod = 998244353
ma = [1]
for i in range(1, k + 1):
	mad = ma[-1] * (n - i) * pow(i, mod - 2, mod)
	ma.append(mad)
	ma[-1] %= mod
ans = 0
for i in range(k + 1):
	ans += ma[i] * m * pow(m - 1, n - i - 1, mod)
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353

def inv(a):
	return pow(a, MOD - 2, MOD)
fact = [0, 1]
for i in range(2, N + 1):
	fact.append(fact[-1] * i % MOD)

def choose(n, r):
	if r == 0 or r == n:
		return 1
	else:
		return fact[n] * inv(fact[r]) * inv(fact[n - r]) % MOD
exp = [1]
for i in range(1, N):
	exp.append(exp[-1] * (M - 1) % MOD)
ans = 0
for i in range(K + 1):
	ans += M * choose(N - 1, i) * exp[N - 1 - i] % MOD
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
MOD = 998244353

def inv(x, MOD):
	return pow(x, MOD - 2, MOD)
c = [0 for _ in range(n)]
c[0] = 1
for i in range(1, n):
	c[i] = c[i - 1] * (n - i)
	c[i] *= inv(i, MOD)
	c[i] %= MOD
ans = sum([m * c[i] * pow(m - 1, n - 1 - i, MOD) for i in range(k + 1)]) % MOD
print(ans)


(n, m, k) = map(int, input().split())

def cmb(n, r, mod):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % mod
mod = 998244353
N = 3 * 10 ** 5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
	fact.append(fact[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	factinv.append(factinv[-1] * inv[-1] % mod)
ans = 0
for i in range(min(n, k + 1)):
	ans = (ans + cmb(n - 1, i, mod) * m * pow(m - 1, n - i - 1, mod)) % mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
f = [1]
for i in range(1, N + 1):
	f.append(f[-1] * i % mod)

def comb(n, r):
	return f[n] * (pow(f[r], mod - 2, mod) * pow(f[n - r], mod - 2, mod) % mod) % mod
ans = 0
for i in range(K + 1):
	k = M * pow(M - 1, N - 1 - i, mod) % mod * comb(N - 1, i)
	k %= mod
	ans += k
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
b = str(bin(mod - 2))[2:]
blis = []
for _ in range(len(b)):
	if b[-_ - 1] == '1':
		blis.append(_)

def modinv(a):
	if a == 1:
		return 1
	else:
		res = 1
		n = len(b)
		li = []
		for _ in range(n):
			li.append(a % mod)
			a = a * a % mod
		for item in blis:
			res = res * li[item] % mod
		return res
if N == 1:
	print(M)
	return
m = [1]
s = 1
for _ in range(N - 1):
	s = s * (M - 1) % mod
	m.append(s)
ncombi = [1]
c = 1
for k in range(K):
	c = c * (N - 1 - k) * modinv(k + 1)
	c %= mod
	ncombi.append(c)
ans = 0
for k in range(K + 1):
	ans = ans + m[-k - 1] * ncombi[k]
	ans %= mod
ans = ans * M % mod
print(ans)


def comb(n, r, m):
	if 2 * r > n:
		r = n - r
	(nume, deno) = (1, 1)
	for i in range(1, r + 1):
		nume *= n - i + 1
		nume %= m
		deno *= i
		deno %= m
	return nume * pow(deno, m - 2, m) % m

def main():
	(N, M, K) = list(map(int, input().split()))
	mod = 998244353
	(ans, comb_r) = (pow(M - 1, N - 1, mod), 1)
	for r in range(1, K + 1):
		comb_r = comb_r * (N - r) * pow(r, mod - 2, mod) % mod
		ans = (ans + comb_r * pow(M - 1, N - r - 1, mod)) % mod
	ans = ans * M % mod
	print(ans)

def __starting_point():
	main()
__starting_point()


fact = [1 for _ in range(200000)]
inv = [1 for _ in range(200000)]
fact_inv = [1 for _ in range(200000)]
mod = 998244353
for i in range(2, 200000):
	fact[i] = fact[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	fact_inv[i] = fact_inv[i - 1] * inv[i] % mod
(N, M, K) = map(int, input().split())
ans = 0
a = pow(M - 1, N - 1 - K, mod)
for i in range(K, -1, -1):
	ans += fact[N - 1] * fact_inv[i] * fact_inv[N - 1 - i] * M * a
	ans = ans % mod
	a *= M - 1
	a = a % mod
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
mod = 998244353
memo = [-1] * 10 ** 6
memo[0] = 1

def fact(n):
	if memo[n] != -1:
		return memo[n]
	else:
		res = n * fact(n - 1) % mod
		memo[n] = res
		return res

def comb(n, k):
	return fact(n) * pow(fact(k), mod - 2, mod) * pow(fact(n - k), mod - 2, mod) % mod
(N, M, K) = map(int, input().split())
ans = 0
for k in range(K + 1):
	ans += M * pow(M - 1, N - k - 1, mod) * comb(N - 1, k)
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
p = 998244353
factorial = [1]
counter = 0
for i in range(1, N + 1):
	factorial.append(factorial[i - 1] * i % p)
for k in range(K + 1):
	counter += factorial[N - 1] * pow(factorial[k], p - 2, p) * pow(factorial[N - k - 1], p - 2, p) * M * pow(M - 1, N - 1 - k, p)
print(counter % p)


MOD = 998244353
(n, m, k) = map(int, input().split())
c = 1
cnt = 0
for x in range(k + 1):
	cnt += c * m * pow(m - 1, n - 1 - x, MOD)
	cnt %= MOD
	c *= (n - x - 1) * pow(x + 1, MOD - 2, MOD)
	c %= MOD
print(cnt)


(n, m, k) = map(int, input().split())
mod = 998244353
if m == 1:
	print(0 if k != n - 1 else 1)
	exit()
fact = [1] * (n - 1 + 1)
inv = [1] * (n - 1 + 1)
for i in range(2, n - 1 + 1):
	fact[i] = i * fact[i - 1] % mod
inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(n - 1, 1, -1):
	inv[i - 1] = inv[i] * i % mod

def comb(x, y):
	return fact[x] * inv[y] % mod * inv[x - y] % mod
ans = 0
po = pow(m - 1, n - 1, mod) * m % mod
ue = fact[n - 1]
iii = pow(m - 1, mod - 2, mod) % mod
for i in range(k + 1):
	ans += comb(n - 1, i) * po % mod
	po *= iii
	po %= mod
print(ans % mod)


(n, m, k) = map(int, input().split())
mod = 998244353
MAX_N = n + 5
fac = [1, 1] + [0] * MAX_N
finv = [1, 1] + [0] * MAX_N
inv = [0, 1] + [0] * MAX_N
for i in range(2, MAX_N):
	fac[i] = fac[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	finv[i] = finv[i - 1] * inv[i] % mod

def nCk(n, k):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
ans = 0
for i in range(k + 1):
	ans += nCk(n - 1, i) * m * pow(m - 1, n - i - 1, mod)
	ans %= mod
print(ans)


class Combination:

	def __init__(self, n, mod):
		self.fact = [1]
		for i in range(1, n + 1):
			self.fact.append(self.fact[-1] * i % mod)
		self.inv_fact = [0] * (n + 1)
		self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
		for i in reversed(list(range(n))):
			self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
		self.mod = mod

	def factorial(self, k):
		return self.fact[k]

	def inverse_factorial(self, k):
		return self.inv_fact[k]

	def permutation(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[k - r] % self.mod

	def combination(self, k, r):
		if k < r:
			return 0
		return self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r] % self.mod

	def combination_large(self, k, r):
		if k < r:
			return 0
		res = 1
		for l in range(r):
			res *= k - l
			res %= self.mod
		return res * self.inv_fact[r] % self.mod
(n, m, k) = list(map(int, input().split()))
mod = 998244353
cmb = Combination(10 ** 6, mod)
ans = 0
for i in range(k + 1):
	ans += m * cmb.combination(n - 1, i) * pow(m - 1, n - 1 - i, mod)
	ans %= mod
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
combination_N_1_ = [1]
for k in range(1, K + 1):
	tmp = combination_N_1_[-1] * (N - k) * pow(k, MOD - 2, MOD)
	tmp %= MOD
	combination_N_1_.append(tmp)
counter = 0
for i in range(K + 1):
	counter += pow(M - 1, N - i - 1, MOD) * M * combination_N_1_[i]
	counter %= MOD
print(counter)


def combs_mod(n, k, mod):
	inv = [1] * (k + 1)
	for i in range(1, k + 1):
		inv[i] = pow(i, mod - 2, mod)
	ans = [1] * (k + 1)
	for i in range(1, k + 1):
		ans[i] = ans[i - 1] * (n + 1 - i) * inv[i] % mod
	return ans

def solve():
	ans = 0
	mod = 998244353
	(N, M, K) = map(int, input().split())
	lis = combs_mod(N - 1, K, mod)
	for i in range(K + 1):
		ans += M * lis[i] * pow(M - 1, N - 1 - i, mod)
		ans %= mod
	return ans
print(solve())


(n, m, k) = map(int, input().split())
g = 998244353
r = 1
p = pow(m - 1, n - 1, g)
for i in range(1, k + 1):
	r = r * (n - i) * pow(i, g - 2, g) % g
	p = (p + r * pow(m - 1, n - 1 - i, g)) % g
print(m * p % g)


M = 998244353
(n, m, K) = map(int, input().split())
ans = 0
c = 1
for k in range(K + 1):
	ans += c * m * pow(m - 1, n - k - 1, M)
	c *= (n - k - 1) * pow(k + 1, M - 2, M)
	ans %= M
	c %= M
print(ans)


(N, M, K) = map(int, input().split())
fac = [1]
mod = 998244353
for i in range(1, N + 1):
	fac.append(fac[i - 1] * i % mod)
ifac = [None] * (N + 1)
ifac[-1] = pow(fac[N], mod - 2, mod)
for i in range(N, 0, -1):
	ifac[i - 1] = ifac[i] * i % mod
ans = 0
for k in range(K + 1):
	t = M * fac[N - 1] % mod
	t = t * ifac[N - 1 - k] % mod
	t = t * ifac[k] % mod
	t = t * pow(M - 1, N - 1 - k, mod)
	t %= mod
	ans = (ans + t) % mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
facs = [1] * N
invs = [1] * N
nfac = 1
for i in range(1, N):
	nfac = nfac * i % mod
	facs[i] = nfac
	invs[i] = pow(facs[i], mod - 2, mod)
s = 0
for i in range(K + 1):
	d = facs[N - 1] * invs[i] * invs[N - 1 - i] * M * pow(M - 1, N - 1 - i, mod) % mod
	s = (s + d) % mod
print(s)


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy
import heapq
m = 2 * 10 ** 5
mod = 998244353
fact = [0] * (m + 5)
fact_inv = [0] * (m + 5)
inv = [0] * (m + 5)
fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1
for i in range(2, m + 5):
	fact[i] = fact[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

def cmb(n, k, mod):
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod
ans = 0
(n, m, k) = list(map(int, input().split()))
for i in range(k + 1):
	ans = (ans + m * cmb(n - 1, i, mod) % mod * pow(m - 1, n - 1 - i, mod) % mod) % mod
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
ans = 0
x = 1
for i in range(k + 1):
	ans += m * pow(m - 1, n - i - 1, mod) % mod * x % mod
	ans %= mod
	x = x * (n - i - 1) * pow(i + 1, mod - 2, mod) % mod
print(ans % mod)


import sys
sys.setrecursionlimit(10 ** 8)
MOD = 998244353
(N, M, K) = map(int, input().split())
inv_M = pow(M - 1, -1, MOD) if M > 1 else 0
ans = 0
tmp = pow(M - 1, N - 1, MOD) if M > 1 else 0
comb = 1
for i in range(K + 1):
	ans = (ans + M * comb * tmp) % MOD
	if i == K:
		break
	tmp = tmp * inv_M % MOD
	comb = comb * (N - 1 - i) * pow(i + 1, -1, MOD) % MOD
if M == 1 and K == N - 1:
	ans += 1
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
fact = [1] * (N + 1)
fact_inv = [1] * (N + 1)
for i in range(1, N + 1):
	fact[i] = i * fact[i - 1] % mod
fact_inv[N] = pow(fact[N], mod - 2, mod)
for i in range(1, N + 1)[::-1]:
	fact_inv[i - 1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n - k] % mod
ans = 0
for i in range(K + 1):
	ans = (ans + comb(N - 1, i) * M * pow(M - 1, N - 1 - i, mod)) % mod
print(ans)


(N, M, K) = map(int, input().split())
out = 0
mod = 998244353
c = 1
for k in range(K + 1):
	out += M * pow(M - 1, N - k - 1, mod) * c
	out %= mod
	c *= (N - k - 1) * pow(k + 1, mod - 2, mod)
	c %= mod
print(out)


(N, M, K) = map(int, input().split())
mod = 998244353
fact = [1 for i in range(N + 1)]
for i in range(1, N):
	fact[i + 1] = fact[i] * (i + 1) % mod

def nCk(n, k):
	return fact[n] * pow(fact[n - k] * fact[k], mod - 2, mod)
result = 0
for k in range(K + 1):
	result += nCk(N - 1, k) * M * pow(M - 1, N - k - 1, mod)
	result = int(result) % mod
print(result)


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	(n, m, k) = list(map(int, readline().split()))
	MM = 998244353
	ans = 0
	com = 1
	for i in range(k + 1):
		l = n - i
		x = pow(m - 1, l - 1, MM)
		ans += m * x * com
		ans %= MM
		com *= n - (i + 1)
		com *= pow(i + 1, MM - 2, MM)
		com %= MM
	print(ans)
main()


mod = 998244353
(n, m, k) = map(int, input().split())
fcl = [1] * (n + 1)
for i in range(1, n + 1):
	fcl[i] = fcl[i - 1] * i % mod

def comb(x, y, p):
	return fcl[x] * pow(fcl[y], p - 2, p) % p * pow(fcl[x - y], p - 2, p) % p
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - 1 - i, mod) * comb(n - 1, i, mod)
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
N = n
fac = [1] * (N + 3)
inv = [1] * (N + 3)
t = 1
for i in range(1, N + 3):
	t *= i
	t %= mod
	fac[i] = t
t = pow(fac[N + 2], mod - 2, mod)
for i in range(N + 2, 0, -1):
	inv[i] = t
	t *= i
	t %= mod

def comb(n, r):
	if r > n or r < 0:
		return 0
	return fac[n] * inv[n - r] * inv[r] % mod
ans = pow(m, n, mod)
for i in range(k + 1, n):
	ans -= comb(n - 1, i) * m * pow(m - 1, n - i - 1, mod) % mod
	ans %= mod
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
UPPERLIMIT = 2 * 10 ** 5 + 1
MODMUL = [1, 1] + [0] * (UPPERLIMIT - 1)
for i in range(2, UPPERLIMIT + 1):
	MODMUL[i] = MODMUL[i - 1] * i % MOD
MODDIV = [1] * UPPERLIMIT + [pow(MODMUL[-1], MOD - 2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
	MODDIV[i - 1] = MODDIV[i] * i % MOD

def MODCOMB(n, r):
	return MODMUL[n] * MODDIV[r] % MOD * MODDIV[n - r] % MOD
ans = 0
for i in range(K + 1):
	ans += M * pow(M - 1, N - 1 - i, MOD) * MODCOMB(N - 1, i) % MOD
	ans %= MOD
print(ans)


MOD = 998244353
(N, M, K) = map(int, input().split())
f = [1]
for i in range(N):
	f.append(f[i] * (i + 1) % MOD)

def comb_mod(n, r, p):
	return f[n] * pow(f[r], p - 2, p) * pow(f[n - r], p - 2, p)
ans = 0
for i in range(K + 1):
	ans = (ans + M * pow(M - 1, N - 1 - i, MOD) * comb_mod(N - 1, i, MOD)) % MOD
print(ans)


(n, m, k) = map(int, input().split())
MOD = 998244353

def nck(n, k):
	(numer, denom) = (1, 1)
	for i in range(k):
		numer *= n - i
		denom *= k - i
	return numer * pow(denom, MOD - 2, MOD) % MOD
ans = 0
combination = 1
ans += m * pow(m - 1, n - 1, MOD) % MOD
for i in range(1, k + 1):
	combination *= (n - i) * pow(i, MOD - 2, MOD)
	combination %= MOD
	ans += combination * m * pow(m - 1, n - 1 - i, MOD) % MOD
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
ans = 0
if m == 1:
	print(1 if k == n - 1 else 0)
	exit()
tmp = m * pow(m - 1, n - 1, mod)
m_inv = pow(m - 1, mod - 2, mod)
invs = [0] + [pow(i + 1, mod - 2, mod) for i in range(n)]
for i in range(1, k + 2):
	ans += tmp
	tmp *= m_inv
	if i < n:
		tmp *= n - i
		tmp *= invs[i]
	tmp %= mod
print(ans % mod)


(n, m, k) = list(map(int, input().split()))
MOD = 998244353

class Combination:

	def __init__(self, n, mod):
		self.n = n
		self.mod = mod
		self.f = self._get_f()
		self.fi = self._get_fi()

	def __call__(self, k):
		if not 0 <= k <= self.n:
			return 0
		else:
			num = self.f[self.n]
			deninv = self.fi[k] * self.fi[self.n - k] % self.mod
			return num * deninv % self.mod

	def _get_f(self):
		f = 1
		lf = [1]
		for i in range(1, self.n + 1):
			f = f * i % self.mod
			lf.append(f)
		return lf

	def _get_fi(self):
		ii = 1
		lii = [0, 1]
		fi = 1
		lfi = [1, 1]
		for i in range(2, self.n + 1):
			ii = -lii[self.mod % i] * (self.mod // i) % self.mod
			lii.append(ii)
			fi = fi * ii % self.mod
			lfi.append(fi)
		return lfi
c = Combination(n - 1, MOD)

def n_pattern(i):
	result = m
	result *= c(i)
	result %= MOD
	result *= pow(m - 1, n - i - 1, MOD)
	result %= MOD
	return result
answer = sum((n_pattern(i) for i in range(k + 1))) % MOD
print(answer)


mod = 998244353
(N, M, K) = map(int, input().split())
invs = {}

def inv(n):
	if n not in invs:
		invs[n] = pow(n, mod - 2, mod)
	return invs[n]
fact = [1] * (N + 1)
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i
	fact[i] %= mod

def comb(n, r):
	ret = fact[n] * inv(fact[r]) * inv(fact[n - r])
	return ret % mod
ans = 0
for i in range(K + 1):
	now = M * pow(M - 1, N - 1 - i, mod) * comb(N - 1, i)
	now %= mod
	ans += now
	ans %= mod
print(ans)


from sys import stdin
(N, M, K) = [int(x) for x in stdin.readline().rstrip().split()]
mod = 998244353
maxn = 2 * 10 ** 5 + 1
fac = [0 for _ in range(maxn)]
finv = [0 for _ in range(maxn)]
inv = [0 for _ in range(maxn)]
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, maxn):
	fac[i] = fac[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	finv[i] = finv[i - 1] * inv[i] % mod

def combinations(n, k):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod
ans = 0
for i in range(0, K + 1):
	tmp = 1
	tmp *= M * pow(M - 1, N - i - 1, mod)
	tmp %= mod
	tmp *= combinations(N - 1, i)
	tmp %= mod
	ans += tmp
print(ans % mod)


def fast_pow(x, n, MOD):
	res = 1
	while n:
		if n & 1:
			res = res * x % MOD
		x = x * x % MOD
		n >>= 1
	return res

def prepare(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)
MOD = 998244353
(fact, fact_inv) = prepare(3 * 10 ** 5, MOD)
(n, m, k) = map(int, input().split())
dp = [0] * (n + 1)
ans = 0
for i in range(k + 1):
	color = fast_pow(m - 1, n - 1 - i, MOD)
	order = fact[n - 1] * fact_inv[i] % MOD * fact_inv[n - 1 - i] % MOD
	ans += m * color % MOD * order % MOD
	ans %= MOD
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline

def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % mod

def make_table2(n, mod=10 ** 9 + 7):
	g1 = [0] * (n + 1)
	g1[0] = 1
	g1[1] = 1
	tmp = 1
	for i in range(2, n + 1):
		tmp = tmp * i % mod
		g1[i] = tmp
	g2 = [0] * (n + 1)
	g2[-1] = pow(g1[-1], mod - 2, mod)
	tmp = g2[-1]
	for i in range(n - 1, -1, -1):
		tmp = tmp * (i + 1) % mod
		g2[i] = tmp
	return (g1, g2)
(N, M, K) = list(map(int, read().split()))
mod = 998244353
(g1, g2) = make_table2(N, mod)
answer = 0
for i in range(K + 1):
	answer = (answer + cmb(N - 1, i, mod) * M * pow(M - 1, N - i - 1, mod)) % mod
print(answer)


(n, m, k) = map(int, input().split())
if m == 1:
	if k == n - 1:
		print(1)
	else:
		print(0)
	return
MOD = 998244353
ans = tmp = m * (m - 1) ** (n - 1) % MOD
for i in range(k):
	tmp *= n - 1 - i
	tmp %= MOD
	tmp *= pow((m - 1) * (i + 1), -1, MOD)
	ans += tmp
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
ans = 0

def comb(n, r, mod):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % mod
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n + 1):
	fact.append(fact[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	factinv.append(factinv[-1] * inv[-1] % mod)
for i in range(k + 1):
	a = pow(m - 1, n - i - 1, mod)
	b = comb(n - 1, i, mod)
	ans += a * b % mod
ans *= m
print(ans % mod)


(N, M, K) = list(map(int, input().split()))
ans = 0
mod = 998244353
fact = [0] * 200001
invfact = [0] * 200001
fact[0] = 1
invfact[0] = 1
for i in range(1, 200001):
	fact[i] = fact[i - 1] * i % mod
invfact[-1] = pow(fact[-1], mod - 2, mod)
for i in reversed(list(range(1, 200000))):
	invfact[i] = invfact[i + 1] * (i + 1) % mod
for k in range(K + 1):
	ans += invfact[N - 1 - k] * invfact[k] * pow(M - 1, N - 1 - k, mod) % mod
	ans %= mod
ans = ans * M * fact[N - 1] % mod
print(ans)


mod = 998244353

def comb(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fa[n] * fi[r] % mod * fi[n - r] % mod
(n, m, k) = map(int, input().split())
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
	fa[i] = fa[i - 1] * i % mod
	fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(k + 1):
	ans += pow(m - 1, n - i - 1, mod) % mod * comb(n - 1, i) * m % mod
	ans %= mod
print(ans)


(n, m, k) = list(map(int, input().split()))
fac = [1] * n
finv = [1] * n
inv = [1] * n
MOD = 998244353
for i in range(2, n):
	fac[i] = fac[i - 1] * i % MOD
	inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def comb(n, k):
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
ans = 0
for i in range(k + 1):
	ans += comb(n - 1, i) * m * pow(m - 1, n - i - 1, MOD) % MOD
	ans %= MOD
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353

def comb(n, k):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * finv[k] % mod * finv[n - k] % mod
fac = [1] * (n + 1)
finv = [1] * (n + 1)
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
	finv[i] = pow(fac[i], mod - 2, mod)
p = [1] * (n + 1)
for i in range(1, n + 1):
	p[i] = p[i - 1] * (m - 1) % mod
ans = 0
for i in range(k + 1):
	ans += m * comb(n - 1, i) % mod * p[n - 1 - i] % mod
	ans %= mod
print(ans)


(N, M, K) = list(map(int, input().rstrip().split()))
fact = [0] * (N + 1)
fact_inv = [0] * (N + 1)
inv = [0] * (N + 1)
mod = 998244353
fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1
for i in range(2, N + 1):
	fact[i] = fact[i - 1] * i % mod
	inv[i] = mod - inv[mod % i] * (mod // i) % mod
	fact_inv[i] = fact_inv[i - 1] * inv[i] % mod
pow_M1 = [0] * N
pow_M1[0] = 1
for i in range(1, N):
	pow_M1[i] = pow_M1[i - 1] * (M - 1) % mod
ans = 0
for i in range(K + 1):
	comb = fact[N - 1] * fact_inv[i] * fact_inv[N - 1 - i] % mod
	ans += comb * M * pow_M1[N - i - 1] % mod
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
fac = [1 for _ in range(n + 1)]
fac_inv = [1 for _ in range(n + 1)]
memo = [1 for _ in range(n + 1)]
for i in range(n):
	fac[i + 1] = fac[i] * (i + 1) % mod
	fac_inv[i + 1] = pow(fac[i + 1], mod - 2, mod)
	memo[i + 1] = memo[i] * (m - 1) % mod
ans = 0
for i in range(0, k + 1):
	ans = (ans + m * memo[n - i - 1] * fac[n - 1] * fac_inv[i] * fac_inv[n - i - 1]) % mod
print(ans)


def main():
	mod = 998244353
	fact = [1, 1]
	for i in range(2, 400001):
		fact.append(fact[-1] * i % mod)

	def nCr(n, r):
		return pow(fact[n - r] * fact[r] % mod, mod - 2, mod) * fact[n] % mod
	(n, m, k) = map(int, input().split())
	ans = 0
	for i in range(k + 1):
		ans = (ans + m * pow(m - 1, n - i - 1, mod) * nCr(n - 1, n - i - 1)) % mod
	print(ans)
main()


p = 998244353
(N, M, K) = map(int, input().split())
ans = 0
cmb = 1
for k in range(K + 1):
	ans += M * pow(M - 1, N - k - 1, p) * cmb
	ans %= p
	cmb *= (N - 1 - k) * pow(k + 1, p - 2, p)
	cmb %= p
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353

def genCombinationFunction(max_k, mod):
	modinv_table = [-1] * (max_k + 1)
	modinv_table[1] = 1
	for i in range(2, max_k + 1):
		modinv_table[i] = -modinv_table[mod % i] * (mod // i) % mod

	def binomial_coefficients(n, k):
		ans = 1
		for i in range(k):
			ans *= n - i
			ans *= modinv_table[i + 1]
			ans %= mod
		return ans
	return (binomial_coefficients, modinv_table)
(f, table) = genCombinationFunction(10 ** 6, mod)
ans = 0
C = 1
for i in range(K + 1):
	base = M * pow(M - 1, N - i - 1, mod)
	if i:
		C *= N - i
		C *= table[i]
		C %= mod
	ans += C * base
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
ans = 0
mod = 998244353
f = [1]
for i in range(n):
	f += [f[-1] * (i + 1) % mod]

def comb(a, b):
	return f[a] * pow(f[b], mod - 2, mod) * pow(f[a - b], mod - 2, mod) % mod
for kk in range(k + 1):
	anss = m * pow(m - 1, n - 1 - kk, mod) % mod
	anss = anss * comb(n - 1, kk) % mod
	ans = (ans + anss) % mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
n = 200050
frac = [1] * (n + 1)
finv = [1] * (n + 1)
for i in range(n):
	frac[i + 1] = (i + 1) * frac[i] % mod
finv[-1] = pow(frac[-1], mod - 2, mod)
for i in range(1, n + 1):
	finv[n - i] = finv[n - i + 1] * (n - i + 1) % mod

def nCr(n, r):
	if n < 0 or r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return frac[n] * finv[n - r] * finv[r] % mod
ans = 0
for i in range(K + 1):
	tmp = M * nCr(N - 1, i) % mod
	tmp *= pow(M - 1, N - 1 - i, mod)
	ans += tmp % mod
print(ans % mod)


def main():
	MOD = 998244353
	if 'get_ipython' in globals():
		(n, m, k) = (60522, 114575, 7559)
	else:
		(n, m, k) = map(int, input().split())
	(ans, N, K) = (0, 1, 1)
	for i in range(k + 1):
		ans += N * pow(K, MOD - 2, MOD) * pow(m - 1, n - 1 - i, MOD)
		ans %= MOD
		N *= n - 1 - i
		N %= MOD
		K *= i + 1
		K %= MOD
	ans *= m
	ans %= MOD
	print(ans)
main()


class CombMod:

	def __init__(self, V, mod):
		self.fact = [1] * V
		self.finv = [1] * V
		for i in range(1, V):
			self.fact[i] = self.fact[i - 1] * i % mod
		self.finv[-1] = pow(self.fact[-1], mod - 2, mod)
		for i in range(V - 2, 0, -1):
			self.finv[i] = self.finv[i + 1] * (i + 1) % mod
		self.mod = mod

	def comb(self, a, b):
		return self.fact[a] * self.finv[b] % mod * self.finv[a - b] % mod
(N, M, K) = list(map(int, input().split()))
mod = 998244353
tool = CombMod(N + 1, mod)
ans = 0
for k in range(K + 1):
	val = M * tool.comb(N - 1, k) % mod * pow(M - 1, N - 1 - k, mod) % mod
	ans = (ans + val) % mod
print(ans)


import sys
from networkx.utils import UnionFind
from operator import itemgetter

def input():
	return sys.stdin.readline().rstrip()

class prepere_pch:

	def __init__(self, maxnum=3 * 10 ** 5, mod=10 ** 9 + 7):
		self.factorial = [0] * (maxnum + 1)
		self.factorial[0] = 1
		for i in range(1, maxnum):
			self.factorial[i] = self.factorial[i - 1] * i % mod
		self.mod = mod

	def per(self, n, r):
		return self.factorial[n] * pow(self.factorial[n - r], -1, self.mod) % self.mod

	def com(self, n, r):
		return self.per(n, r) * pow(self.factorial[r], -1, self.mod)

	def comH(self, n, r):
		return self.com(n + r - 1, r)

def main():
	(n, m, k) = list(map(int, input().split()))
	ans = 0
	pt = m
	pch = prepere_pch(mod=998244353)
	for same in range(n - 1, -1, -1):
		if same <= k:
			ans += pt * pch.com(n - 1, same)
			ans %= 998244353
		pt *= m - 1
		pt %= 998244353
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, M, K) = map(int, input().split())
if M == 1:
	print(1 if K == N - 1 else 0)
	exit()
mod = 998244353
f = [0] * N
f[0] = p = 1
for i in range(1, N):
	f[i] = p = p * i % mod
finv = [0] * N
finv[N - 1] = p = pow(f[N - 1], mod - 2, mod)
for i in range(N - 2, -1, -1):
	finv[i] = p = p * (i + 1) % mod
ans = 0
for k in range(K + 1):
	x = M * pow(M - 1, N - k - 1, mod) % mod
	y = f[N - 1] * finv[N - 1 - k] % mod * finv[k] % mod
	ans = (ans + x * y % mod) % mod
print(ans)


mod = 998244353
(n, m, k) = map(int, input().split())
mm1 = []
div = [0]
conv = [1]
p = 1
d = 1
for i in range(n):
	mm1.append(p)
	p = p * (m - 1) % mod
	div.append(pow(i + 1, mod - 2, mod))
	conv.append(conv[-1] * (n - i - 1) * div[-1] % mod)
ans = 0
for i in range(k + 1):
	a = m * mm1[n - i - 1] * conv[i]
	ans += a % mod
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
fact = [1 for i in range(N + 1)]
fact_inv = [1 for i in range(N + 1)]
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % mod
	fact_inv[i] = pow(fact[i], mod - 2, mod)
ans = 0
for k in range(K + 1):
	x = M * pow(M - 1, N - 1 - k, mod) * fact[N - 1] * fact_inv[k] * fact_inv[N - 1 - k]
	ans += x % mod
	ans = ans % mod
print(ans)


mod = 998244353
fact = [1]
for i in range(1, 2 * 10 ** 5 + 1):
	fact.append(fact[-1] * i % mod)
revfact = [1]
for i in range(1, 2 * 10 ** 5 + 1):
	revfact.append(pow(fact[i], mod - 2, mod))
(n, m, k) = map(int, input().split())
ans = 0
for i in range(k, -1, -1):
	group = n - i
	tmp = fact[n - 1] * revfact[group - 1] * revfact[n - 1 - (group - 1)]
	tmp %= mod
	tmp *= m
	tmp %= mod
	tmp *= pow(m - 1, group - 1, mod)
	ans += tmp
	ans %= mod
print(ans)


(n, m, k) = map(int, input().split())
MOD = 998244353
FAC = [1]
INV = [1]
for i in range(1, n + 1):
	FAC.append(FAC[i - 1] * i % MOD)
	INV.append(pow(FAC[-1], MOD - 2, MOD))

def nCr(n, r):
	return FAC[n] * INV[n - r] * INV[r]
ans = 0
for i in range(k + 1):
	ans += nCr(n - 1, i) * m * pow(m - 1, n - i - 1, MOD)
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
NN = N - 1
MAX = K + 1
com = [0] * MAX

def COM2init():
	com[0] = 1
	for i in range(1, MAX):
		if i > NN:
			break
		com[i] = com[i - 1] * (NN - i + 1) % MOD * pow(i, MOD - 2, MOD) % MOD
COM2init()
ans = 0
for k in range(K + 1):
	ans = (ans + M * pow(M - 1, N - k - 1, MOD) * com[k]) % MOD
print(ans)


from sys import stdin
readline = stdin.readline
(N, M, K) = map(int, readline().split())
mod = 998244353
fact = [1] * (N + 1)
finv = [1] * (N + 1)
inv = [1] * (N + 1)
inv[0] = 0
for i in range(2, N + 1):
	fact[i] = fact[i - 1] * i % mod
	inv[i] = -inv[mod % i] * (mod // i) % mod
	finv[i] = finv[i - 1] * inv[i] % mod

def com(N, K, mod):
	if K < 0 or N < K:
		return 0
	return fact[N] * finv[K] * finv[N - K] % mod
ans = 0
for x in range(K + 1):
	ans += com(N - 1, x, mod) * M * pow(M - 1, N - x - 1, mod)
	ans %= mod
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, m, k) = map(int, input().split())
mod = 998244353
n_max = 2 * (10 ** 5 + 1)
(F, FI) = ([0] * (n_max + 1), [0] * (n_max + 1))
(F[0], FI[0]) = (1, 1)
for i in range(n_max):
	F[i + 1] = F[i] * (i + 1) % mod
FI[n_max - 1] = pow(F[n_max - 1], mod - 2, mod)
for i in reversed(range(n_max - 1)):
	FI[i] = FI[i + 1] * (i + 1) % mod

def comb(x, y):
	return F[x] * FI[x - y] * FI[y] % mod
P = [1]
for i in range(n):
	P.append(P[-1] * (m - 1) % mod)
ans = 0
for i in range(k + 1):
	ans += m * P[n - 1 - i] * comb(n - 1, i)
	if ans > mod:
		ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
ans = 0
(x, y) = (1, 1)
for k in range(K + 1):
	ans = ans + M * x * pow(y, MOD - 2, MOD) * pow(M - 1, N - 1 - k, MOD)
	ans = ans % MOD
	x = x * (N - k - 1)
	y = y * (k + 1)
	x = x % MOD
	y = y % MOD
print(ans % MOD)


class Combination:

	def __init__(self, N, MOD):
		self.mod = MOD
		self.FACT = [1, 1]
		self.INV = [0, 1]
		self.FACTINV = [1, 1]
		for i in range(2, N + 1):
			self.FACT.append(self.FACT[-1] * i % self.mod)
			self.INV.append(pow(i, self.mod - 2, self.mod))
			self.FACTINV.append(self.FACTINV[-1] * self.INV[-1] % self.mod)

	def calculate(self, N, R):
		if R < 0 or N < R:
			return 0
		R = min(R, N - R)
		return self.FACT[N] * self.FACTINV[R] * self.FACTINV[N - R] % self.mod
(n, m, k) = list(map(int, input().split()))
mod = 998244353
cmb = Combination(n, mod)
cnt = 0
for i in range(k + 1):
	cnt += m * pow(m - 1, n - i - 1, mod) * cmb.calculate(n - 1, i) % mod
print(cnt % mod)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353

class CmbMod:

	def __init__(self, n, p):
		self.n = n
		self.p = p
		self.fact = [1, 1]
		self.factinv = [1, 1]
		self.inv = [0, 1]

	def cmb_mod(self, n, r):
		(numer, denom) = (1, 1)
		for i in range(r):
			numer = numer * (n - i) % self.p
			denom = denom * (i + 1) % self.p
		return numer * pow(denom, self.p - 2, self.p) % self.p

	def prep(self):
		for i in range(2, self.n + 1):
			self.fact.append(self.fact[-1] * i % self.p)
			self.inv.append(-self.inv[self.p % i] * (self.p // i) % self.p)
			self.factinv.append(self.factinv[-1] * self.inv[-1] % self.p)

	def cmb_mod_with_prep(self, n, r):
		if r < 0 or n < r:
			return 0
		r = min(r, n - r)
		return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p

def resolve():
	(n, m, k) = list(map(int, input().split()))
	cmb = CmbMod(n, mod)
	cmb.prep()
	res = 0
	for i in range(k + 1):
		res += m * pow(m - 1, n - (i + 1), mod) * cmb.cmb_mod_with_prep(n - 1, i) % mod
		res %= mod
	print(res)

def __starting_point():
	resolve()
__starting_point()


def pre_c(n, mod):
	f = [0] * (n + 1)
	g = [0] * (n + 1)
	for i in range(n + 1):
		if i == 0:
			f[i] = 1
			g[i] = 1
		else:
			f[i] = f[i - 1] * i % mod
			g[i] = pow(f[i], mod - 2, mod)
	return (f, g)
(n, m, k) = map(int, input().split())
mod = 998244353
(F, G) = pre_c(n - 1, mod)
cnt = 0
for i in range(k + 1):
	temp = F[n - 1] * G[i] * G[n - 1 - i] * m * pow(m - 1, n - 1 - i, mod)
	cnt = (cnt + temp) % mod
print(cnt)


(n, m, k) = [int(t) for t in open(0).read().split()]
mod = 998244353
mem = [0] * max(k + 3, n + 1)
for i in range(k + 2):
	mem[i] = pow(m, i, mod)
c = 1
for i in range(k + 2, n + 1):
	mem[i] = (m * mem[i - 1] - m * c * pow(m - 1, i - k - 2, mod)) % mod
	c = c * (i - 1) * pow(i - k - 1, -1, mod) % mod
print(mem[n])


(N, M, K) = map(int, input().split())
mod = 998244353
fact = [1 for i in range(N + 1)]
fact_inv = [1 for i in range(N + 1)]
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % mod
	fact_inv[i] = pow(fact[i], mod - 2, mod)

def cmb(n, k):
	return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod
ans = 0
for k in range(K + 1):
	now = M * pow(M - 1, N - k - 1, mod) * cmb(N - 1, k)
	ans = (ans + now % mod) % mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
fac = [1]
inv = [1]
for i in range(1, N + 10):
	fac.append(fac[-1] * i % mod)
	inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r):
	return fac[n] * inv[n - r] * inv[r] % mod
ret = 0
for k in range(K + 1):
	ret += comb(N - 1, k) * M * pow(M - 1, N - k - 1, mod) % mod
	ret %= mod
print(ret)


def cmb(n, r, p):
	return fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p) % p
p = 998244353
(N, M, K) = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
	fac[i] = fac[i - 1] * i % p
ans = 0
for k in range(K + 1):
	ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
	ans %= p
print(ans)


(n, m, k) = map(int, input().split())
mod = 998244353
fact = [1]
fact_inv = [1]
for i in range(n + 1):
	new_fact = fact[-1] * (i + 1) % mod
	fact.append(new_fact)
	fact_inv.append(pow(new_fact, mod - 2, mod))

def mod_comb(n, k, mod):
	return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - 1 - i, mod) * mod_comb(n - 1, i, mod) % mod
ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
mod = 998244353
c = 1
answer = 0
for i in range(K + 1):
	answer += M * c * pow(M - 1, N - i - 1, mod) % mod
	answer %= mod
	c = c * (N - i - 1) * pow(i + 1, mod - 2, mod) % mod
print(answer)


(n, m, k) = map(int, input().split())
MOD = 998244353

def fn(n, m):
	return m * pow(m - 1, n - 1, MOD) % MOD
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n):
	fact.append(fact[-1] * i % MOD)
	inv.append(-inv[MOD % i] * (MOD // i) % MOD)
	factinv.append(factinv[-1] * inv[-1] % MOD)

def nCr(n, r):
	return fact[n] * factinv[r] * factinv[n - r] % MOD
ans = fn(n, m)
for i in range(1, k + 1):
	ans += nCr(n - 1, i) * fn(n - i, m)
	ans %= MOD
print(ans)


class Combination:

	def __init__(self, n, mod=10 ** 9 + 7):
		self.mod = mod
		self.fac = [1] * (n + 1)
		for i in range(1, n + 1):
			self.fac[i] = self.fac[i - 1] * i % self.mod
		self.invfac = [1] * (n + 1)
		self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
		for i in range(n - 1, 0, -1):
			self.invfac[i] = self.invfac[i + 1] * (i + 1) % self.mod

	def combination(self, n, r):
		ans = self.fac[n] * self.invfac[r] % self.mod * self.invfac[n - r] % self.mod
		if n >= r:
			return ans
		else:
			return 0

	def factorial(self, i):
		return self.fac[i]

	def invfactorial(self, i):
		return self.invfac[i]

def main():
	import sys

	def input():
		return sys.stdin.readline().rstrip()
	(n, m, k) = map(int, input().split())
	mod = 998244353
	c = Combination(n, mod)
	ans = 0
	mex = [0] * (k + 1)
	mex[0] = pow(m - 1, n - k - 1, mod)
	for i in range(1, k + 1):
		mex[i] = mex[i - 1] * (m - 1) % mod
	mex = mex[::-1]
	for i in range(k + 1):
		ans += c.combination(n - 1, i) * mex[i]
		ans %= mod
	ans *= m
	ans %= mod
	print(ans)

def __starting_point():
	main()
__starting_point()


mod = 998244353
(n, m, k) = map(int, input().split())
count = 0
comb = 1
for i in range(k + 1):
	tmp = comb * m * pow(m - 1, n - i - 1, mod) % mod
	count = (count + tmp) % mod
	comb = comb * (n - i - 1) * pow(i + 1, mod - 2, mod) % mod
print(count)


(n, m, k) = map(int, input().split())
mod = 998244353
fact = [1] * (n + 1)
rfact = [1] * (n + 1)
r = 1
for i in range(1, n + 1):
	fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod - 2, mod)
for i in range(n, 0, -1):
	rfact[i - 1] = r = r * i % mod

def perm(n, k):
	return fact[n] * rfact[n - k] % mod

def comb(n, k):
	return fact[n] * rfact[k] * rfact[n - k] % mod
paint = [0] * n
ans = 0
for i in range(n - k - 1, n):
	ans += comb(n - 1, i) * pow(m - 1, i, mod)
ans *= m
ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
MOD = 998244353
fac = [1] * (N + 1)
inv = [1] * (N + 1)
ifac = [1] * (N + 1)
for i in range(2, N + 1):
	fac[i] = fac[i - 1] * i % MOD
	inv[i] = -(inv[MOD % i] * (MOD // i)) % MOD
	ifac[i] = ifac[i - 1] * inv[i] % MOD
cmbarr = [1] * N
for r in range(N - 1):
	cmbarr[r + 1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD
A = [M * pow(M - 1, N - 1 - i, MOD) * cmbarr[i] % MOD for i in range(K + 1)]
print(sum(A) % MOD)


mod = 998244353
(n, m, k) = map(int, input().split())
fac = [1]
for i in range(n):
	fac.append(fac[-1] * (i + 1) % mod)
ans = 0
for x in range(k + 1):
	rev = pow(fac[x] * fac[n - 1 - x] % mod, mod - 2, mod)
	r = fac[n - 1] * rev % mod * m * pow(m - 1, n - x - 1, mod) % mod
	ans += r
	ans %= mod
print(ans)


(N, M, K) = list(map(int, input().split()))
mod = 998244353
MAX = 510000
fac = [0] * MAX
facinv = [0] * MAX
inv = [0] * MAX

def modinv(a, mod):
	b = mod
	(x, u) = (1, 0)
	while b:
		q = a // b
		(a, b) = (b, a - q * b)
		(x, u) = (u, x - q * u)
	x %= mod
	return x

def mod_nCr_init(n, mod):
	fac[0] = fac[1] = 1
	facinv[0] = facinv[1] = 1
	inv[1] = 1
	for i in range(2, n):
		fac[i] = fac[i - 1] * i % mod
		inv[i] = -inv[mod % i] * (mod // i) % mod
		facinv[i] = facinv[i - 1] * inv[i] % mod

def mod_nCr(n, r, mod):
	if n < r or n < 0 or r < 0:
		return 0
	return fac[n] * (facinv[r] * facinv[n - r] % mod) % mod
mod_nCr_init(MAX, mod)
ans = 0
for i in range(K + 1):
	ans += mod_nCr(N - 1, i, mod) * M * pow(M - 1, N - i - 1, mod)
	ans %= mod
print(ans)


def solve():
	(N, M, K) = map(int, input().split())
	mod = 998244353
	dp = [1] * (K + 1)
	for i in range(1, K + 1):
		dp[i] = dp[i - 1] * (N - i) * pow(i, mod - 2, mod) % mod
	ans = 0
	for i in range(K + 1):
		ans += dp[i] * M * pow(M - 1, N - 1 - i, mod)
		ans %= mod
	return ans
print(solve())


MOD = 998244353
MAXN = 2 * 10 ** 5 + 10
f = [1]
for i in range(MAXN):
	f.append(f[-1] * (i + 1) % MOD)

def nCr(n, r, mod=MOD):
	return f[n] * pow(f[r], mod - 2, mod) * pow(f[n - r], mod - 2, mod) % mod
(N, M, K) = map(int, input().split())
ans = 0
for i in range(K + 1):
	tmp = pow(M - 1, N - i - 1, MOD) * M % MOD
	tmp *= nCr(N - 1, i, MOD)
	ans += tmp % MOD
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
p = 998244353
cnt = 0
com = 1
for k in range(K + 1):
	l = N - k
	x = pow(M - 1, l - 1, p)
	cnt += M * x * com
	cnt %= p
	com *= N - (k + 1)
	com *= pow(k + 1, p - 2, p)
	com %= p
print(cnt)


class Combination:

	def __init__(self, n_max, mod=10 ** 9 + 7):
		self.mod = mod
		f = 1
		self.fac = fac = [f]
		for i in range(1, n_max + 1):
			f = f * i % mod
			fac.append(f)
		f = pow(f, mod - 2, mod)
		self.facinv = facinv = [f]
		for i in range(n_max, 0, -1):
			f = f * i % mod
			facinv.append(f)
		facinv.reverse()

	def __call__(self, n, r):
		return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod
(N, M, K) = list(map(int, input().split()))
mod = 998244353
comb = Combination(202020, mod)
ans = 0
for n in range(0, K + 1):
	ans += comb(N - 1, n) * pow(M - 1, N - 1 - n, mod) % mod
ans = ans * M % mod
print(ans)


(N, M, K) = list(map(int, input().split()))
ans = 0

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
p = 998244353
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
	fact.append(fact[-1] * i % p)
	inv.append(-inv[p % i] * (p // i) % p)
	factinv.append(factinv[-1] * inv[-1] % p)
for i in range(K + 1):
	res_i = M * pow(M - 1, N - i - 1, p) % p
	res_i = res_i * cmb(N - 1, i, p) % p
	ans = (ans + res_i) % p
print(ans)


def main():
	MOD = 998244353
	(n, m, k) = list(map(int, input().split()))
	fact = [0] * 220000
	invfact = [0] * 220000
	fact[0] = 1
	for i in range(1, 220000):
		fact[i] = fact[i - 1] * i % MOD
	invfact[220000 - 1] = pow(fact[220000 - 1], MOD - 2, MOD)
	for i in range(220000 - 2, -1, -1):
		invfact[i] = invfact[i + 1] * (i + 1) % MOD

	def nCk(n, k):
		if k < 0 or n < k:
			return 0
		return fact[n] * invfact[k] * invfact[n - k] % MOD
	ans = 0
	for i in range(0, k + 1):
		ans += m * pow(m - 1, n - i - 1, MOD) * nCk(n - 1, i) % MOD
	print(ans % MOD)

def __starting_point():
	main()
__starting_point()


(n, m, k) = map(int, input().split())
mod = 998244353
if m == 1:
	print(0 if k != n - 1 else 1)
	exit()
fact = [1] * (n - 1 + 1)
inv = [1] * (n - 1 + 1)
for i in range(2, n - 1 + 1):
	fact[i] = i * fact[i - 1] % mod
inv[-1] = pow(fact[-1], mod - 2, mod)
for i in range(n - 1, 1, -1):
	inv[i - 1] = inv[i] * i % mod
ans = 0
po = pow(m - 1, n - 1, mod) * m % mod
ue = fact[n - 1]
iii = pow(m - 1, mod - 2, mod) % mod
for i in range(k + 1):
	ans += ue * inv[n - 1 - i] % mod * inv[i] % mod * po % mod
	po *= iii
	po %= mod
print(ans % mod)


(n, m, k) = map(int, input().split())
MOD = 998244353
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
	fac[j] = fac[j - 1] * j % MOD
inv[n] = pow(fac[n], MOD - 2, MOD)
for j in range(n - 1, -1, -1):
	inv[j] = inv[j + 1] * (j + 1) % MOD

def comb(n, r):
	if r > n or n < 0 or r < 0:
		return 0
	return fac[n] * inv[n - r] * inv[r] % MOD
ans = 0
for i in range(k + 1):
	ans += m * pow(m - 1, n - i - 1, MOD) * comb(n - 1, i) % MOD
print(ans % MOD)


from sys import exit
(n, m, k) = map(int, input().split())
if m == 1:
	if k == n - 1:
		print(1)
	else:
		print(0)
	exit()
MOD = 998244353
ans = tmp = m * (m - 1) ** (n - 1) % MOD
for i in range(k):
	tmp *= n - 1 - i
	tmp %= MOD
	tmp *= pow((m - 1) * (i + 1), -1, MOD)
	ans += tmp
	ans %= MOD
print(ans)


MOD = 998244353
(n, m, k) = map(int, input().split())
fac = [1] * (n + 1)
fac_inv = [0] * (n + 1)
for i in range(n):
	fac[i + 1] = fac[i] * (i + 1) % MOD
fac_inv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(n, 0, -1):
	fac_inv[i - 1] = fac_inv[i] * i % MOD

def comb(n, k):
	if k < 0 or k > n:
		return 0
	x = fac[n] * (fac_inv[k] * fac_inv[n - k]) % MOD % MOD
	return x
ans = 0
for i in range(k + 1):
	ans += comb(n - 1, i) * m % MOD * pow(m - 1, n - i - 1, MOD) % MOD
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
P = [1 for i in range(10 ** 6 + 1)]
for i in range(10 ** 6):
	P[i + 1] = P[i] * (i + 1) % mod

def comb(a, b):
	if a >= b:
		return P[a] * pow(P[a - b], mod - 2, mod) * pow(P[b], mod - 2, mod) % mod
	else:
		return 0
ans = 0
for i in range(K + 1):
	ans += M * comb(N - 1, i) * pow(M - 1, N - 1 - i, mod)
	ans %= mod
print(ans)


(n, m, k) = (int(i) for i in input().split())
mod = 998244353
fac = [1]
inv = []
for i in range(n - 1):
	fac.append(fac[-1] * (i + 2) % mod)
for i in range(n):
	inv.append(pow(fac[i], mod - 2, mod))

def modcom(n, k, fac, inv):
	if k > n or k < 0:
		return 0
	elif k == n or k == 0:
		return 1
	else:
		return fac[n - 1] * inv[k - 1] * inv[n - k - 1] % mod
r = 0
for i in range(0, k + 1):
	r += m % mod * pow(m - 1, n - 1 - i, mod) * modcom(n - 1, i, fac, inv)
print(r % mod)


(n, m, k) = map(int, input().split())
mod = 998244353
N = 10 ** 6
fact = [1, 1]
fact_inv = [1, 1]
inv = [0, 1]

def comb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return fact[n] * fact_inv[r] * fact_inv[n - r] % mod

def perm(n, r, mod):
	if r < 0 or r > n:
		return 0
	return fact[n] * fact_inv[n - r] % mod
for i in range(2, N + 1):
	fact.append(fact[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	fact_inv.append(fact_inv[-1] * inv[-1] % mod)
ans = 0
for i in range(k + 1):
	ans += comb(n - 1, i, mod) * m * pow(m - 1, n - i - 1, mod)
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
ans = 0
comb = [1]
for i in range(K):
	comb_temp = comb[i] * (N - 1 - i) * pow(i + 1, -1, mod)
	comb_temp %= mod
	comb.append(comb_temp)
for k in range(K + 1):
	ans_temp = M * comb[k] * pow(M - 1, N - 1 - k, mod)
	ans += ans_temp
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
MOD = 998244353
ans = 0

def calc(n, m):
	return m * pow(m - 1, n - 1, MOD) % MOD
(C, ans) = (1, calc(N, M))
for k in range(1, K + 1):
	C = C * (N - k) % MOD * pow(k, MOD - 2, MOD) % MOD
	ans = (ans + C * calc(N - k, M) % MOD) % MOD
print(ans)


mod = 998244353
(N, M, K) = map(int, input().split())
ans = 0

def pow(x, n):
	if n == 0:
		return 1
	if n % 2 == 0:
		return pow(x ** 2 % mod, n // 2) % mod
	else:
		return x * pow(x ** 2 % mod, (n - 1) // 2) % mod
A = 1
for i in range(K + 1):
	p = N - i
	x = M * pow(M - 1, p - 1) * A % mod
	ans += x
	A = A * (N - i - 1) % mod
	y = pow(i + 1, mod - 2)
	A = A * y % mod
print(ans % mod)


def main():
	(N, M, K) = list(map(int, input().split()))
	mod = 998244353
	r = 0
	m = 1
	inv = [0] * (N + 1)
	inv[1] = 1
	for i in range(2, N + 1):
		inv[i] = inv[mod % i] * ((mod - mod // i) % mod)
	for i in range(K + 1):
		if i > 0:
			m = m * (N - i) * inv[i] % mod
		r += M * pow(M - 1, N - i - 1, mod) * m
	return r % mod
print(main())


(N, M, K) = map(int, input().split())
MOD = 998244353
fact = [1]
rfact = [1]
for i in range(1, N + 1):
	fact.append(fact[i - 1] * i % MOD)
	rfact.append(pow(fact[i], MOD - 2, MOD))

def cmb(n, m):
	return fact[n] * rfact[m] * rfact[n - m] % MOD
answer = 0
for i in range(K + 1):
	answer += M * cmb(N - 1, i) * pow(M - 1, N - 1 - i, MOD) % MOD
print(answer % MOD)


MOD = 998244353
fac = [1] * (3 * 10 ** 5)
for i in range(len(fac) - 1):
	fac[i + 1] = fac[i] * (i + 1) % MOD

def comb(n, k):
	return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD
(n, m, k) = map(int, input().split())
ans = 0
for a in range(n, n - k - 1, -1):
	ans += m * pow(m - 1, a - 1, MOD) * comb(n - 1, a - 1) % MOD
print(ans % MOD)


(N, M, K) = map(int, input().split())
MOD = 998244353
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
comb = [M] * (K + 1)
for i in range(1, K + 1):
	comb[i] = comb[i - 1] * (N - i) % MOD
	comb[i] = comb[i] * modinv(i) % MOD
ans = 0
for i in range(K + 1):
	ans = (ans + comb[i] * pow(M - 1, N - i - 1, MOD)) % MOD
print(ans)


(n, M, K) = list(map(int, input().split()))
mod = 998244353
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
	fac[j] = fac[j - 1] * j % mod
inv[n] = pow(fac[n], mod - 2, mod)
for j in range(n - 1, -1, -1):
	inv[j] = inv[j + 1] * (j + 1) % mod

def comb(n, r):
	if r > n or n < 0 or r < 0:
		return 0
	return fac[n] * inv[n - r] * inv[r] % mod
ans = 0
temp = M * (M - 1) ** (n - K - 1) % mod
for k in range(K + 1)[::-1]:
	ans = (ans + temp * comb(n - 1, k)) % mod
	temp = temp * (M - 1) % mod
print(ans)


(N, M, K) = map(int, input().split())

def comb_list(n, r, mod):
	ret = [1]
	for i in range(1, r + 1):
		ret.append(ret[-1] * (n + 1 - i) * pow(i, mod - 2, mod) % mod)
	return ret
ans = 0
mod = 998244353
c_list = comb_list(N - 1, K, mod)
for i in range(K + 1):
	ans = (ans + c_list[i] * M * pow(M - 1, N - i - 1, mod)) % mod
print(ans)


import numpy as np
N = 10 ** 6
Nsq = 10 ** 3
mod = 998244353
(n, m, k) = list(map(int, input().split()))
fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
	fac[:, i] *= fac[:, i - 1]
	fac[:, i] %= mod
for i in range(1, Nsq):
	fac[i] *= fac[i - 1, -1]
	fac[i] %= mod
fac = fac.ravel()
finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
	finv[:, i] *= finv[:, i - 1]
	finv[:, i] %= mod
for i in range(1, Nsq):
	finv[i] *= finv[i - 1, -1]
	finv[i] %= mod
finv = finv.ravel()[::-1]

def nCr(a, b):
	comb = fac[a] * finv[b] % mod * finv[a - b] % mod
	return comb
prt = [1] * (n + 1)
for i in range(n):
	prt[i + 1] = prt[i] * (m - 1) % mod
res = 0
for i in range(k + 1):
	res += m * prt[n - i - 1] % mod * nCr(n - 1, i)
	res %= mod
print(res)


(n, m, k) = map(int, input().split())
mod = 998244353
fact = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, n + 5):
	fact.append(fact[-1] * i % mod)
	inv.append(inv[mod % i] * (mod - mod // i) % mod)
	finv.append(finv[-1] * inv[-1] % mod)
f = pow(m - 1, mod - 2, mod)

def nCr(n, r, mod):
	if r > n:
		return 0
	else:
		return fact[n] * finv[r] * finv[n - r] % mod
ans = 0
for i in range(k + 1):
	ans += nCr(n - 1, i, mod) * m * pow(m - 1, n - 1 - i, mod) % mod
	ans %= mod
print(ans % mod)


(N, M, K) = list(map(int, input().split()))
MOD = 998244353
MAX_N = 10 ** 6
fac = [0] * MAX_N
fac_inv = [0] * MAX_N
fac[0] = 1
for i in range(MAX_N - 1):
	fac[i + 1] = fac[i] * (i + 1) % MOD
fac_inv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(MAX_N - 2, -1, -1):
	fac_inv[i] = fac_inv[i + 1] * (i + 1) % MOD

def nCk(n, k):
	return fac[n] * fac_inv[k] % MOD * fac_inv[n - k] % MOD
ans = 0
for k in range(K + 1):
	temp = M * nCk(N - 1, k) % MOD * pow(M - 1, N - k - 1, MOD) % MOD
	ans += temp
	ans %= MOD
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
	fac.append(fac[-1] * i % mod)
	inv.append(mod - inv[mod % i] * (mod // i) % mod)
	finv.append(finv[-1] * inv[-1] % mod)

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod
ans = 0
for i in range(K + 1):
	ans += comb(N - 1, i) * M * pow(M - 1, N - 1 - i, mod)
	ans %= mod
print(ans)


(N, M, K) = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]
for i in range(1, N + 1):
	nCi.append(nCi[i - 1] * (N - i) * pow(i, mod - 2, mod) % mod)
for i in range(K + 1):
	ans += M * pow(M - 1, N - 1 - i, mod) * nCi[i]
	ans %= mod
print(ans)


Q = 998244353

def main():
	(N, M, K) = map(int, input().split())
	ans = 0
	cmb = 1
	for k in range(K + 1):
		ans += M * pow(M - 1, N - 1 - k, Q) % Q * cmb % Q
		ans %= Q
		cmb *= (N - k - 1) * pow(k + 1, Q - 2, Q) % Q
		cmb %= Q
	print(ans)
main()


import math
(N, M, K) = map(int, input().split())
mod = 998244353
ans = 0
d = [1] + [1]
e = [0] + [1]
f = [0] + [1]
for i in range(2, N + 1):
	d += [d[i - 1] * i % mod]
	e += [e[mod % i] * (mod - int(mod / i)) % mod]
	f += [f[i - 1] * e[i] % mod]

def combinations_count(n, r):
	if r == n or r == 0:
		return 1
	return d[n] * f[n - r] * f[r] % mod
for i in range(K + 1):
	l = M * pow(M - 1, N - 1 - i, mod) % mod
	ans += l * combinations_count(N - 1, i) % mod
	ans %= mod
print(ans)