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
MAXN = 200000+10
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

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

for i in range(K+1):
    tmp = M*pow(M-1, N-1-i, MOD)
    ans += comb(N-1, i)*tmp
    ans %= MOD

print(ans)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    N=2*10**5+3
    mod=998244353
    fac=[1]*(N+1)
    for i in range(1,N+1):
        fac[i]=fac[i-1]*i%mod
    inv_fac=[1]*(N+1)
    inv_fac[N]=pow(fac[N],mod-2,mod)
    for i in range(N-1,0,-1):
        inv_fac[i]=inv_fac[i+1]*(i+1)%mod
    def nCr(n,r):
        if n<0 or r<0 or r>n:
            return 0
        return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod
    n,m,k=map(int,input().split())
    m_mod=[1]
    for _ in range(n):
        m_mod.append(m_mod[-1]*(m-1)%mod)
    ans=0
    for i in range(k+1):
        ans_=nCr(n-1,i)*m%mod*m_mod[n-i-1]%mod
        ans=(ans+ans_)%mod
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
N,M,K=map(int,input().split())
pr=998244353
MAX_NUM = 2*10**5 + 5
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
for i in range(K+1):
    a=(a+M*pow(M-1,N-1-i,pr)*c(N-1,i))%pr
print(a)

Solution (Python):
mod=998244353




def find_power(n,mod):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 
def pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)



N,M,K=map(int,input().split())
dp=[0 for i in range(N+1)]

ans=M*pow(M-1,N-1,mod)

for i in range(1,K+1):
    ans+=M*combi(N-1,i,mod)*pow(M-1,N-1-i,mod)
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
MOD = 998244353
INF = 10 ** 15

MAXN = 200005
factorial = [1]
for i in range(1, MAXN + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (MAXN + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(MAXN)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

def fact(n):
    return factorial[n]%MOD

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n]*inv_factorial[n - k]*inv_factorial[k]%MOD

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

    ans = 0
    for i in range(K + 1):
        ret = nck(N - 1,i)*invs[i]%MOD
        ret *= invs[N - i - 1]*pow(M - 1,N - i - 1,MOD)%MOD
        ans += ret%MOD
        ans %= MOD
    ans *= pow(M,N,MOD)
    ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N,M,K  =Ints()

mod = 998244353





def make_bikkuri(N):
    bikkuri = [1]
    for i in range(1,N+1):
        bikkuri.append((bikkuri[-1]*i)%mod)
    return bikkuri

bikkuri = make_bikkuri(N)

def nCk(n,k):
    ans = bikkuri[n] * pow(bikkuri[k], mod-2, mod) * pow(bikkuri[n-k], mod-2, mod)
    return ans%mod


ans = 0

for i in range(K+1):
    ans += nCk(N-1,i)*pow(M-1,N-1-i,mod)
    ans %= mod
ans *= M
ans %= mod

print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 998244353; INF = float("inf")

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

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


def main():
	N, M, K = getlist()
	if N == 1:
		print(M)
		return

	Com = Combination(N - 1, con)
	ans = 0
	for i in range(N - 1 - K, N):
		ans += Com.com(N - 1, i) * pow(M - 1, i, con)
		ans %= con
	ans *= M
	ans %= con
	print(ans)


if __name__ == '__main__':
	main()

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

class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

c = Combination(n - 1, mod)
ans = 0
for i in range(k+1):
    ans += c.comb(n-1, i) * pow(m-1, n-i-1, mod) * m
    ans %= mod

print(ans)

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


def make_fact(n):
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) 
def make_fact_inv(n):
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)
def comb(n, k):
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

bekizyo = [1] * N

for i in range(1, N):
    bekizyo[i] = bekizyo[i-1] * (M - 1) % mod



ans = 0

for i in range(K + 1):
    ans += comb(N-1, i) * M * bekizyo[N-i-1]
    ans %= mod

print(ans)

Solution (Python):
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N, M, K = map(int, input().split())
    mod = 998244353
    c = cmbs(mod)
    r = 0
    for i in range(K+1):
        r += pow(M-1, N-1-i, mod) * c.cmb(N-1, i)
    r *= M
    r %= mod
    return r
print(main())

Solution (Python):
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M, K = LI()
    C = combination(N,mod2)
    ans = 0
    for i in range(N):
        if i>K:
            break
        cur = C.comb(N-1,i) * M * pow((M - 1), N - i - 1, mod2) % mod2
        
        ans += cur
        ans %= mod2
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
mod = 998244353
fact = [1]*(2*10**5+1)
for n in range(2*10**5):
    fact[n+1] = (n+1)*fact[n]
    fact[n+1] %= mod

factinv = [1]*(2*10**5+1)
for n in range(2*10**5):
    factinv[n+1] = pow(fact[n+1],mod-2,mod)

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

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

pm = [1]*(N+1)
for i in range(N):
    pm[i+1] = pm[i]*(M-1)%mod

ans = 0
for k in range(K+1):
    ans += M*pm[N-k-1]*comb(N-1,k)
    ans %= mod
print(ans)

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

fac = [0]*(n+1)
per = [0]*(n+1)

fac[0]=1
per[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    per[i] = pow(fac[i],mod-2,mod)

def nCk(n,k):
    return fac[n]*per[k]%mod*per[n-k]%mod

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

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

if M==1:
    print(1 if K==N-1 else 0)
    exit()

mod = 998244353

f = [0]*N
f[0] = p = 1
for i in range(1,N):
    f[i] = p = p*i%mod

finv = [0]*N
finv[N-1] = p = pow(f[N-1],mod-2,mod)
for i in range(N-2, -1, -1):
    finv[i] = p = p*(i+1)%mod

ans = 0
for k in range(K+1):
    x = M * pow(M-1, N-k-1, mod) % mod
    y = (f[N-1]*finv[N-1-k]%mod)*finv[k]%mod
    ans = (ans + x*y%mod)%mod

print(ans)

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+1
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

print(ans)

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    mod = 998244353

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

    
    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod
    
    
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    for i in range(k+1):
        temp = pow(m-1, n-i-1, mod)
        temp = temp * m % mod
        res += ncr(n-1, i) * temp
        res %= mod
    print(res)



if __name__ == '__main__':
    main()

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

MAX = 2 * 10**5 + 5
fact = [1] * (MAX + 1)  
finv = [1] * (MAX + 1)  
iinv = [1] * (MAX + 1)  
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


mm = [1]
for j in range(n):
    mm.append((mm[-1] * (m - 1)) % MOD)

dp = [(comb(n - 1, j) * m * mm[n - 1 - j]) % MOD for j in range(k + 1)]


ans = sum(dp) % MOD
print(ans)

Solution (Python):
N,M,K = map(int,input().split())
MOD = 998244353
if M==1:
    print(1 if K==N-1 else 0)
    exit()

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

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

cs = []
ms = [(M * pow(M-1, N-1-K, MOD)) % MOD]
for i in range(K+1):
    cs.append(comb(N-1, i))
    if i:
        ms.append((ms[-1] * (M-1)) % MOD)

ans = 0
for c,m in zip(cs, ms[::-1]):
    ans += c*m
print(ans%MOD)

Solution (Python):
U = 2*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float("INF")
fact = [i for i in range(2 * 10 ** 5 + 1)]
fact[0] = 1
for i in range(2 * 10 ** 5):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod
invfact = [None] * (2 * 10 ** 5 + 1)
invfact[-1] = pow(fact[-1], mod - 2, mod)
for i in range(2 * 10 ** 5, 0, -1):
    invfact[i - 1] = invfact[i] * i
    invfact[i - 1] %= mod
def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = fact[n]
    b = invfact[k]
    c = invfact[n - k]
    return (a * b * c) % mod

def solve():
    n, m, k = LI()
    if m == 1:
        if n == k + 1:
            print(1)
            return

        else:
            print(0)
            return
    ans = 0
    tmp = m
    for i in range(n - 1):
        tmp *= m - 1
        tmp %= mod
    for i in range(k + 1):
        ans += tmp * combination_mod(n - 1, i, mod)
        tmp *= pow(m - 1, mod - 2, mod)
        tmp %= mod
        ans %= mod
    print(ans)
    return



if __name__ == '__main__':
    solve()

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

UPPERLIMIT=2*10**5+1
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

ans=0
for i in range(K+1):
  ans+=M*pow(M-1, N-1-i, MOD)*MODCOMB(N-1, i)%MOD
  ans%=MOD
  
print(ans)

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

mod = 998244353

fac = [1]
inv = [1]
for i in range(1, N + 10) :
  fac.append(fac[-1] * i % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

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

Solution (Python):
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


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

ans = 0
for s in range(k + 1):
    p = n - s
    ans = (ans + m * pow(m - 1, p - 1, MOD) * facts[n - 1] * invs[s] * invs[n - s - 1]) % MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 998244353
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N + M, mod)

dp = [0] * (N + 1)
dp[1] = M
for i in range(1, N):
  dp[i + 1] = dp[i] * (M - 1)
  dp[i + 1] %= mod

res = 0
for i in range(K + 1):
  res += dp[N - i] * f.combi(N - 1, i) % mod
  res %= mod
print(res)

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
if m == 1:
  if k == n-1:
    print(1)
  else:
    print(0)
  exit()
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y

now = int(m)
for _ in range(n-1):
  now *= m-1
  now %= mod
ans = int(now)
for i in range(k):
  now *= inv(m-1)
  now *= n-1-i
  now *= inv(i+1)
  now %= mod
  
  ans += now
  ans %= mod
print(ans)

Solution (Python):
n,m,k = map(int, input().split())
mod = 998244353
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)

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

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

ans *= m
ans %= mod
print(ans)

Solution (Python):
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18

MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, M, K = list(map(int, sys.stdin.buffer.readline().split()))
















comb = Combination(max=max(N, M, K) + 100, mod=MOD)
ans = 0
for k in range(K + 1):
    ans += pow(M - 1, N - 1 - k, MOD) * comb.ncr(N - 1, k)
    ans %= MOD
print(ans * M % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 998244353

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

ans = [0] * (K + 1)
ans[0] = M

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

C = Factorial(N + 1, MOD).comb

ans = 0
m = M - 1
for i in range(K + 1):
    tmp = C(N - 1, i)
    tmp = (tmp * pow(m, N - 1 - i, MOD)) % MOD
    ans += tmp
    ans %= MOD

ans *= M
ans %= MOD

print (ans)

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

    return r % mod

print(main())

Solution (Python):
SIZE=200001; MOD=998244353 

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

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



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

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

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

print(ans%MOD)

Solution (Python):


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


N, M, K = LI()

MOD = 998244353
MAX = 10 ** 6
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    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] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    pm = [None] * N
    pm[0] = 1
    for i in range(1, N):
        pm[i] = pm[i - 1] * (M - 1) % MOD
    
    ans = 0
    for k in range(K + 1):
        x = comb(N - 1, k) * M * pm[N - k - 1] % MOD
        ans = (ans + x) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter, defaultdict, deque

N, M, K = [int(x) for x in input().split()]
MOD = 998244353


def modInverse(a, p):
    
    return pow(a, p - 2, p)



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


def nCr(n, r, p=MOD):
    
    return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


total = 0
for i in range(K + 1):
    total += nCr(N - 1, i) * M * pow(M - 1, N - i - 1, MOD)
    total %= MOD
print(total)

Solution (Python):
MOD = 998244353

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

fac = [1]*(n+1)
fac_inv =  [0]*(n+1)

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

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

print(ans)

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

m = 2*(10**5) +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

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

Solution (Python):
MOD = 998244353

fact = [0] * 220000
invfact = [0] * 220000

fact[0] = 1
for i in range(1, 220000):
    fact[i] = fact[i-1] * i % MOD

invfact[220000 - 1] = pow(fact[220000 - 1], MOD-2, MOD)

for i in range(220000 - 2, -1, -1):
    invfact[i] = invfact[i+1] * (i+1) % MOD

def nCk(n, k):
    if k < 0 or n < k:return 0
    return fact[n] * invfact[k] * invfact[n-k] % MOD



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

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

Solution (Python):
nn = 200200
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
    exit()
ans = 0
t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
for i in range(K+1):
    ans = (ans + t * C(N-1, i)) % P
    t = t * m % P
print(ans * M % P)

Solution (Python):
lim, mod = 3*10**5, 998244353
n, m, k = map(int, input().split())
ifac, fac = [1], [1]
for i in range(1, lim):
    fac.append((fac[-1]*i)%mod)
    ifac.append(1)
ifac[-1] = pow(fac[-1], mod-2, mod)
for i in range(1, lim-1):
    ifac[lim-1-i] = (ifac[lim-i] * (lim-i))%mod
pw = [1]
for i in range(1, lim):
    pw.append((pw[-1]*(m-1))%mod)
def C(n, k):
    r = fac[n] * ifac[k]
    r %= mod
    r *= ifac[n-k]
    return r%mod

ans = 0
for i in range(k+1):
    
    N = n - i
    add = C(n-1, i) * m
    add %= mod
    add *= pw[N-1]
    add %= mod
    ans += add
    ans %= mod
print(ans)