On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.

There are $n$ bricks lined in a row on the ground. Chouti has got $m$ paint buckets of different colors at hand, so he painted each brick in one of those $m$ colors.

Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $k$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).

So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $998\,244\,353$.


-----Input-----

The first and only line contains three integers $n$, $m$ and $k$ ($1 \leq n,m \leq 2000, 0 \leq k \leq n-1$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.


-----Output-----

Print one integer — the number of ways to color bricks modulo $998\,244\,353$.


-----Examples-----
Input
3 3 0

Output
3

Input
3 2 1

Output
4



-----Note-----

In the first example, since $k=0$, the color of every brick should be the same, so there will be exactly $m=3$ ways to color the bricks.

In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $4$ possible colorings. [Image]

Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
(N, M, K) = map(int, input().split())
MOD = 998244353
dp = [[0] * 2002 for i in range(2002)]
dp[1][0] = M
for i in range(1, N):
	for j in range(K + 1):
		dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
		dp[i + 1][j + 1] = dp[i][j] * (M - 1) % MOD
print(dp[N][K])


from math import factorial as f
mod = 998244353
(n, m, k) = map(int, input().split())
ans = 1
for i in range(k):
	ans = ans * (m - 1) % mod
ans = ans * m % mod
val = f(n - 1) // (f(k) * f(n - 1 - k))
ans = ans * val % mod
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, m, k) = RL()
	dp = [[0] * (k + 2) for _ in range(n + 1)]
	for i in range(1, n + 1):
		dp[i][0] = m
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if j > i - 1:
				break
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod
			dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (m - 1)) % mod
	print(dp[n][k] % mod)
main()


(n, m, k) = map(int, input().split())
dp = [[0] * (n + 1) for i in range(n)]
MOD = 998244353
dp[0][0] = m
for i in range(1, n):
	for j in range(k + 1):
		dp[i][j + 1] += dp[i - 1][j] * (m - 1)
		dp[i][j] += dp[i - 1][j]
		dp[i][j + 1] %= MOD
		dp[i][j] %= MOD
print(dp[n - 1][k])


import sys, threading
sys.setrecursionlimit(4000000)
threading.stack_size(10 ** 8)

def f(x, y):
	global m, dp
	a = 0
	b = 0
	if x == 1 and y == 1:
		return m - 1
	if x == 1 and y == 0:
		return 1
	if dp[x][y] >= 0:
		return dp[x][y]
	if y > 0 and x >= y:
		a = (m - 1) * f(x - 1, y - 1)
		a %= 998244353
	if x >= y:
		b = f(x - 1, y)
		b %= 998244353
	dp[x][y] = (a + b) % 998244353
	return dp[x][y]

def main():
	global m, dp
	dp = [[-1 for j in range(2001)] for i in range(2001)]
	(n, m, k) = map(int, input().split())
	if n > 1:
		ans = m * f(n - 1, k)
	else:
		ans = m
	print(ans % 998244353)
t = threading.Thread(target=main)
t.start()
t.join()


from math import factorial
e = list(map(int, input().split()))
(n, m, k) = e[:]
print(factorial(n - 1) // factorial(k) // factorial(n - k - 1) * m * (m - 1) ** k % 998244353)


from math import factorial as f
(n, m, k) = [int(x) for x in input().split()]
if k == 0:
	print(m)
else:
	a = f(n - 1)
	b = f(k)
	c = f(n - 1 - k)
	d = b * c
	e = a // d
	t = e * m * (m - 1) ** k
	print(t % 998244353)


import math

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


from math import factorial
(n, m, k) = map(int, input().split())

def combinations(n, k):
	return factorial(n) // (factorial(n - k) * factorial(k))
print(int(combinations(n - 1, k) * m * (m - 1) ** k % 998244353))


P = 998244353

def C(n, k):
	nonlocal P
	k = min(k, n - k)
	p = 1
	for i in range(n, n - k, -1):
		p *= i
	for i in range(k, 0, -1):
		assert p % i == 0
		p //= i
	return p % P
(n, m, k) = list(map(int, input().split()))
r = C(n - 1, k)
r = r * m % P
for i in range(k):
	r = r * (m - 1) % P
print(r)


def inv(x):
	return pow(x, MOD - 2, MOD)

def C(n, r):
	return fact[n] * inv(fact[r]) * inv(fact[n - r])
(n, m, k) = map(int, input().split())
MOD = 998244353
fact = [1]
for i in range(1, 2100):
	fact.append(fact[-1] * i % MOD)
ans = C(n - 1, k) * m * pow(m - 1, k, MOD)
ans %= MOD
print(ans)


import math
f = math.factorial
(n, m, k) = map(int, input().split())
print(f(n - 1) // f(k) // f(n - k - 1) * m * (m - 1) ** k % 998244353)


(n, m, k) = [int(x) for x in input().split()]
dp = [0] * (n - 1)
if len(dp) > 0:
	dp[0] = n - 1
	n -= 1
	for i in range(1, n):
		n -= 1
		dp[i] = dp[i - 1] * n // (i + 1)
	if k == 0:
		print(m)
	else:
		print(dp[k - 1] * m * (m - 1) ** k % 998244353)
else:
	print(m)


R = lambda : map(int, input().split())
(n, m, k) = R()
dp = [[0] * (k + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
	dp[i][0] = m
for i in range(1, n + 1):
	for j in range(1, k + 1):
		dp[i][j] = (dp[i - 1][j] + (m - 1) * dp[i - 1][j - 1]) % 998244353
print(dp[n][k])


import math
MOD = 998244353
(n, m, k) = [int(x) for x in input().split()]
ans = math.factorial(n - 1) // (math.factorial(k) * math.factorial(n - k - 1)) * m * (m - 1) ** k
print(ans % MOD)


from math import factorial, pow
(n, m, k) = map(int, input().split())
mod = 998244353
c = factorial(n - 1) // factorial(k) // factorial(n - 1 - k)
ans = c * m * (m - 1) ** k
print(int(ans % mod))


(n, m, k) = [int(x) for x in input().split()]

def perm(n, k):
	s = 1
	for i in range(n - k + 1, n + 1):
		s *= i
	return s

def choose(n, k):
	if k > n // 2:
		return choose(n, n - k)
	else:
		return perm(n, k) // perm(k, k)
ans = m
for i in range(0, k):
	ans = ans * (m - 1) % 998244353
print(ans * choose(n - 1, k) % 998244353)


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


MOD = 998244353

def power(x, a):
	if a == 0:
		return 1
	z = power(x, a // 2)
	z = z * z % MOD
	if a % 2:
		z = z * x % MOD
	return z

def fact(n):
	factn = 1
	for i in range(2, n + 1):
		factn = factn * i % MOD
	return factn

def ncr(n, r):
	return fact(n) * power(fact(r), MOD - 2) * power(fact(n - r), MOD - 2) % MOD
[n, m, k] = list(map(int, input().split()))
print(ncr(n - 1, k) * m * power(m - 1, k) % MOD)


import math

def binom(n, k):
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k)
m = list(map(int, input().split()))
n = m[0]
c = m[1]
k = m[2]
print(int(binom(n - 1, k) * c * (c - 1) ** k % 998244353))


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

def comb(x, r):
	return f[x] * pow(f[r], mod - 2, mod) * pow(f[x - r], mod - 2, mod) % mod
ans = comb(n - 1, k) * m * pow(m - 1, k, mod) % mod
print(ans)


(n, m, k) = [int(x) for x in input().split()]
mod = 998244353

def com(n, r, p=998244353):
	C = [0 for i in range(r + 1)]
	C[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, r), 0, -1):
			C[j] = (C[j] + C[j - 1]) % p
	return C[r]
ans = com(n - 1, k) * m * pow(m - 1, k, mod) % mod
print(ans)


def binomialCoef(n, k):
	C = [[0 for x in range(k + 1)] for x in range(n + 1)]
	mod = 998244353
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod
	return C[n][k]
(n, m, k) = map(int, input().split())
mod = 998244353
y = binomialCoef(n - 1, k)
z = m * (m - 1) ** k % mod
print(int(y * z % mod))


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass

def e_gcd(a, b):
	if a == 0 and b == 0:
		return (-1, 0, 0)
	if b == 0:
		return (a, 1, 0)
	(d, y, x) = e_gcd(b, a % b)
	y -= a // b * x
	return (d, x, y)

def m_reverse(a, n):
	(d, x, y) = e_gcd(a, n)
	dprint(x, y, a, n)
	assert x * a + y * n == d
	if d == 1:
		if x % n <= 0:
			return x % n + n
		else:
			return x % n
	else:
		return -1
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
base = 998244353
d = 1233
t = m_reverse(d, base)
dprint(t)
z = t * d % base
dprint(z)
(N, M, K) = getIntList()
J = N - 1 - K
Z = N - J
dprint(Z)
R = M
for i in range(Z - 1):
	R *= M - 1
	R %= base
dprint(R)
n0 = J
m0 = Z
dprint(n0, m0)
for i in range(m0 - 1):
	g = n0 + m0 - 1 - i
	R *= g
	R %= base
for i in range(2, m0):
	t = m_reverse(i, base)
	R *= t
	R %= base
print(R)


f = [[0 for i in range(2001)] for j in range(2001)]
mod = 998244353

def colorful_bricks(n, m, k):
	f[1][0] = m
	for i in range(2, n + 1):
		for j in range(i):
			f[i][j] = f[i - 1][j]
			if j > 0:
				f[i][j] = (f[i][j] + f[i - 1][j - 1] * (m - 1)) % mod
	return f[n][k]
[n, m, k] = map(int, input().split())
result = colorful_bricks(n, m, k)
print(result)


def calc(n, k):
	return fact[n] * pow(fact[n - k] * fact[k], mod - 2, mod) % mod
mod = 998244353
(n, m, k) = map(int, input().split())
fact = [1]
for i in range(1, 2001):
	fact.append(fact[-1] * i % mod)
print(calc(n - 1, k) * m * pow(m - 1, k, mod) % mod)


import math
(n, m, k) = map(int, input().split())
M = 998244353
mf = math.factorial
print(mf(n - 1) // mf(n - 1 - k) // mf(k) * m * (m - 1) ** k % M)


def main():
	from math import factorial as fac
	(n, m, k) = map(int, input().split())
	ans = fac(n - 1) // (fac(n - 1 - k) * fac(k)) * m * (m - 1) ** k
	ans %= 998244353
	print(ans)
	return
main()


(n, m, k) = [int(x) for x in input().split()]
dp = [[0 for _ in range(k + 1)] for _ in range(n)]
dp[0][0] = m
for n1 in range(1, n):
	dp[n1][0] = m
for n1 in range(1, n):
	for k1 in range(1, k + 1):
		dp[n1][k1] = (dp[n1 - 1][k1] + dp[n1 - 1][k1 - 1] * (m - 1)) % 998244353
print(dp[n - 1][k])


Z = 998244353

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % Z
		den = den * (i + 1) % Z
	return num * pow(den, Z - 2, Z) % Z
(n, m, k) = list(map(int, input().split()))
print(ncr(n - 1, k) * m * pow(m - 1, k, Z) % Z)


def fastpowmod(a, b, mod):
	if b == 0:
		return 1
	r = fastpowmod(a, int(b / 2), mod)
	if b % 2:
		return r * r * a % mod
	else:
		return r * r % mod

def getcoefbezout(a, b):
	A = [[1, 0], [0, 1]]
	while b != 0:
		w = int(a / b)
		A[0][0] = A[0][0] - w * A[1][0]
		A[0][1] = A[0][1] - w * A[1][1]
		t1 = A[0][0]
		t2 = A[0][1]
		A[0][0] = A[1][0]
		A[0][1] = A[1][1]
		A[1][0] = t1
		A[1][1] = t2
		t = a
		a = b
		b = t % b
	return [A[0][0], A[0][1]]

def factmod(n, mod):
	r = 1
	for i in range(1, n + 1):
		r = r * i % mod
	return r

def inversemod(x, mod):
	r = getcoefbezout(x, mod)[0]
	r = (r % mod + mod) % mod
	return r

def combmod(n, k, mod):
	a = factmod(n, mod)
	b = factmod(n - k, mod)
	c = factmod(k, mod)
	b = inversemod(b, mod)
	c = inversemod(c, mod)
	r = a * b % mod * c % mod
	return r
t = 1
for i in range(t):
	X = input().split()
	n = int(X[0])
	m = int(X[1])
	k = int(X[2])
	if k == 0:
		print(m)
	elif m == 1:
		print(0)
	else:
		a = fastpowmod(m - 1, k, 998244353)
		b = combmod(n - 1, k, 998244353)
		cd = a * b % 998244353
		cd = cd * m % 998244353
		print(cd)


from math import factorial
(n, m, k) = list(map(int, input().split()))
if k == 0:
	print(m)
else:
	try:
		print(m * (m - 1) ** k * (factorial(n - 1) // (factorial(k) * factorial(n - k - 1))) % 998244353)
	except:
		print(0)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m, k) = map(int, input().split())
import math

def comb(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
ans = comb(n - 1, k) % 998244353
ans *= comb(m, 1) % 998244353
ans *= (m - 1) ** k % 998244353
print(ans % 998244353)


mod = 998244353

def nCrModp(n, r):
	C = [0 for i in range(r + 1)]
	C[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, r), 0, -1):
			C[j] = (C[j] + C[j - 1]) % mod
	return C[r]
(n, m, k) = map(int, input().split())
if m == 1 and k > 0:
	print(0)
else:
	ans = m
	ans = ans % mod * (pow(m - 1, k, mod) % mod) % mod
	val1 = nCrModp(n - 1, k)
	ans = ans % mod * (val1 % mod) % mod
	print(ans)


from math import factorial

def colorful_bricks():
	(n, m, k) = map(int, input().split())
	comb = factorial(int(n - 1)) // (factorial(int(k)) * factorial(int(n - 1 - k))) * m * (m - 1) ** k
	print(int(comb) % 998244353)
colorful_bricks()


stdin = lambda type_='int', sep=' ': list(map(eval(type_), input().split(sep)))
joint = lambda sep=' ', *args: sep.join((str(i) if type(i) != list else sep.join(map(str, i)) for i in args))

def binomial(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def solve(n, m, k):
	parts = m * pow(m - 1, k)
	return binomial(n - 1, k) * parts % 998244353
(n, m, k) = stdin()
print(solve(n, m, k))


import math

def modi(a, m):
	return pow(a, m - 2, m)
(n, m, k) = [int(x) for x in input().split()]
mod = 998244353
ans = 1
for i in range(k):
	ans *= (n - 1 - i) % mod
	ans = ans % mod
for i in range(1, k + 1):
	ans *= modi(i, mod) % mod
	ans = ans % mod
ans *= m
ans = ans % mod
ans *= pow(m - 1, k, mod) % mod
ans = ans % mod
print(ans)


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

def nCr(n, k):
	C = [0 for i in range(k + 1)]
	C[0] = 1
	for i in range(1, n + 1):
		j = min(i, k)
		while j > 0:
			C[j] = C[j] + C[j - 1]
			j -= 1
	return C[k]
answer = m * nCr(n - 1, k) * (m - 1) ** k
print(answer % MOD)


import sys, bisect
from math import floor, ceil
input = sys.stdin.readline
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
mod = 998244353

def inp():
	return int(input().rstrip())

def inlt():
	return list(map(int, input().rstrip().split()))

def insr():
	s = input().rstrip()
	return s[:len(s) - 1]

def invr():
	return map(int, input().rstrip().split())
(n, m, k) = invr()
result = m * pow(m - 1, k, mod) % mod
print(result * ncr(n - 1, k) % mod)


import sys
sys.setrecursionlimit(3000)

def fac(n):
	return 1 if n < 2 else n * fac(n - 1)

def choose(n, k):
	return fac(n) // (fac(k) * fac(n - k))
(n, m, k) = (int(s) for s in input().split(' '))
print(choose(n - 1, k) * m * (m - 1) ** k % 998244353)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *

def main():
	mod = 998244353
	(n, m, k) = map(int, input().split())
	f = [1]
	inf = [0] * (n + 1)
	for i in range(1, n + 1):
		f.append(f[-1] * i % mod)
	inf[-1] = pow(f[-1], mod - 2, mod)
	for i in range(n - 1, -1, -1):
		inf[i] = inf[i + 1] * (i + 1) % mod
	print(f[n - 1] * inf[n - k - 1] * inf[k] % mod * m * pow(m - 1, k, mod) % mod)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import setrecursionlimit
setrecursionlimit(2500)
d = dict()
LIMITE = 998244353

def rec(total, cores, dif):
	s = '%d %d' % (total, dif)
	if dif >= total:
		d[s] = 0
		return 0
	if total == 1:
		d[s] = cores
		return cores
	if s in d:
		return d[s]
	if dif == 0:
		d[s] = cores
		return cores
	sim_dif = (cores - 1) * rec(total - 1, cores, dif - 1) % LIMITE
	nao_dif = rec(total - 1, cores, dif)
	x = (sim_dif + nao_dif) % LIMITE
	d[s] = x
	return x
(n, m, k) = [int(x) for x in input().split(' ')]
for i in range(1, n):
	rec(i, m, i - 1)
print(rec(n, m, k))


dp = [[0 for j in range(2001)] for i in range(2001)]
(n, m, k) = map(int, input().split())
for i in range(1, n + 1):
	for j in range(k + 1):
		if j == 0 and i == 1:
			dp[i][j] = m
			continue
		if j <= i - 1:
			dp[i][j] = (m - 1) * dp[i - 1][j - 1] + dp[i - 1][j]
			dp[i][j] %= 998244353
print(dp[n][k])


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


from math import factorial
[n, m, k] = [int(i) for i in input().split()]
mod = 998244353
l = m * (m - 1) ** k
L = factorial(n - 1) // factorial(n - 1 - k) // factorial(k)
print(l * L % mod)


import sys
input = sys.stdin.readline
mod = 998244353
(n, m, k) = list(map(int, input().split()))
N = n - 1
INV = [None] * (n + 1)
for i in range(1, n + 1):
	INV[i] = pow(i, mod - 2, mod)
Combi = [None] * (N + 1)
Combi[0] = 1
for i in range(1, N + 1):
	Combi[i] = Combi[i - 1] * (N - i + 1) * INV[i] % mod
ANS = Combi[k] % mod * m % mod * pow(m - 1, k, mod) % mod
print(ANS)


(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
result = 1
k = k + 1
for i in range(k - 1):
	result *= n - 1 - i
	result //= 1 + i
result = result % 998244353
result *= m
for i in range(k - 1):
	result *= m - 1
result = result % 998244353
if result < 0:
	result += 998244353
print(result)


import sys
inf = float('inf')
mod = 998244353

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

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

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

def main():
	(n, m, k) = get_ints()
	dp[1][0] = m
	for i in range(1, n):
		for j in range(k + 1):
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod
			dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) * (m - 1) % mod
	print(dp[n][k])
dp = [[0 for _ in range(2005)] for _ in range(2005)]
main()


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

def combination_mod(k, n, mod):
	fact_k = 1
	for i in range(2, k + 1):
		fact_k = fact_k * i % mod
	fact_n = 1
	for i in range(2, n + 1):
		fact_n = fact_n * i % mod
	fact_n_k = 1
	for i in range(2, n - k + 1):
		fact_n_k = fact_n_k * i % mod
	return fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod) % mod
print(combination_mod(k, n - 1, mod) * m * pow(m - 1, k, mod) % mod)


import math
(n, m, k) = map(int, input().split())
ans = math.factorial(n - 1)
ans //= math.factorial(k)
ans //= math.factorial(n - 1 - k)
ans *= (m - 1) ** k
ans *= m
ans %= 998244353
if k == 0:
	ans = m
print(ans)


MOD = 998244353
(n, m, k) = map(int, input().split())
a = [1]
for _ in range(n - 1):
	a = [sum(x) % MOD for x in zip([0] + a, a + [0])]
print(m * pow(m - 1, k, MOD) * a[k] % MOD)


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
print(m * (m - 1) ** k * ncr(n - 1, k) % 998244353)


import sys
from math import ceil, floor, factorial
import operator as op
from functools import reduce
input = sys.stdin.readline

def ncr(n, r):
	f = factorial
	return f(n) // f(r) // f(n - r) % 998244353
(n, m, k) = map(int, input().split())
if k >= n:
	print(0)
	sys.exit(0)
colorings = m
for i in range(k):
	colorings *= m - 1
	colorings %= 998244353
print(int(ncr(n - 1, k) % 998244353 * colorings % 998244353) % 998244353)


MOD = 998244353
list_size = 2100
f_list = [1] * list_size
f_r_list = [1] * list_size
for i in range(list_size - 1):
	f_list[i + 1] = int(f_list[i] * (i + 2) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int(n * n % MOD), int(x / 2))
	else:
		return int(n * power(n, x - 1) % MOD)
f_r_list[-1] = power(f_list[-1], MOD - 2)
for i in range(2, list_size + 1):
	f_r_list[-i] = int(f_r_list[-i + 1] * (list_size + 2 - i) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return f_list[n - 1] * f_r_list[n - r - 1] % MOD * f_r_list[r - 1] % MOD
(n, m, k) = map(int, input().split())
print(m * (m - 1) ** k % MOD * comb(n - 1, k) % MOD)


import sys
MOD = 998244353
(n, m, k) = list(map(int, input().strip().split()))
memo = dict()

def C(n, m, k, first):
	if n == 0:
		if k == 0:
			return 1
		else:
			return 0
	if k == 0:
		if first:
			return m
		else:
			return 0
	if (n, m, k, first) in memo:
		return memo[n, m, k, first]
	vseh = 0
	if first:
		for i in range(n):
			vseh += m * C(i, m, k, False)
	else:
		for i in range(n):
			vseh += (m - 1) * C(i, m, k - 1, False)
	memo[n, m, k, first] = vseh % MOD
	return memo[n, m, k, first]

def C2(n, m, k):
	matrika = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
	matrika[0][0] = 1
	for j in range(1, k + 1):
		acc = 0
		for a in range(1, n + 1):
			acc += (m - 1) * matrika[j - 1][a - 1]
			matrika[j][a] = acc % MOD
	result = m * sum(matrika[k][:-1])
	return result % MOD
print(C2(n, m, k))


(n, m, k) = map(int, input().split(' '))
MOD = 998244353
dp = [[0] * (k + 1) for _ in range(n)]
dp[0][0] = m
for i in range(1, n):
	for j in range(min(i + 1, k + 1)):
		dp[i][j] = ((0 if j == 0 else dp[i - 1][j - 1] * (m - 1) % MOD) + dp[i - 1][j]) % MOD
print(dp[-1][-1])


from sys import stdin, stdout
import math
mod = 998244353
I = stdin.readline
P = stdout.write
(n, m, k) = map(int, I().split())
comb = math.factorial(n - 1) // math.factorial(n - 1 - k) // math.factorial(k)
comb %= mod
power = pow(m - 1, k, mod)
comb *= power
comb *= m
comb %= mod
P(str(comb) + '\n')


(n, m, k) = list(map(int, input().split()))
import math
a = math.factorial(n - 1) // (math.factorial(k) * math.factorial(n - 1 - k))
print(a * m * (m - 1) ** k % 998244353)


import math
(n, m, k) = map(int, input().split())
out = 1
for i in range(k):
	out *= m - 1
	out %= 998244353
out *= m
out %= 998244353
out *= math.factorial(n - 1) // math.factorial(k) // math.factorial(n - 1 - k)
out %= 998244353
print(out)


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import combinations
import sys
import math
MAX = sys.maxsize
MAXN = 10 ** 6 + 10
MOD = 998244353

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b, x, y):
	return abs(a - x) + abs(b - y)

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

def charIN():
	return sys.stdin.readline().strip().split()
t = [(-1, -1)] * 1000010

def create(a):
	global t, n
	for i in range(n, 2 * n):
		t[i] = (a[i - n], i - n)
	for i in range(n - 1, 0, -1):
		x = [t[2 * i], t[2 * i + 1]]
		x.sort(key=lambda x: x[0])
		t[i] = x[1]

def update(idx, value):
	global t, n
	idx = idx + n
	t[idx] = value
	while idx > 1:
		idx = idx // 2
		x = [t[2 * idx], t[2 * idx + 1]]
		x.sort(key=lambda x: x[0])
		t[idx] = x[1]

def dis(a, b, k):
	ans = 0
	for i in range(k):
		ans += abs(a[i] - b[i])
	return ans

def cal(n, k):
	res = 1
	c = [0] * (k + 1)
	c[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, k), 0, -1):
			c[j] = (c[j] + c[j - 1]) % MOD
	return c[k]
(n, m, k) = numIN()
x = cal(n - 1, k)
y = m
for i in range(k):
	y *= m - 1
	y %= MOD
x *= y
x %= MOD
print(x)


import math
(n, m, k) = [int(x) for x in input().split()]
if k == 0:
	ar = m
else:
	a = m * (math.factorial(n - 1) // (math.factorial(k) * math.factorial(n - 1 - k))) * (m - 1) ** k
	ar = a % 998244353
print(ar)


MOD = 998244353

def f(x):
	ans = 1
	for i in range(1, x):
		ans = ans * i
	return ans
(n, m, k) = map(int, input().split())
print(m * (m - 1) ** k * f(n) // f(k + 1) // f(n - k) % MOD)


import math
a = math.factorial
n = 998244353
(p, q, r) = map(int, input().split())
x = a(p - 1) // a(r) // a(p - r - 1) * q * (q - 1) ** r % n
print(x)


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


def fact(i):
	if i == 0:
		return 1
	if i < 0:
		return 0
	res = 1
	for t in range(1, i + 1):
		res *= t
	return res
(n, m, k) = map(int, input().split(' '))
if k >= n:
	print(0)
	exit(0)
print(fact(n - 1) // fact(k) // fact(n - k - 1) * m * (m - 1) ** k % 998244353)


data = input().split()
n = int(data[0])
m = int(data[1])
k = int(data[2])
K = 998244353
gt = [0 for i in range(2005)]
rev = [0 for i in range(2005)]

def mu(a, n):
	if n == 0:
		return 1
	q = mu(a, n // 2)
	if n % 2 == 0:
		return q * q % K
	return q * q % K * a % K
gt[0] = rev[0] = 1
for i in range(1, 2001):
	gt[i] = gt[i - 1] * i % K
	rev[i] = mu(gt[i], K - 2)
res = gt[n - 1] * rev[k] % K * rev[n - k - 1] % K
res = res * m % K
res = res * mu(m - 1, k) % K
print(res)


import os
import sys
from io import BytesIO, IOBase

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def factors(a):
	fact = []
	if a % 2 == 0:
		ch = 0
		while a % 2 == 0:
			ch += 1
			a //= 2
		fact.append([2, ch])
	i = 3
	while i * i <= a:
		if a % i == 0:
			ch = 0
			while a % i == 0:
				ch += 1
				a //= i
			fact.append([i, ch])
		i += 2
	if a > 1:
		fact.append([a, 1])
	return fact

def main():
	md = 998244353
	(n, m, k) = lin()
	dp = [[0 for j in range(k + 2)] for i in range(n + 1)]
	dp[1][0] = m
	for i in range(2, n + 1):
		for j in range(k + 1):
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % md
			dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j] * (m - 1)) % md
	print(dp[n][k])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
MOD = 998244353
(n, m, k) = list(map(int, input().split()))
res = pow(m - 1, k, MOD)
res = res * m % MOD
res = res * nCr(n - 1, k) % MOD
print(res)


import operator as op
from functools import reduce

def ncr(z, r):
	r = min(r, z - r)
	numer = reduce(op.mul, range(z, z - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
(n, m, k) = list(map(int, input().strip().split()))
mod = 998244353
if m == 1:
	if k == 0:
		print(1)
	else:
		print(0)
elif n == 1:
	print(m)
else:
	ans = m * (m - 1) ** k
	ans = ans % mod
	c = ncr(n - 1, k) % mod
	ans = ans * c
	ans = ans % mod
	print(ans)


from math import factorial
(n, m, k) = map(int, input().split())
M = 998244353
fn = 1
fnk1 = 1
fk = 1
for i in range(1, n):
	fn *= i
	fn %= M
for i in range(1, n - k):
	fnk1 *= i
	fnk1 %= M
for i in range(1, k + 1):
	fk *= i
	fk %= M
print(fn * pow(fnk1 * fk, M - 2, M) * m * pow(m - 1, k, M) % M)


from math import factorial as f
(n, m, k) = map(int, input().split())
ans = f(n - 1) // (f(n - k - 1) * f(k)) * m * (m - 1) ** k
print(int(ans % 998244353))


import math
f = math.factorial
(n, m, k1) = map(int, input().split())
print(f(n - 1) // f(k1) // f(n - k1 - 1) * m * (m - 1) ** k1 % 998244353)
for i in range(5):
	i += 1


M = 998244353

def f(k):
	r = 1
	for i in range(2, k + 1):
		r *= i
	return r
(n, m, k) = map(int, input().split())
print(f(n - 1) * pow(f(k) * f(n - k - 1), M - 2, M) * m * pow(m - 1, k, M) % M)


s = input()
s = s.split(' ')
n = int(s[0])
m = int(s[1])
k = int(s[2])
ans = 1
if k > 0:
	for i in range(n - k, n):
		ans = ans * i
	for i in range(1, k + 1):
		ans = ans // i
ans = ans * m
for i in range(k):
	ans = ans * (m - 1)
	pass
print(ans % 998244353)


mod = 998244353
(n, m, k) = map(int, input().strip().split())
dp = [0 for i in range(k + 1)]
dp[0] = m
for i in range(1, n):
	new_dp = list(dp)
	for j in range(1, k + 1):
		new_dp[j] = (new_dp[j] + dp[j - 1] * (m - 1)) % mod
	dp = new_dp
print(dp[-1] % mod)


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict, OrderedDict
import math
import heapq

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

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res // (i + 1)
	return res
(n, m, k) = listIn()
mod = 998244353
selection = nCr(n - 1, k) % mod
colors_ways = m * (m - 1) ** k % mod
total_ways = colors_ways * selection
print(total_ways % mod)


def ncr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
(n, m, k) = map(int, input().split())
mod = 998244353
a = ncr(n - 1, k)
if k >= 1:
	c = (m - 1) ** k
else:
	c = 1
c = c % mod
ans = a * m * c
print(ans % mod)


mod = 998244353
fac = [1]
for i in range(1, 2001):
	fac.append(fac[-1] * i % mod)

def fexp(x, y):
	ans = 1
	while y > 0:
		if y % 2 == 1:
			ans = ans * x % mod
		x = x * x % mod
		y //= 2
	return ans

def rev(x):
	return fexp(x, mod - 2)

def c(n, k):
	return fac[n] * rev(fac[n - k]) * rev(fac[k]) % mod
(n, m, k) = map(int, input().split(' '))
print(c(n - 1, k) * m * fexp(m - 1, k) % mod)


(n, m, k) = list(map(int, input().split()))
mod = 998244353
same_bricks = n - 1 - k
total = m
for i in range(k):
	total *= m - 1
	total %= mod
val = 1
for i in range(n - k, n):
	val *= i
for i in range(1, k + 1):
	val //= i
total *= val
total %= mod
print(total)


H = list(map(int, input().split()))
n = H[0]
m = H[1]
k = H[2]
a = 1
b = 1
c = 1
for i in range(1, n):
	a = a * i
for i in range(1, n - k):
	b = b * i
for i in range(1, k + 1):
	c = c * i
q = a // (b * c)
ans = q * m * (m - 1) ** k
print(ans % 998244353)


(n, m, k) = map(int, input().split())
if k == 0:
	print(m)
elif m == 1:
	print(0)
else:
	total1 = m * pow(m - 1, k) % 998244353
	total2 = 1
	for i in range(1, k + 1):
		total2 = total2 * (n - i)
	for i in range(1, k + 1):
		total2 = total2 // i
	t = total1 * total2 % 998244353
	print(t)


import math
(n, m, k) = map(int, input().split())
mod = 998244353
print(math.factorial(n - 1) % mod * m * pow(m - 1, k, mod) * pow(math.factorial(n - 1 - k) % mod * math.factorial(k) % mod, mod - 2, mod) % mod)


import os, sys
from io import BytesIO, IOBase
mod = 998244353
fac = [1]
for i in range(1, 2001):
	fac.append(fac[-1] * i % mod)
fac_in = [pow(fac[-1], mod - 2, mod)]
for i in range(2000, 0, -1):
	fac_in.append(fac_in[-1] * i % mod)
fac_in.reverse()

def comb(a, b):
	return fac[a] * fac_in[b] * fac_in[a - b] % mod

def main():
	(n, m, k) = map(int, input().split())
	print(m * pow(m - 1, k, mod) * comb(n - 1, k) % mod)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


m = list(map(int, input().split(' ')))
a = m[0]
b = m[1]
c = m[2]
ways = 1

def fact(n):
	a = 1
	for i in range(2, n + 1):
		a *= i
	return a

def p(r, n):
	return fact(n) // fact(r)

def entekhab(r, n):
	return p(r, n) // fact(n - r)
ways *= b
a -= 1
ways *= entekhab(c, a)
ways *= (b - 1) ** c
print(ways % 998244353)


(n, m, k) = map(int, input().split())
mod = 998244353
dp = [[0 for i in range(n)] for j in range(n)]
dp[0][0] = m
for i in range(1, n):
	for j in range(0, min(i + 1, k + 1)):
		if j == 0:
			dp[i][j] = dp[i - 1][j]
		elif j == i + 1:
			dp[i][j] = dp[i - 1][j] * (m - 1) % mod
		else:
			dp[i][j] = (dp[i - 1][j - 1] * (m - 1) + dp[i - 1][j]) % mod
print(dp[n - 1][k] % mod)


def power(x, y):
	res = 1
	while y != 0:
		if y & 1:
			res = res * x % mod
		x = x * x % mod
		y >>= 1
	return res
(n, m, k) = map(int, input().split())
mod = 998244353
jc = [1]
for i in range(n - 1):
	jc.append(jc[i] * (i + 1) % mod)
ans = jc[n - 1] * power(m - 1, k) % mod * m % mod
ans = ans * power(jc[k], mod - 2) % mod * power(jc[n - 1 - k], mod - 2) % mod
print(ans)


MOD = 998244353
(n, nColors, nDiff) = map(int, input().split())
dp = [[0 for _ in range(nDiff + 1)] for _ in range(n)]
dp[0][0] = nColors
for size in range(1, n):
	for cnt in range(nDiff + 1):
		dp[size][cnt] += dp[size - 1][cnt]
		dp[size][cnt] %= MOD
		if cnt - 1 >= 0:
			dp[size][cnt] += dp[size - 1][cnt - 1] * (nColors - 1) % MOD
			dp[size][cnt] %= MOD
print(dp[n - 1][nDiff])


import math
(n, m, k) = [int(x) for x in input().split()]
c_n_k = math.factorial(n - 1) // math.factorial(n - 1 - k) // math.factorial(k) % 998244353
c_n_k = c_n_k * (m % 998244353) % 998244353
c_n_k = c_n_k * ((m - 1) ** k % 998244353) % 998244353
print(int(c_n_k % 998244353))


def fact(n):
	q = 1
	for i in range(1, n + 1):
		q *= i
	return q
(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
com = fact(n - 1) // (fact(k) * fact(n - 1 - k))
dd = m * (m - 1) ** k
print(com * dd % 998244353)


def fact(n):
	if n == 0:
		return 1
	else:
		return fact(n - 1) * n

def C(n, k):
	return fact(n) // (fact(n - k) * fact(k))
(n, m, k) = map(int, input().split())
print(m * (m - 1) ** k * C(n - 1, k) % 998244353)


from math import factorial
(n, m, k) = [int(i) for i in input().split()]
modulo = 998244353
print(factorial(n - 1) // factorial(k) // factorial(n - k - 1) * m * (m - 1) ** k % modulo)


(n, m, k) = map(int, input().split())
mod = 998244353
t = 1
n -= 1
for i in range(n - k + 1, n + 1):
	t *= i
for j in range(1, k + 1):
	t //= j
for i in range(k):
	t *= m - 1
	t %= mod
print(m * t % mod)


from functools import lru_cache

@lru_cache(maxsize=None)
def bf(i, prv, kk, m, n, k):
	if i == n:
		if kk != k:
			return 0
		else:
			return 1
	ans = 0
	for j in range(m):
		if i == 0:
			ans += bf(i + 1, j, kk, m, n, k)
			continue
		if j != prv:
			ans += bf(i + 1, j, kk + 1, m, n, k)
		if j == prv:
			ans += bf(i + 1, j, kk, m, n, k)
	return ans

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def fact(x, p):
	if x == 0:
		return 1
	return x * fact(x - 1, p) % p

def fun(n, m):
	dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
	dp[0] = [1 for j in range(m + 1)]
	for i in range(n):
		for prev in range(m):
			val = dp[i][prev]
			dp[i + 1][0] += val
			dp[i + 1][m] -= val
			dp[i + 1][0] %= p
			dp[i + 1][m] += p
			dp[i + 1][m] %= p
		for j in range(1, m):
			dp[i + 1][j] += dp[i + 1][j - 1]
			dp[i + 1][j] += p
			dp[i + 1][j] %= p
		if i > 0:
			for j in range(m):
				dp[i + 1][j] -= dp[i][j]
				dp[i + 1][j] += p
				dp[i + 1][j] %= p
	return (dp[n][m - 1] + p) % p
p = 998244353
(n, m, k) = map(int, input().split())
ans = ncr(n - 1, k, p) * fun(k + 1, m) % p
print(ans)


from decimal import Decimal
import operator as op
from functools import reduce
import math

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom
(z, m, k) = input().split()
z = int(z)
m = int(m)
k = int(k)
p = 998244353
l = math.factorial(z - 1) // (math.factorial(k) * math.factorial(z - 1 - k))
pow = (m - 1) ** k
answer = int(Decimal(l * m * pow)) % p
print(answer)


MOD = 998244353

def bpow(a, b):
	sol = 1
	while b:
		if b & 1:
			sol *= a
			if sol >= MOD:
				sol %= MOD
		a *= a
		if a >= MOD:
			a %= MOD
		b >>= 1
	return sol
fac = []
fac += [1]
for i in range(1, 2001):
	fac.append(fac[i - 1] * i % MOD)
ifac = []
for i in range(0, 2001):
	ifac.append(bpow(fac[i], MOD - 2))

def nCr(a, b):
	return fac[a] * ifac[a - b] * ifac[b] % MOD
(n, m, k) = map(int, input().split())
print(nCr(n - 1, k) * m * bpow(m - 1, k) % MOD)


import sys
sys.setrecursionlimit(10000)
D = {(1, 0): 1, (1, 1): 0}
(n, m, k) = [int(x) for x in input().split()]

def f(n, k):
	if k == 0:
		return m
	if k >= n:
		return 0
	if (n, k) in D:
		return D[n, k]
	else:
		ans = (f(n - 1, k) + (m - 1) * f(n - 1, k - 1)) % 998244353
		D[n, k] = ans
		return ans
print(f(n, k))


l = list(map(int, input().strip().split()))
n = l[0]
m = l[1]
k = l[2]
mod = 998244353
soma = 0

def power_mod(base, power, mod):
	res = 1
	while power:
		if power % 2 == 1:
			res = res * base % mod
		base = base * base % mod
		power = power >> 1
	return res

def inverse(n, mod):
	return power_mod(n, mod - 2, mod)

def choose(n, r, mod):
	factorial = []
	factorial.append(1)
	for i in range(1, n + 1):
		factorial.append(i * factorial[i - 1] % mod)
	inverse_factorial = []
	for _ in range(n + 1):
		inverse_factorial.append(0)
	inverse_factorial[n] = inverse(factorial[n], mod)
	for i in range(n - 1, -1, -1):
		inverse_factorial[i] = (i + 1) * inverse_factorial[i + 1] % mod
	numerator = factorial[n]
	denominator_inverse = inverse_factorial[r] * inverse_factorial[n - r] % mod
	return numerator * denominator_inverse % mod
nGroups = k + 1
group_size_count = choose(n - 1, k, mod)
colour_distribution_count = m * power_mod(m - 1, nGroups - 1, mod) % mod
res = group_size_count * colour_distribution_count % mod
print(res)


from operator import mul
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(mul, range(n, n - r, -1), 1)
	denom = reduce(mul, range(1, r + 1), 1)
	return numer // denom

def mult(a, b):
	return a * b % mod
(n, m, k) = map(int, input().split())
mod = 998244353
ans = 1
ans = mult(ans, (m - 1) ** k)
ans = mult(ans, m)
ans = mult(ans, ncr(n - 1, k))
print(ans)


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
mod = 998244353
fact = [1] * 20001
ifact = [1] * 20001
for i in range(1, 1001):
	fact[i] = fact[i - 1] * i % mod
	ifact[i] = ifact[i - 1] * pow(i, mod - 2, mod) % mod

def ncr(n, r):
	return fact[n] * ifact[n - r] % mod * ifact[r] % mod

def npr(n, r):
	return fact[n] * ifact[n - r] % mod

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

def lcm(a, b):
	return a * b // math.gcd(a, b)

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def binsearch(arr, b, low, high):
	if low == high:
		return low
	if arr[math.ceil((low + high) / 2)] < b:
		return binsearch(arr, b, low, math.ceil((low + high) / 2) - 1)
	else:
		return binsearch(arr, b, math.ceil((low + high) / 2), high)

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s

def calc(n, m, r):
	s = 0
	for i in range(0, r + 1, 2):
		s += ncr1(n, i) * ncr1(m, i)
		s %= mod
	return s
mod1 = 998244353
t = int()
(n, m, k) = map(int, input().split())
if k > 0 and m == 1 or k >= n:
	print(0)
elif k == 0:
	print(m)
else:
	k1 = ncr1(n - 1, k)
	k1 *= pow(m - 1, k, mod1)
	k1 %= mod
	k1 *= m
	print(k1 % mod)


def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n - 1)

def combinations(n, k):
	return factorial(n) // (factorial(k) * factorial(n - k))

def main():
	(n, m, k) = map(int, input().split())
	print(combinations(n - 1, k) * m * (m - 1) ** k % 998244353)
main()


def fact(n):
	ans = 1
	for i in range(n, 0, -1):
		ans *= i
	return ans

def c_n_k(n, k):
	return fact(n) // (fact(k) * fact(n - k))
(n, m, k) = map(int, input().split())
print(c_n_k(n - 1, k) * (m - 1) ** k * m % 998244353)


s = input().split()
(n, m, k) = list(map(int, s))
MOD = 998244353
ans = m
for i in range(k):
	ans = ans * (m - 1) % MOD
if k > n // 2:
	k = n - 1 - k
for i in range(1, k + 1):
	ans = ans * (n - 1 - k + i) // i
print(ans % MOD)


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


import math
nmk = list(map(int, input().split()))
n = nmk[0]
m = nmk[1]
k = nmk[2]
val1 = math.factorial(n - 1) // (math.factorial(k) * math.factorial(n - 1 - k))
val2 = (m - 1) ** k * m
print(val1 * val2 % 998244353)


import sys
mod = 998244353
(bricks, colors, left) = map(int, input().split())
dp = [[0] * (left + 1) for i in range(bricks + 1)]
if left == 0:
	print(colors)
	sys.exit()
for i in range(1, bricks + 1):
	dp[i][0] = colors
for i in range(1, bricks + 1):
	for j in range(1, left + 1):
		dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (colors - 1)) % mod
print(dp[bricks][left] % mod)


import sys
sys.setrecursionlimit(1000000)
M = 998244353

def Qpow(x, y):
	if y == 0:
		return 1
	else:
		ret = Qpow(x, int(y / 2)) % M
		ret *= ret
		ret %= M
		if y % 2 == 1:
			ret *= x
			ret %= M
		return ret
(n, m, k) = map(int, input().split())
fact = [0 for i in range(0, 5005)]
fact[0] = 1
for i in range(1, 5002 + 1):
	fact[i] = fact[i - 1] * i % M
way = fact[k] * fact[n - 1 - k] % M
way = fact[n - 1] * Qpow(way, M - 2) % M % M
ans = way * (Qpow(m - 1, k) % M + M) * m % M
if ans < 0:
	ans += M
	ans %= M
print(ans)


MOD = 998244353

def pow(base, exp):
	if exp == 0:
		return 1
	if exp % 2 == 1:
		return pow(base, exp - 1) * base % MOD
	tmp = pow(base, exp // 2)
	return tmp * tmp % MOD

def inv_mod(x):
	return pow(x, MOD - 2)

def C(n, k):
	if k < n // 2:
		return C(n, n - k)
	result = 1
	for x in range(k + 1, n + 1):
		result = result * x % MOD
	for x in range(1, n - k + 1):
		result = result * inv_mod(x) % MOD
	return result
(n, m, k) = map(int, input().split())
print(m * C(n - 1, n - 1 - k) * pow(m - 1, k) % MOD)


(n, m, k) = list(map(int, input().split()))
d = [[0] * (k + 1) for _ in range(0, n + 1)]
MOD = 998244353
for i in range(1, n + 1):
	for j in range(0, k + 1):
		if j == 0:
			d[i][j] = m
		else:
			d[i][j] = (d[i - 1][j] + d[i - 1][j - 1] * (m - 1)) % MOD
print(d[n][k])


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
tmp = 998244353
(n, m, k) = lint()
print(nCr(n - 1, k) * m * (m - 1) ** k % tmp)


(n, m, k) = map(int, input().split())
import math
if m == 0 or k > n - 1:
	print('0')
	exit()
ans = 0
x = math.factorial(n - 1)
y = math.factorial(k)
z = math.factorial(n - 1 - k)
ans = x // (y * z)
x = 1
hell = 998244353
for i in range(k):
	x *= m - 1
print(m * x * ans % hell)


mod = 998244353

def comb(n, r):
	facn = 1
	for i in range(1, n + 1):
		facn = facn * i
	facr = 1
	for i in range(1, r + 1):
		facr *= i
	facnr = 1
	for i in range(1, n - r + 1):
		facnr *= i
	res = facn // (facnr * facr)
	res = res % mod
	return res
nmk = list(map(int, input().split()))
n = nmk[0]
m = nmk[1]
k = nmk[2]
res = comb(n - 1, k) * m * (m - 1) ** k % mod
print(int(res))


(n, m, k) = map(int, input().split())
comb = 1
power = 1
fact = 1
M = 998244353
for i in range(k):
	comb = comb * (n - 1 - i)
	power *= m - 1
	power = power % M
	fact *= k - i
print(comb // fact % M * m * (power % M) % M)