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: interview

Starter code:

Solutions:
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)

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)

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)


import sys
input = sys.stdin.readline
mod=998244353

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

N=n-1
INV=[None]*(n+1)#1/aのリストを予め作っておく.
for i in range(1,n+1):
    INV[i]=pow(i,mod-2,mod)

#nCkは、nもしくはkが固定の場合はリストで作る

Combi=[None]*(N+1)#Combi[i]=nCi を表す
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)


import math

def modi(a,m) : 
	return pow(a,m-2,m)


def __starting_point():

	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)




__starting_point()

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 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)

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 = list(map(int, input().split()))
mod = 998244353
dp = [[0] * (k + 1) for i in range(n)]
dp[0][0] = m
for i in range(1, n):
    for j in range(k + 1):
        dp[i][j] = dp[i - 1][j]
        if j > 0:
            dp[i][j] += dp[i - 1][j - 1] * (m - 1)
        dp[i][j] %= mod
print(dp[n-1][k])


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)


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)


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)

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)


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

same_bricks = n - 1 - k
total = m # First brick
# Different bricks
for i in range(k):
	total *= (m-1)
	total %= mod

# Choosing same bricks
# times (n-1 choose k)
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)


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)

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        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())     #idle 中不会执行 atexit

    
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   # same

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)
#comb(n0 + m0 -1, m0-1)
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)
    





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)

MOD = 998244353
n, m, k = list(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)


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

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

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

n = int(n)
m = int(m)
k = int(k)

# Taken from https://www.geeksforgeeks.org/binomial-coefficient-dp-9/
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)


'''input
3 2 1
6 3 2
5 3 0
3 3 1
3 3 0
'''
n, m, k = list(map(int, input().split()))
MOD  = 998244353
ans = m * pow(m - 1, k, MOD) % MOD
'''
for i in range(k + 1):
	if i & 1:
		ans -= m * pow(m - 1, k - i, MOD)
	else:
		ans += m * pow(m - 1, k - i, MOD)
'''


for i in range(n - k, n):
	ans = ans * i
for i in range(n - k, n):
	# print(n - 1 - i)
	ans = ans // (n - i)
'''
for i in range(1, k + 1):
	print(ans)
	ans = ans * (n - 1 - i) * pow(i, MOD - 2, MOD) % MOD
'''
print(ans % MOD)



mod=998244353
def nCrModp(n, r): 
  
    # The array C is going to store last row of 
    # pascal triangle at the end. And last entry 
    # of last row is nCr. 
    C = [0 for i in range(r+1)] 
  
    C[0] = 1 # Top row of Pascal Triangle 
  
    # One by constructs remaining rows of Pascal 
    # Triangle from top to bottom 
    for i in range(1, n+1): 
  
        # Fill entries of current row  
        # using previous row values 
        for j in range(min(i, r), 0, -1): 
  
            # nCj = (n - 1)Cj + (n - 1)C(j - 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
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 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)
    return

colorings = m
for i in range(k):
    colorings *= (m-1)
    colorings %= 998244353 

print(int(((ncr(n-1, k) % 998244353) * colorings) % 998244353) % 998244353)