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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

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

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

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


N, M, K = MAP()

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

def power(x, n, p):
	ans = 1
	while n:
		if n%2:
			ans = ans*x%p
		x = x*x%p
		n >>= 1
	return ans

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

fact_inv = [1]*(lim+1)
fact_inv[lim] = power(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

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


N, M, K = MAP()

ans = 0
for i in range(K+1):
	a = M*power(M-1, N-1-i, mod)%mod*C(N-1, i)%mod
	ans = (ans+a)%mod

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

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

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

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


N, M, K = MAP()

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

print(ans)

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

Solution (Python):
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

    def mod_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

    ans = 0
    power = M % MOD
    for k in range(N - 1, -1, -1):
        if k <= K:
            ans += mod_com(N - 1, k) * power % MOD
        power = power * (M - 1) % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

n,m,k = myinput()
mod = 998244353

comb = Combination(n,mod)

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

Solution (Python):
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

    def mod_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

    ans = 0
    power = M % MOD
    for k in range(N - 1, -1, -1):
        if k <= K:
            ans += mod_com(N - 1, k) * power % MOD
        power = power * (M - 1) % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def comb_mod_faster(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k = min(n-k,k)
    ans = 1
    inv = [1]*(k+1)
    if k>=1:
        ans *= (n-k+1)%mod
    for i in range(2,k+1):
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        ans = ans*(n-k+i)*inv[i]%mod
    return ans

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

def make_comb_mod_list(n,mod):
    r = n
    ls = [0]*(n+1)
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    ls[0] = 1
    ls[1] = n
    for i in range(2, n + 1):
        fac.append(fac[-1] * i % mod)
        inv.append(-inv[mod % i] * (mod // i) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
        ans = int(fac[n] * finv[r] * finv[n - r] % mod)
        ls[i] = ans
    return ls




def combination_list(n, mod=10**9+7):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst

def power_func(a,n,p):
    bi = str(format(n,"b"))
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i]=="1":
            res = (res*a) % p
    return res

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

n,m,k = myinput()
mod = 998244353

comb = Combination(n,mod)

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

Solution (Python):

import sys
from functools import reduce
from operator import mul

MOD = 998244353  

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


def combinations_count(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 solve(N: int, M: int, K: int):
    SUM = ModInt(0)
    n_1Ck = [ModInt(1) for k in range(K + 1)]
    for i in range(1, K + 1):
        n_1Ck[i] = n_1Ck[i-1] * (N-i) / i
    for k in range(0, K + 1):
        SUM += M * n_1Ck[k] * (pow(M - 1, N - 1 - k, MOD))
    print(SUM)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, M, K)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











MOD = 998244353
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
N,M,K = map(int,input().split())
for i in range(2, N+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
s = 0
for i in range(K+1):
    s += M*pow(M-1,N-1-i,MOD)*comb_mod(N-1,i,MOD)
    s %= MOD
print(s%MOD)

Solution (Python):
N, M, K = [int(_) for _ in input().split()]

MOD = 998244353
L = 200001

Fm = {}

inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % MOD

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], MOD - 2, MOD)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % MOD
    return result

result = 0


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

print(result)

Solution (Python):
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    MOD = 998244353
    ans = 0
    comb = Combination(1000000, MOD)

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

    print(ans)

Solution (Python):
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]

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


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

print(ans)

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

def bin(a, b, p):
    res = 1
    while b > 0:
        if b & 1 > 0:
            res = res * a % p
        a = a * a % p
        b >>= 1

    return res

MOD = 998244353
N = 200000 + 50
f = [0 for i in range(N)]
invf = [0 for i in range(N)]

f[0] = invf[0] = 1
for i in range(1, N):
    f[i] = f[i-1] * i % MOD

invf[n] = bin(f[n], MOD-2, MOD)
for ri in range(1, N-1):
    i = n - ri
    invf[i] = invf[i+1] * (i+1) % MOD

def binom(n, m):
    if n < m or n < 0 or m < 0:
        return 0
    return f[n] * invf[m] % MOD * invf[n-m] % MOD

def g(n, m):
    return m * bin(m-1, n-1, MOD)

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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

def main():
    mod=998244353
    N,M,K=MI()
    
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
        
    p=[1]*(N+3)
    for i in range(N+2):
        p[i+1]=(p[i]*(M-1))%mod
        
    ans=0
    for i in range(K+1):
        temp=M*p[N-1-i]*cmb(N-1,i,mod)
        temp%=mod
        ans=(ans+temp)%mod
        
    print(ans)

main()

Solution (Python):

import sys
readline = sys.stdin.readline

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




MOD = 998244353

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

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

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m


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

print(ans)

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

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

def power_func(a, n, p):
    bi = str(format(n,"b"))
    if a == 0:
        return 0
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res

P = 998244353
inv_t = [0] + [1]
for i in range(2, max(M,K)+2):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

Solution (Python):
import sys

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """

    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

mod = 998244353
ans = 0

comb = Combination(2*10**5)


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

print(ans)

Solution (Python):
n,m,k = map(int,input().split())
def nCr(n,r,fac,finv):
    mod = 998244353
    ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    return ans
ans = 0
mod = 998244353
fac = [1,1]+[0]*n
finv = [1,1]+[0]*n
inv = [1,1]+[0]*n
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod%i] * (mod//i) % mod
    finv[i] = finv[i-1] * inv[i] % mod
for i in range(k+1):
    ans += m*pow(m-1,n-1-i,mod)*nCr(n-1,i,fac,finv) % mod
    ans %= mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def extgcd1(a0,b0):
    u=1
    v=0
    a=a0
    b=b0
    while b:
        t=a//b
        a-=t*b
        a,b=b,a
        u-=t*v
        u,v=v,u
    if a!=1: 
        
        return -1
    return u%b0 

def main():
    mod =998244353
    

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

    
    
    
    
    
    
    
    
    
    
    

    
    
    

    
    
    
    
    ans=0
    c0=1
    c1=pow(M-1,N-1,mod)
    inv=[1,1]+[extgcd1(i,mod) for i in range(2,N)]
    
    ifac=[1]*(N)
    nfac=1
    for i in range(1,N):
        nfac=(i*nfac)%mod
        ifac[i]=(ifac[i-1]*inv[i])%mod
    
    
    
    
    mp=[1]*(N)
    for i in range(1,N):
        mp[i]=(mp[i-1]*(M-1))%mod
    
    ans=0
    
    
    
    for k in range(0,K+1):
        
        ans=ans+(mp[N-1-k]*nfac*ifac[k]*ifac[N-1-k])%mod
        ans%=mod
        
    
    ans=(ans*M)%mod
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def extgcd1(a0,b0):
    u=1
    v=0
    a=a0
    b=b0
    while b:
        t=a//b
        a-=t*b
        a,b=b,a
        u-=t*v
        u,v=v,u
    if a!=1: 
        
        return -1
    return u%b0 

def main():
    mod =998244353
    

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

    
    
    
    
    
    
    
    
    
    
    

    
    
    

    
    
    
    
    ans=0
    c0=1
    c1=pow(M-1,N-1,mod)
    inv=[1,1]+[pow(i,mod-2,mod) for i in range(2,N)]
    
    ifac=[1]*(N)
    nfac=1
    for i in range(1,N):
        nfac=(i*nfac)%mod
        ifac[i]=(ifac[i-1]*inv[i])%mod
    
    
    
    
    mp=[1]*(N)
    for i in range(1,N):
        mp[i]=(mp[i-1]*(M-1))%mod
    
    ans=0
    
    
    
    for k in range(0,K+1):
        
        ans=ans+(mp[N-1-k]*nfac*ifac[k]*ifac[N-1-k])%mod
        ans%=mod
        
    
    ans=(ans*M)%mod
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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

    
    

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

    def C(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0:
            return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  
        if n == k:
            return 1
        if k == 0:
            return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  
        if n == k:
            return 1  
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  
        if n == 0:
            return 1
        if n % 2 and n >= 3:
            return 0  
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  
        
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


n, m, k = map(int, read().split())
mod = 998244353
comb = Combination(n, mod)
ans = 0
n -= 1
for i in range(k + 1):
    ans += comb.C(n, n - i) * m * pow(m - 1, n - i, mod) % mod
    ans %= mod
print(ans)

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