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






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MODULO = 998244353


def combi(n: int, k: int, fact: List[int]) -> int:
    r = 1
    for i in range(k):
        r *= n - i
    return (r // fact[k]) % MODULO


def factorial(n: int) -> List[int]:
    fact = [0] * (n + 1)
    inv = [0] * (n + 1)
    fact[0] = 1
    inv[0] = 1
    for i in range(1, n + 1):
        fact[i] = (i * fact[i - 1]) % MODULO
        inv[i] = pow(fact[i], MODULO - 2, MODULO)
    return fact, inv


def solve(n: int, m: int, k: int) -> int:
    result = 0
    
    fact, inv = factorial(n - 1)
    for i in range(k + 1):
        result = (
            result
            + (
                m
                * pow(m - 1, n - i - 1, MODULO)
                * fact[n - 1]
                * inv[i]
                * inv[n - 1 - i]
            )
        ) % MODULO
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    
    N, M, K = map(int, input().split())
    result = solve(N, M, K)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            
            
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Solution (Python):
n,m,k=map(int,input().split())
ans=0
mod=998244353
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
for kk in range(k+1):
  anss=m*pow(m-1,n-1-kk,mod)%mod
  anss=anss*comb(n-1,kk)%mod
  ans=(ans+anss)%mod
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):    
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))

zenpou.reverse()
ans=0
for i in range(x+1):
    
    
    
    ans+=(n_c_i[i]*k*each_cal[i])%od
    ans%=od

print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
    

ans=0
for i in range(x+1):
    
    ans+=(n_c_i[i]*k*each_cal[i])%od
    ans%=od

print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)

pow_k=pow(k-1,n-1,od)
inv_k=pow(k-1,od-2,od)
ans=0

for i in range(x+1):
        
    
    p_k=(k*pow(k-1,n-i-1,od))%od
    
    ans+=(n_c_i[i]*p_k)%od
    ans%=od

print(ans)

Solution (Python):
def pre_c(n, mod):
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for i in range(n + 1):
        if i == 0:
            f[i] = 1
            g[i] = 1
        else:
            f[i] = (f[i - 1] * i) % mod
            g[i] = pow(f[i], mod - 2, mod)

    return f, g
n, m, k = map(int,input().split())
mod = 998244353
F, G = pre_c(n - 1, mod)
cnt = 0
for i in range(k + 1):
    temp = F[n - 1] * G[i] * G[n - 1 - i] * m * pow(m - 1, n - 1 - i, mod)
    cnt = (cnt + temp) % mod
print(cnt)

Solution (Python):
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = []
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-f[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    g = [1]
    for i in range(n-1):
        g.append(g[i]*(m-1)%z)
    for i in range(k+1):
        a.append(b[i]*m*g[n-i-1]%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353

def make_array_for_comb(N, mod):
    fact = [1,1]
    fact_inv = [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)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

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

n,m,k = map(int,readline().split())
fact, fact_inv = make_array_for_comb(n,mod)
ans = 0

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

print(ans)

Solution (Python):
class Facts:

  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      self.setup_table(n_max)

  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod

  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t


mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

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

print(ans % mod)

Solution (Python):
class Facts:
  
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

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

print(ans % mod)

Solution (Python):
class Facts:
  
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

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

print(ans % mod)

Solution (Python):
MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)

Solution (Python):
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


class Comb(object):

    def __init__(self, n, MOD=1e9 + 7):
        self.MOD = MOD

        self.fact = [1, 1] + [0] * n
        self.finv = [1, 1] + [0] * n
        self.inv = [0, 1] + [0] * n

        for i in range(2, n + 2):
            self.fact[i] = self.fact[i - 1] * i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i] * (self.MOD // i) % self.MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % self.MOD

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

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

    def calc_h(self, n, k):
        return self.calc_c(n + k - 1, n - 1)


MOD = 998244353
N, M, K = map(int, read().split())
comb = Comb(N + K, MOD=MOD)

ans = 0
col = M

for x in range(N - 1, -1, -1):
    acc = col
    acc *= comb.calc_c(N - 1, x)
    if x <= K:
        ans += acc
        ans %= MOD
    col *= (M - 1)
    col %= MOD

print(ans)

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

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

    finv[N - 1] = pow(fact[N - 1], MOD - 2, MOD)
    for i in range(N - 2, -1, -1):
        finv[i] = finv[i + 1] * (i + 1) % MOD

    def C(n, r):
        return fact[n] * finv[r] * finv[n - r] % MOD

    ans = pow(m, n, MOD)
    for r in range(1, n - k):
        ans -= C(n - 1, r - 1) * m * pow(m - 1, r - 1, MOD)
        ans %= MOD

    print(ans)

main()

Solution (Python):
mod = 998244353

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

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

Solution (Python):
n, m, k = map(int, input().split())
mod = 998244353
s = m - 1
S = 1
ans = 0
fact = [1] * (n + 1)
fact_inv = [0] * (n + 1)
for i in range(1, n + 1):
	fact[i] = (fact[i - 1] * i) % mod
	fact_inv[i] = pow(fact[i], mod - 2, mod)
fact_inv[0] = fact_inv[1]


for t in range(n):
	if t >= n - k - 1:
		b = fact[n - 1] * fact_inv[t] * fact_inv[n - t - 1]
		ans += (S * b) % mod
		
	S = (S * s) % mod
	
print((m * ans) % mod)

Solution (Python):
import math
n,m,k=map(int,input().split())
num=210000
mod=998244353
fact=[0]*num
invfact=[0]*num
fact[0]=1
for i in range(1,num):
    fact[i]=fact[i-1]*i%mod
invfact[num-1]=pow(fact[num-1],mod-2,mod)
for i in range(num-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod
def nck(n,k):
    if n<k or k<0:
        return 0
    return fact[n]*invfact[k]*invfact[n-k]
ans=0
for i in range(k+1):
    
    ans+=nck(n-1,i)*m*pow(m-1,n-i-1,mod)%mod
    ans%=mod
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    MOD = 998244353

    if M == 1:
        if K == N - 1:
            print(1)
        else:
            print(0)
        exit()
    
    prepare(N + 10, MOD)

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

        m *= m_inv
        m %= MOD

    print(ans * M % MOD)


if __name__ == "__main__":
    main()

Solution (Python):

class ModCombination():
    def __init__(self, n, mod=998244353):
        self.mod = mod
        self.N = n
        fact = [1, 1] 
        ifact = [1, 1] 
        inverse = [0, 1] 

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

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

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

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

    ans = 0
    for i in range(0, K + 1):
        
        
        
        base = M * pow(M - 1, N - i - 1, MOD)
        
        
        
        patterns = base * mc.nCr(N - 1, i)
        
        
        ans = (ans + patterns) % MOD
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines



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

    MOD = 998244353

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

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

    print(ans * M % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


class Bigint:

    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n % self.mod

    @classmethod
    def set_mod(cls, mod):
        cls.mod = mod

    @staticmethod
    def _to_int(n):
        t = type(n)
        if t == int:
            return n
        elif t == Bigint:
            return n.n
        else:
            raise

    @staticmethod
    def _to_bigint(n):
        t = type(n)
        if t == int:
            return Bigint(n)
        elif t == Bigint:
            return n
        else:
            raise

    def __str__(self):
        return f"{self.n}"

    def __add__(self, other):
        return Bigint(self.n + self._to_int(other))

    def __iadd__(self, other):
        self.n = (self.n + self._to_int(other)) % self.mod
        return self

    def __sub__(self, other):
        return Bigint(self.n - self._to_int(other))

    def __isub__(self, other):
        self.n = (self.n - self._to_int(other)) % self.mod
        return self

    def __mul__(self, other):
        return Bigint(self.n * self._to_int(other))

    def __imul__(self, other):
        self.n = (self.n * self._to_int((other))) % self.mod
        return self

    def __pow__(self, other):
        assert type(other) == int, "power should be integer"
        
        if other < 0:
            return self ** (other % (self.mod-1))
        ret = Bigint(1)
        now = Bigint(self.n)
        while other > 0:
            if other & 1:
                ret *= now
            other >>= 1
            now *= now
        return ret

    def __truediv__(self, other):
        return self * (self._to_bigint(other) ** (self.mod-2))

    def __itruediv__(self, other):
        self *= (self._to_bigint(other) ** (self.mod-2))
        return self


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, m, k = _ia()
    Bigint.set_mod(998244353)
    power = [Bigint(1)]
    for i in range(n-1):
        power.append(power[i] * (m-1))

    fact = Bigint(1)
    inv = [Bigint(1)] * n
    for i in range(1, n):
        fact *= i
        inv[i] = inv[i-1] * Bigint(i) ** (-1)

    ans = Bigint(0)
    for i in range(k+1):
        c = fact * inv[n-1-i] * inv[i]
        ans += (c * m * power[n-1-i])

    return ans


if __name__ == "__main__":
    print(main())

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

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

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

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






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


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

Solution (Python):

from collections import defaultdict

MOD = 998244353

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


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


fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD

ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
color = M
for x in reversed(range(N)):
    now = color
    now *= combination(N-1, x)
    now %= MOD
    if x <= K:
        ans += now
        ans %= MOD
    color *= M - 1
    color %= MOD

print(ans)

Solution (Python):
def e_colorful_blocks(MOD=998244353):
    N, M, K = [int(i) for i in input().split()]

    class Combination(object):
        """素数 mod に対する二項係数の計算"""
        __slots__ = ['mod', 'fact', 'factinv']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], -1, mod))
            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.fact, self.factinv = mod, fac, inv[::-1]

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

    ans = 0
    comb = Combination(max(N, M), MOD).combination
    for x in range(K + 1):
        a = (M * pow(M - 1, N - 1 - x, MOD)) % MOD
        b = comb(N - 1, x)
        ans = (ans + a * b) % MOD
    return ans

print(e_colorful_blocks())

Solution (Python):
P = 998244353


nn = 200200

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


def comb(a, b):
    return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


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

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


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

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M,K=map(int,input().split())
mod=998244353
fac=[1,1]
for i in range(2,N*2):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    if a<b:
        return(0)
    return(fac[a]*ifac[b]*ifac[a-b]%mod)


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

Solution (Python):

n,m,k = list(map(int,input().split()))
fac = [1]*n
finv = [1]*n
inv = [1]*n
MOD = 998244353
for i in range(2,n):
    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 comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

ans = 0
for i in range(k+1):

    ans += comb(n-1,i)*m*pow(m-1,n-i-1,MOD)%MOD
    ans %= MOD
print(ans)

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


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


mod = 998244353
n = 2*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)

ans = 0
for i in range(K+1):
    
    ans += cmb(N-1, i, mod)*M*pow(M-1, N-1-i, mod)
    ans %= 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  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

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

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

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

facs = [1] * N
invs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

s = 0
for i in range(K+1):
    d = facs[N-1] * invs[i] * invs[N-1-i] \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

Solution (Python):
MOD = 998244353
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
n,m,k = map(int,input().split())
c = 0
for i in range(k+1):
    c += comb_mod(n-1, i)*m*pow(m-1,n-i-1,MOD)
    c %= MOD
print(c)

Solution (Python):
import itertools

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   
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

ans = 0

l2 = m*(m-1)**(n-k-1)
for _k in range(k, -1, -1):
    

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p

    l2 %= p
    l2 *= (m - 1)
    l2 %= p


print(ans)

Solution (Python):
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, n):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)

Solution (Python):
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, max(n, m) + 1):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)

Solution (Python):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

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

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

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

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

Solution (Python):
n, m, k = map(int, input().split())
mod =998244353
 
def cmb1(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 = 10**6
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 )
 
def power(a, n, mod):
  bi=str(format(n,"b")) 
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res
 
ans = 0
for x in range(k+1):
    temp = cmb1(n-1, x, mod)
    temp *= m*power(m-1, n-1-x, mod)
    ans += temp
print(ans%mod)

Solution (Python):
import itertools

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   
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

ans = 0

l2 = m*(m-1)**(n-k-1)
for _k in range(k, -1, -1):
    

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p
    l2 %= p
    l2 *= (m - 1)


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



MOD = 998244353


def inv(x, m):
  y, u, v = m, 1, 0

  while y != 0:
    t = x // y
    x -= t * y
    u -= t * v
    x, y = y, x
    u, v = v, u

  return u % m


def main():
  N, M, K = map(int, input().split())
  color = M
  division = 1
  count = 0

  if K == N - 1:
    count += color * division

  for i in range(N - 2, -1, -1):
    color = (color * (M - 1)) % MOD
    division = division * (i + 1) * inv(N - 1 - i, MOD) % MOD

    if i <= K:
      count = (count + color * division) % MOD

  print(count)


if __name__ == '__main__':
  main()