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 cmb(n, k, mod, fac, ifac):    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

n,m,k = map(int,input().split())
f=[0 for _ in range(n)]
mod=998244353
for i in range(n):
    if i == 0:
        f[i]=m
    else:
        f[i]=(f[i-1]*(m-1))%mod
c=1
ans=0
if k==0:
    print(f[n-1])
    exit()
fac, ifac = make_tables(mod, n)
for i in range(k+1):
    ans+=f[n-1-i]*c
    ans%=mod
    
    
    c=cmb(n-1,i+1,mod,fac,ifac)

print(ans%mod)

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

def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
dp = [0]*(k+1)
dp[0] = m* modpow(m-1, n-1, MOD) % MOD
bunsi = 1
bunbo = 1
for j in range(1, k+1):
  bunsi = bunsi * (n-j) % MOD
  bunbo = bunbo * j % MOD

  comb = bunsi * modpow(bunbo, MOD-2, MOD) % MOD
  dp[j] = (m * modpow(m-1, n-1-j, MOD)*comb % MOD + dp[j-1]) % MOD
print(dp[k])

Solution (Python):
from functools import reduce
mod = 998244353

N, M, K = map(int, input().split())
C = 1
ans = (M*pow(M-1, (N-1), mod))%mod
k = 1
while k <= K and k < N:
  C *= (N-k)*pow(k, mod-2, mod)
  C %= mod
  a = (C*M*pow(M-1, (N-k-1), mod))%mod
  ans = (ans+a)%mod
  k += 1
print(ans)

Solution (Python):
def ext_euler(a, b):
    if b == 0:
        return 1, 0, a
    else:
        y, x, v = ext_euler(b, a%b)
        y -= (a//b) * x
        return x, y, v


def mod_inv(x, mod):
    if x > mod:
        ans, _, _ = ext_euler(x, mod)
    else:
        _, ans, _ = ext_euler(mod, x)
    return ans % mod


def comb_list(n, mod):
    ret = [1 for _ in range(n + 1)]
    for k in range(n):
        c = ret[k]
        c *= (n - k)
        c %= mod
        c *= mod_inv(k + 1, mod)
        c %= mod
        ret[k + 1] = c
    return ret


def main():
    MOD = 998244353
    N, M, K = list(map(int, input().split(' ')))
    
    
    
    patterns = [0 for _ in range(N)]
    comb = comb_list(N - 1, MOD)
    pw = M
    for x in range(N - 1, -1, -1):
        patterns[x] = pw * comb[x]
        patterns[x] %= MOD
        pw *= (M - 1)
        pw %= MOD
    ans = 0
    for x in range(min(K, N - 1) + 1):
        ans += patterns[x]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

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

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

print(ans)

Solution (Python):
N,M,K = list(map(int,input().split()))
MOD = 998244353
 
fac = [1] * (N+1)
inv = [1] * (N+1)
ifac = [1] * (N+1)
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]= -(inv[MOD%i]*(MOD//i))%MOD
    ifac[i]=(ifac[i-1]*inv[i])%MOD
 
cmbarr = [1] * N
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD
 
A = [M*pow(M-1,N-1-i,MOD)*cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)

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

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


C = [-1] * (N + 1)


def comb(n, r):
    if r > n - r:
        C[r] = C[n - r]

    if r == 0:
        C[0] = 1

    if C[r] != -1:
        return C[r]
    else:
        C[r] = comb(n, r - 1) * (n + 1 - r) * pow(r, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = 0

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

print(ans)

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

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


C = [-1] * (N + 1)


def comb(n, r):
    if r > n - r:
        C[r] = C[n - r]

    if r == 0:
        C[0] = 1

    if C[r] != -1:
        return C[r]
    else:
        C[r] = comb(n, r - 1) * (n + 1 - r) * pow(r, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = 0

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

print(ans)

Solution (Python):
import time

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

p = 998244353
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)


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

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

for k in range(K+1):
  
  rlt += cmb(N-1,k,p)*Mp[k]
  rlt %= p

print(rlt)

Solution (Python):
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 cmb(fact, n ,r):
    return ModInt(1) * fact[n] / fact[n - r] / fact[r]

def solve(N, M, K):
    fact = [ModInt(1)]
    for i in range(1, N + 1):
        fact.append(fact[i -1] * i)

    ret = ModInt(0)
    for x in range(K + 1):
        ret += cmb(fact, N - 1, x) * M * pow(M - 1, N - x - 1, MOD)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    print(solve(N, M, K))

Solution (Python):
MOD = 998244353
N, M, K = map(int, input().split())
Mp = [0]*(K+1)
nck = [0]*(K+1)
nck[0] = 1
ans = 0
comb = 1
for i in range(K+1):
  t = 1
  t *= M
  t %= MOD
  t *= pow(M-1, N-1-i, MOD)
  t %= MOD
  t *= comb
  t %= MOD
  ans += t
  ans %= MOD
  comb *= N-1-i
  comb %= MOD
  comb *= pow(i+1, MOD-2, MOD)
  comb %= MOD
  
print(ans)

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

N, M, K = map(int, readline().rstrip().split())
fact = [1] * (N+1)
finv = [1] * (N+1)
inv = [1] * (N+1)
inv[0] = 0
for i in range(2, N+1):
    fact[i] = (fact[i-1] * i % MOD)
    inv[i] = (-inv[MOD%i] * (MOD // i)) % MOD
    finv[i] = (finv[i-1] * inv[i]) % MOD

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

def main():
    res = 0
    for k in range(K+1):
        res += comb(N-1, k, MOD) * pow(M-1, N-k-1, MOD) * M
        res %= MOD
    
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
    po%=mod
print(ans%mod)

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

N = 10 ** 6


inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]


kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)


def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

for i in range(0, k+1):
    if i == n-1:
        base = m
    ans += base * cmb(n-1, n-1-i)
    ans %= mod
    base = base * inv_t[m-1] % mod




print(ans)

Solution (Python):
a,b,K=map(int,input().split())
C=998244353
fac=[0]*a 
finv=[0]*a
inv=[0]*a
N=a-1
def com_init():
	fac[0],finv[0]=1,1
	if a<2:return
	fac[1],finv[1]=1,1
	inv[1]=1
	for i in range(2,N+1):
		fac[i]=fac[i-1]*i%C
		inv[i]=C-inv[C%i]*(C//i)%C
		finv[i]=finv[i-1]*inv[i]%C
def com(m,k):
	if m<k: return 0
	elif m<0 or k<0:return 0
	else:
		return fac[m]*(finv[k]*finv[m-k]%C)%C
com_init()
bfac=[0]*a
bfac[0]=1
for i in range(1,a):
  bfac[i]=bfac[i-1]*(b-1) %C
ans=0

for i in range(K+1):
  ans+= com(a-1,i)*bfac[a-1-i]%C
print(ans*b%C)

Solution (Python):

import sys

MOD = 998244353  

def f(N, M, k, mf):
    '''
    >>> mf = ModFactorial(MOD, 10)
    >>> f(3, 2, 0, mf)
    2
    >>> f(3, 2, 1, mf)
    4
    >>> f(3, 2, 2, mf)
    2
    >>> f(4, 2, 0, mf)
    2
    >>> f(4, 2, 1, mf)
    6
    >>> f(4, 3, 0, mf)
    24
    >>> f(4, 3, 1, mf)
    36
    '''
    if k == N:
        return M
    base = M * pow(M-1, N-k-1, MOD) % MOD
    return base * mf.combination(N-1, k) % MOD


def solve(N: int, M: int, K: int):
    mf = ModFactorial(MOD, N)
    ans = 0
    for k in range(K+1):
        ans = (ans + f(N, M, k, mf)) % MOD
    return ans



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))  
    print(solve(N, M, K))

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self.mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        >>> ModFactorial(1000000007).permutation(10, 0)
        1
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        >>> ModFactorial(1000000007).combination(10, 0)
        1
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

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


import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
temp = ModInt(1)
for k in range(K+1):
    NcK.append(temp)
    temp *= N-1-k
    temp /= k+1

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

ans = ModInt(0)
notNcK = ModInt(M*(M-1)**(N-1))
ans += notNcK*NcK[0]
for k in range(K):
    notNcK /= (M-1)
    ans += notNcK*NcK[k+1]
print(ans)

Solution (Python):
mod=998244353
fact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,2*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m,k=map(int,input().split())
ans=0
for i in range(k,-1,-1):
  group=n-i
  tmp=fact[n-1]*revfact[group-1]*revfact[n-1-(group-1)]
  tmp%=mod
  tmp*=m
  tmp%=mod
  tmp*=pow(m-1,group-1,mod)
  ans+=tmp
  ans%=mod
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect
import functools

MOD = 998244353


def factorial(n, mod=None, memo=False):
    if memo:
        factorial.memo = [1] * (n + 1)
        
        
        for i in range(1, n + 1):
            
            
            if mod is None:
                factorial.memo[i] = i * factorial.memo[i - 1]
            else:
                factorial.memo[i] = i * factorial.memo[i - 1] % mod
            
            
    return factorial.memo[n]

def choose(n, r, mod=None):
    a = factorial(n)
    b = factorial(r)
    c = factorial(n - r)
    if mod is None:
        res = a // b // c
    else:
        
        res = a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod) % mod
    return res

def calc(n, m, k):
    res = choose(n - 1, k, MOD) * m * pow(m - 1, n - 1 - k, MOD) % MOD
    
    
    return res


if __name__ == '__main__':
    n, m, k = list(map(int, input().split()))
    ans = 0
    factorial(n, MOD, True)
    for kk in range(k + 1):
        ans += calc(n, m, kk)
    
    print(ans % MOD)

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

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

print(ans)

Solution (Python):
n,m,k = map (int,input().split())
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 = n-1  
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)

mod = 998244353
ans = 0

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

Solution (Python):


import sys

class EColorfulBlocks:
    def solve(self, tc=0):
        import math

        MOD = 998244353

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

        if n == 1:
            print(m)
            return

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

        ans = 0
        p_min = n - k 
        for p in range(p_min, n + 1):
            ans += m * pow(m - 1, p - 1, MOD) * (c[p])
            ans %= MOD

        
        
        
        

        print(ans)



solver = EColorfulBlocks()
input = sys.stdin.readline

solver.solve()

Solution (Python):
import sys
 
mod = 998244353  
 
 
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  
        self.invModulos = [0, 1]  
        self.invFactorial_ = [1, 1]  
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
 
 
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m
n,m,k=map(int,input().split())
c=Combination(mod)
ans=0
for i in range(k+1):
    ans+=((powm(m-1,n-1-i,mod))*(c.ncr(n-1,i)%mod))%mod
    ans%=mod
m=m%mod
print((ans*m)%mod)

Solution (Python):
import math
memo = {}
mod = 998244353
"""
def choose(n,k):
    x = ",".join([str(n),str(k)])
    if x not in memo:
        memo[x] = math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    return memo[x]
"""
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)

X,M,K = map(int,input().split())
ans = 0
for k in range(K+1):
    ans += M*pow((M-1),X-k-1,mod)*cmb(X-1,k,mod)

print(ans%mod)

Solution (Python):
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
import math
import fractions
import collections
import itertools
import pprint
N,M,K=map(int,input().split())
fracmod=[1]*(2*10**5+10)
invfracmod=[1]*(2*10**5+10)
p=998244353
for i in range(1,2*10**5+10):
    fracmod[i]=(fracmod[i-1]*i)%p
for i in range(2*10**5+10):
    invfracmod[i]=modinv(fracmod[i],p)
ans=0
for i in range(K+1):
    ans=(ans+(M*pow(M-1,N-1-i,p)*fracmod[N-1]*invfracmod[i]*invfracmod[N-1-i])%p)%p
print(ans)

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

result = 0
p = 998244353
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  


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


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)

for k in range(K + 1):
    c = cmb(N - 1, k, p)
    m = M % p
    n = pow(M - 1, N - k - 1, p)
    result = (result + c * m * n) % p

print(result)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
mod = 998244353
memo = [-1]*(10**6)
memo[0] = 1
def fact(n):
    if memo[n] != -1:
        return memo[n]
    else:
        res = n*fact(n-1)%mod
        memo[n] = res
        return res

def comb(n,k):
    return fact(n)*pow(fact(k),mod-2,mod)*pow(fact(n-k),mod-2,mod)%mod

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

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

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

mod = 998244353


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


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = fac[a]
    c *= pow(fac[b], p - 2, p)
    c *= pow(fac[a-b], p - 2, p)
    return c % p


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

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

print(ans)

Solution (Python):
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
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
def COM(n,k):
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)

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

MOD =  998244353
mod = MOD
MAX = N+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    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 cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

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

ans -= minus 
ans = (ans+MOD)%MOD
print(ans)

Solution (Python):
MOD = 998244353


class Combination:

    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)

        for i in range(1, n+1):
            self.fact[i] = i*self.fact[i-1] % mod
            self.ifact[i] = pow(i, mod-2, mod) * self.ifact[i-1] % mod

    def get(self, n: int, k: int):
        if k < 0 or n < k:
            return 0
        return self.fact[n] * self.ifact[k] * self.ifact[n-k] % MOD

    def __call__(self, n: int, k: int):
        return self.get(n, k)


def main():
    N, M, K = [int(x) for x in input().split()]
    comb = Combination(N, MOD)
    ans = 0
    for i in range(0, K+1):
        ans += M * pow(M-1, N-i-1, MOD) * comb(N-1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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


f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)


def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

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):
n,m,k=map(int,input().split())
fact,factinv,mod=[1]*n,[1]*n,998244353
for i in range(2,n):
  fact[i]=fact[i-1]*i%mod
factinv[n-1]=pow(fact[n-1],mod-2,mod)
for i in range(n-2,0,-1):
  factinv[i]=factinv[i+1]*(i+1)%mod
ncr=lambda n,r:fact[n]*factinv[r]%mod*factinv[n-r]%mod
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-i-1,mod)*ncr(n-1,i)%mod
print(ans%mod)

Solution (Python):

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

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

Solution (Python):

"""
隣り合うブロックの組の個数がi個(i=0~k)であるときの組み合わせ数を求めていく。
まず、k=0の時を考えると、m=4の時、
res = 4*3**(n-1)となることがわかる。
次に、k>0のときは、
どれか2つのブロックを1つにつなぎ合わせると考えて、
res = 4*3**(n-1-i)
これに合わせて、どのブロックが接続するのかを考える必要があり、
どのブロックも右隣のブロックにのみ接続できると考えた場合、
接続できるブロックの個数はn-1個(一番右のブロックは接続先がない)
そこからi個選んで右のブロックにつなぐので、
n-1Ciとなる。
よって、k>0の場合の組み合わせ数は、
res = 4*3**(n-1-i)*(n-1)Ci
となる。
これを for i in range(0,k+1)だけ足し合わせたものが答え。
補足：
例えば3つのブロックを接続すると考えた場合、
2つをつなぎ合わせる場合と区別しそうだが、
「つなぐブロックの個数」はどちらでも同じになる。
更に、その時に全体の分割されたブロックの個数はn-i個で固定されるので、
m*pow(m-1,n-1-i)の部分が変わることもなく、
どの隣のブロックを選ぶかというのも隣接しても不都合がない。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,k = map(int,readline().split())
mod = 998244353
 
if m == 1:
    if k < n-1:
        print(0)
    else:
        print(1)
    exit()

def pow(n,p,mod=mod): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def factrial_memo(n=2*10**5,mod=mod):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
fact = factrial_memo()

def fermat_cmb(n, r, mod=mod): 
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
ans = 0
for i in range(k+1):
    res = m*pow(m-1,n-1-i) 
    ans += res*fermat_cmb(n-1,i)%mod
print(ans%mod)

Solution (Python):
from sys import stdin
readline=stdin.readline
N,M,K=map(int,readline().split())
mod=998244353

fact=[1]*(N+1)
finv=[1]*(N+1)
inv=[1]*(N+1)
inv[0]=0
for i in range(2,N+1):
    fact[i]=(fact[i-1]*i%mod)
    inv[i]=(-inv[mod%i]*(mod//i))%mod
    finv[i]=(finv[i-1]*inv[i])%mod

def com(N,K,mod):
    if (K<0) or (N<K):
        return 0
    return fact[N]*finv[K]*finv[N-K]%mod

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

print(ans)