Problem:
 Score : 500 points    Problem Statement 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 1 3 2 1      Sample Output 1 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.       Sample Input 2 100 100 0      Sample Output 2 73074801       Sample Input 3 60522 114575 7559      Sample Output 3 479519525

Solution (Python):




mod = 998244353

class COM:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
        self.fac = [0] * (n+1)
        self.finv = [0] * (n+1)
        self.inv = [0] * (n+1)
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, n+1):
            self.fac[i] = self.fac[i-1] * i % MOD
            self.inv[i] = MOD - self.inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % MOD

    def calc(self, k):
        if k < 0:
            return 0
        return self.fac[self.n] * (self.finv[k] * self.finv[self.n-k] % self.MOD) % self.MOD

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

    
    if N > 1:
        cmbclass = COM(N-1, mod)
        cmb = cmbclass.calc
    else:
        cmb = lambda x:1
    res = 0
    for i in range(K+1):
        res += M * cmb(i) % mod * pow(M-1, N-i-1, mod)


    print(res % mod) 


if __name__ == "__main__":
    main()

Solution (Python):
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 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)


if __name__ == '__main__':
    main()

Solution (Python):
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 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)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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)

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

mod = 998244353
class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size
        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % mod) % mod

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

ans = 0
m = M
comb = Combination(N)
for k in reversed(range(N)):
    now = m
    now *= comb.ncr(N - 1, k)
    now %= mod
    if k <= K:
        ans += now
        ans %= mod
    m *= M - 1
    m %= mod

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,n+10):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,n+10):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,n+10):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,n+10):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]*m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]*m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%=mod
		cnt*=m*mp[n-kk-1]
		cnt%=mod
		ans+=cnt
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
import sys

input=sys.stdin.buffer.readline





def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))




def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%=mod
		cnt*=m*mp[n-kk-1]
		cnt%=mod
		ans+=cnt
	print(ans%mod)













if __name__=="__main__":
	main()

Solution (Python):
def COMinit():
    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

def COM(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

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

max = max(N,2) 
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Solution (Python):
def COMinit():
    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

def COM(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

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

max = N + 1
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Solution (Python):
def COMinit():
    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

def COM(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

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

max = N + M + K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

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

MAX = 10**6
def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 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
    return fac, finv, inv



def comb(n, k):
    """
    nCk mod MODを求める.
    この部分はO(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)


fac, finv, inv = COMinit()
ans = 0
for L in range(N-K, N+1):
    tmp = M*pow(M-1, L-1, MOD)%MOD
    tmp *= comb(N-1, L-1)
    ans += tmp % MOD
    ans %= MOD
print(ans%MOD)

Solution (Python):
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)

Solution (Python):
mod=998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
 
    def calc(self, n, k):  
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

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

C=Combination(N)
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%mod
for i in range(K+1):
    tmp=M*c[N-i-1]*C.calc(N-1,N-i-1)%mod
    ans=(ans+tmp)%mod
print(ans)

Solution (Python):
from functools import reduce

def cin():  return list(map(int,input().split()))
N, M, K = cin()
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 cmb(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 * cmb(N - 1, i) * pow(M - 1, N - 1 - i, MOD)
    ans %= MOD
print(ans)

Solution (Python):
N, M, K = map(int, input().split())
kMod = 998244353







ans = 0
for i in range(N):
    if i == 0:
        acc = M
    else:
        acc *= (M-1)
        acc %= kMod
        acc *= (N-i)
        acc %= kMod
        acc *= pow(i, kMod-2, kMod)
        acc %= kMod
    if i >= N-K-1:
        ans += acc
        ans %= kMod
print(ans)

Solution (Python):
MOD = 998244353
factorial = None
inverse_factorial = None


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    global factorial, inverse_factorial
    factorial = [1]*(max_n+1)
    inverse_factorial = [0]*(max_n+1)
    for i in range(1, max_n+1):
        factorial[i] = (factorial[i-1]*i)%MOD
        inverse_factorial[i] = modpow(factorial[i], MOD-2)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

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)

if __name__ == '__main__':
    Main()

Solution (Python):
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)

Solution (Python):
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


def paint(k):
    res = (m * comb(n-1, k)) % mod * pow(m-1, n-1-k, mod)
    res %= mod
    return res

ans = 0
for k in range(K+1):
    ans += paint(k)
    ans %= mod
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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

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

N = 10**5 * 2  
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)

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

N = 10**5 * 2  
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):




from math import factorial
N, M, K = map(int, input().split())
p = 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) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0

for k in range(K + 1):
    tmp = M * cmb(N - 1, k, p) * pow(M - 1, N - k - 1, p)
    ans += tmp % p

ans = ans % p
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
mod = 998244353

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

N, M, K = getNM()













ans = 0
for k in range(K + 1):
    opt = M * cmb(N - 1, N - k - 1) * pow(M - 1, N - k - 1, mod)
    ans += opt
print(ans % mod)

Solution (Python):
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))%mod
for i in range(1,k+1):
    ans +=cmb(n-1,i,mod)*m*pow(m-1,n-1-i,mod)
    ans %=mod
print(ans)

Solution (Python):
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)

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

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 = n 
g1 = [0]*(N+1) 
g1[0] = g1[1] = 1
g2 = [0]*(N+1) 
g2[0] = g2[1] = 1
inverse = [0]*(N+1) 
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod


ans = 0
for i in range(k+1):
    ans += m * cmb(n-1,i,mod) * pow(m-1,n-1-i,mod)
    ans %= mod
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n, r):
    return fact[n] * pow(fact[n-r], mod-2, mod) * pow(fact[r], mod-2, mod) % mod

n, m, k = LI()
fact = [1] * (n+1)
for i in range(1, n+1):
    fact[i] = fact[i-1] * i
    fact[i] %= mod

ans = 0
for i in range(k+1):
    ans += C(n-1, i) * m * pow(m-1, n-1-i, mod)
    ans %= mod
print(ans)