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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys

INF = 10 ** 17
MOD = 998244353

def main():
    n,m,kk = getList()

    k = m - 1
    ans = 0
    nck = 1
    rui = m
    for itr in range(1, n+1):
        if n - itr <= kk:
            
            ans += (rui*nck) % MOD
            ans %= MOD
            
        nck *= (n - itr)
        nck *= pow(itr, MOD-2, MOD)
        nck %= MOD
        rui *= k
        rui %= MOD
        
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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

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

MOD = 998244353

def mod(n):         
  return n % MOD

def modpow(a, n):   
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)
  
def inverse(a):     
  return modpow(a, MOD-2)

MAX = 1000000           
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     
  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 modcomb(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
combinit()          

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

Solution (Python):
import sys
import math  
import bisect  
import queue  
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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


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

    MOD = 998244353

    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)

    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

    E = [1]
    for _ in range(N):
        e = E[-1] * (M - 1)
        e %= MOD
        E.append(e)

    res = 0
    for k in range(0, K + 1):
        a = N - 1 - k

        b = cmb(N - 1, a, MOD) % MOD
        b *= M
        b %= MOD
        b *= E[a]
        b %= MOD

        res += b
        res %= MOD

    print(res)


if __name__ == '__main__':
    main()

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

P = mod
inv_t = [0]+[1]




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












MAX_N = N

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1) % mod)

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


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod


for i in range(K+1):
    ans += mod_comb_k(N-1, i, mod) * t[-1-i]


print(ans % mod)

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

mod = 998244353

def inved(a):
    x, y, u, v, k, l = 1, 0, 0, 1, a, mod
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % mod
fact = [1 for _ in range(N+M+1)]
invf = [1 for _ in range(N+M+1)]
for i in range(N+M):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(N+M, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
MM = [1 for _ in range(N+1)]
for i in range(1, N+1):
    MM[i] = ((MM[i-1] * (M - 1)) % mod)
S = (MM[N-1] * M) % mod
for i in range(K):
    S += (((fact[N-1] * invf[i+1] * invf[N-i-2]) % mod) * (M * MM[N-i-2])) % mod
    S %= mod
print(S)

Solution (Python):
n, m, k = map(int, input().split())
mod = 998244353
fac = [1 for _ in range(n+1)]
fac_inv = [1 for _ in range(n+1)]
memo = [1 for _ in range(n+1)]
for i in range(n):
    fac[i+1] = (fac[i] * (i+1)) % mod
    fac_inv[i+1] = pow(fac[i+1], mod-2, mod)
    memo[i+1] = memo[i] * (m-1) % mod

ans = 0
for i in range(0, k+1):
    ans = (ans + m * memo[n-i-1] * fac[n-1] * fac_inv[i] * fac_inv[n-i-1]) % mod

print(ans)

Solution (Python):
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
mod = 998244353
N, M, K = map(int, input().split())
x = [1]*N
for i in range(1,N):
    x[i] = Pow(i, mod-2)
cmb = [1]*N
for i in range(N-2):
    cmb[i+1] = ((cmb[i]*(N-1-i))%mod*x[i+1])%mod
ans = 0
for i in range(K+1):
    num = Pow(M-1, N-1-i)
    ans = (ans+M*num%mod*cmb[i]%mod)%mod
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
MOD=998244353
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

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

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

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

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def ma():
    return map(int,input().split())
def main():
    n,m,k=ma()
    
    ans=0
    for j in range(k+1):
        ans+=m*comb(n-1,j)%MOD *pow(m-1,(n-1-j),MOD)
        ans%=MOD
    print(ans)

main()

Solution (Python):
n,m,k = map(int,input().split())
mod = 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
p = 998244353
N = 2*10 ** 5 
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)
s = m
x = m
for i in range(k):
  s = (m*s)%p
for i in range(n-k-1):
  y = x*cmb(k+i,i,p)
  s = (m*s-y)%p
  x = (x*(m-1))%p
print(s)

Solution (Python):


def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 998244353
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  


def combination_mod(n, r, mod=MOD):
    
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


def ret_list_comb_r(n, r, mod=MOD):
    '''nC[0:r+1]を返す。for とかで再計算せずに済むように'''
    ret = [1]
    if r > n:
        raise ValueError('rがnより大きいけど大丈夫か？(0通り？)')
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
        ret.append(nf * pow(rf, mod - 2, mod) % mod)
    return ret


N, M, K = read_ints()
N_1C = ret_list_comb_r(N - 1, K)


def ret_ans_when_k(k):
    ret = M
    ret *= pow(M - 1, N - k - 1, MOD)
    ret %= MOD
    ret *= N_1C[k]  

    return ret % MOD


ans = 0
for i in range(0, K + 1):
    ans += ret_ans_when_k(i)
    ans %= MOD
print(ans)

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

def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer *= n - i
        denom *= k - i
    return numer * pow(denom, MOD-2, MOD) % MOD

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

print(ans)

Solution (Python):

MOD = 998244353
MAX = 2*10**5+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
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 C(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


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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n, m, k = LI()


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

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

print(ret % mod)

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

pattern = [1]*(N+1)
pattern[1] = M
for i in range(2,N+1):
    pattern[i] = pattern[i-1]*(M-1)
    pattern[i] %= mod
factorial = [1]*(N+1)
for i in range(1,N+1):
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod

ans = pattern[N]
for k in range(1,K+1):
    bunbo = factorial[N-1-k]*factorial[k]
    bunbo %= mod
    bunshi = pattern[N-k]*factorial[N-1]
    bunshi %= mod
    ans += (bunshi*pow(bunbo,mod-2,mod))%mod
    ans %= mod
print(ans)

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

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
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x

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

Solution (Python):

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


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

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

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 )

s = 0

for x in range(k+1):
    s += (m * power_func(m-1,n-1-x,998244353) * cmb(n-1,x,998244353)) % 998244353
    s %= 998244353
print(s)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    MODP = 998244353
    N, M, K = mis()
    if N==1:
        print(M)
        return
    fs = factorials_list(N, MODP)
    invs = invs_list(N, fs, MODP)
    ans = 0
    for k in range(K+1):
        p = k 
        q = (N-1) - p 
        perm = fs[p+q] * invs[p] * invs[q]
        t_ans = perm % MODP
        t_ans *= M
        t_ans %= MODP
        t_ans *= pow(M-1, q, MODP)
        t_ans %= MODP
        ans = (ans + t_ans) % MODP
    print(ans)


main()

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

if __name__ == "__main__":
    p = 998244353
    N = 2 *(10**5)  
    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)
    n = 1
    A = [1]
    ans = 0
    N,M,K = map(int,input().split())
    for i in range(N-1):
        n = n*(M-1)%p
        A.append(n)
    for i in range(K+1):
        a = A[N-1-i]*M % p
        b = cmb(N-1,i,p)
        ans = (ans +(a*b)%p)%p
    print(ans)

Solution (Python):
n, m, k = map(int, input().split())
MOD = 998244353
ans = 0
p = 1
px = 1
py = 1
for i in range(k + 1):
    x = m * pow(m - 1, n - 1 - i, MOD) % MOD
    ans += p * x % MOD
    ans %= MOD

    px *= pow(i + 1, MOD - 2, MOD)
    py *= n - i - 1
    px %= MOD
    py %= MOD
    p = px * py % MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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


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

p = 998244353
N = 2*10 ** 5  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

ans =0

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

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

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
elif K==N-1:
  print(powmod(M,N))
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

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

mod = 998244353
p = mod

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(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

initNCMMod(3 * (10**5))
def main():
    n, m, k = LI()
    if m == 1:
        if k >= n-1:
            print(1)
        else:
            print(0)
        return
    m1l = [0] * (n+1)
    m1l[0] = 1
    for i in range(n):
        m1l[i+1] = (m1l[i] * (m-1)) % p
    cnt = 0
    for l in range(k+1):
        x = (m1l[n-l] * m * inv[m-1]) % p
        x *= NCMMod(n-1, l)
        cnt += x
        cnt %= p
    print(cnt % p)




main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 998244353

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

comb = Combination(2 * 10 ** 5)

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

    if K == 0:
        ans = pow(M - 1, N - 1, mod) * M
        print(ans % mod)
        return

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



if __name__ == "__main__":
    main()

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

def calc(n, m):
    return (m * pow(m-1, n-1, MOD)) % MOD

C, ans = 1, calc(N, M)
for k in range(1, K+1):
    C = ((C * (N - k)) % MOD * pow(k, MOD-2, MOD)) % MOD
    ans = (ans + (C * calc(N-k, M)) % MOD) % MOD

print(ans)

Solution (Python):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


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

comb = Combination(10 ** 6, MOD)
ans = 0

for i in range(n + 1):
    same_cnt = n - i
    diff_cnt = i + 1
    if same_cnt > k:
        continue
    box = n - 1
    shikiri = box - same_cnt

    tmp = comb.combination(box, shikiri)

    
    tmp *= m * pow(m - 1, shikiri, MOD)
    
    ans += tmp
    ans %= MOD

print(ans % MOD)

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 998244353
N, M, K = map(int, input().split())
if (M == 1) and (K == (N-1)):
	print(1)
	sys.exit()
def cumprod(x, MOD = mod):
	L = len(x)
	Lsq = int(L**.5 + 1)
	x = np.resize(x, Lsq ** 2).reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		x[:,n] *= x[:,n-1]
		x[:,n] %= MOD
	for n in range(1,Lsq):
		x[n] *= x[n-1, -1]
		x[n] %= MOD
	return x.flatten()[:L]

def make_fact(U, MOD = mod):
	x = np.arange(U, dtype = np.int64)
	x[0] = 1
	fact = cumprod(x, MOD)
	x = np.arange(U, 0, -1, dtype = np.int64)
	x[0] = pow(int(fact[-1]), MOD - 2, MOD)
	fact_inv = cumprod(x, MOD)[::-1]
	return fact, fact_inv

fact, fact_inv = make_fact(N+10)


ans = 0
D = M * ((M-1) ** (N-1))
D %= mod
for i in range(K+1):
	if i == 0:
		ans += D
	else:
		d = fact[N-1]
		d *= fact_inv[i]
		d %= mod
		d *= fact_inv[N-1-i]
		d %= mod

		tmp = d * D
		tmp %= mod
		ans += tmp

	ans %= mod		
	D *= pow(M-1, mod-2, mod)
	D %= mod

ans %= mod

print(ans)

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

MOD = 998244353

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

c = [0 for _ in range(n)]
c[0] = 1
for i in range(1, n):
    c[i] = c[i - 1] * (n - i)
    c[i] *= inv(i, MOD)
    c[i] %= MOD
ans = sum([m * c[i] * pow(m - 1, n - 1 - i, MOD) for i in range(k + 1)]) % MOD
print(ans)

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

mod = 998244353

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

def make_tables(n, mod = 998244353):
    fac = [1, 1] 
    finv = [1, 1] 
    inv = [0, 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)
    return fac, finv

def nCk(n, k, mod = 998244353):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

fac, finv = make_tables(n)
cal = m
ans = 0
for i in range(n - 1 - k):
    cal *= m - 1
    cal %= mod
ans += cal * nCk(n - 1, k)
ans %= mod
for i in range(1, k + 1):
    cal *= (m - 1)
    cal %= mod
    ans += cal * nCk(n - 1, k - i)
    ans %= mod
print(ans)

Solution (Python):
MOD = 998244353
MAXN = 2*(10**5)+10
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod


N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
    tmp = pow(M-1, N-i-1, MOD) * M % MOD
    tmp *= nCr(N-1,i,MOD)
    ans += tmp % MOD
    ans %= MOD
print(ans)

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


class Combination:
    """
    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


mod = 998244353
total = 0
comb = Combination(n, mod)

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

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)

Solution (Python):
N, M, K = map(int, input().split())
MOD = 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) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
for k in range(K+1):
    ans += M * pow(M-1, N-1-k, MOD) * cmb(N-1, k, MOD)
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 + 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 += (pow(m-1,N-1-i,mod)*cmb(N-1,i,mod))% mod
    ans %= mod
print((m * ans)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 998244353
INF = float('inf')

class BinomialCoefficient(object):

    def __init__(self, N=210000, MOD=998244353):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

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

coef = BinomialCoefficient()

N, M, K = MI()
ans = 0
for l in range(K + 1):
    lans = pow(M - 1, N - l - 1, MOD)
    lans = M * lans % MOD
    lans = lans * coef.comb(N - 1, l) % MOD
    ans = (ans + lans) % MOD
print(ans)

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math



NN = 202020
MOD = 998244353

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


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


ans = 0
for i in range(1, k+2):
    ans = (ans + A[-i]*C(n-1, i-1))%MOD
    


print(ans)