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):
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make_inv(n)
        return self._factorial_inv[n]

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self.fact_inv(n-r)*self.fact_inv(r) % self.mod
        return self(n)*t % self.mod

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self.fact_inv(n-1)*self.fact_inv(r) % self.mod
        return self(n+r-1)*t % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def _make_inv(self, n):
        if n >= self.mod:
            n = self.mod
        self._make(n)
        if self._size_inv < n+1:
            for i in range(self._size_inv, n+1):
                self._factorial_inv.append(self.modinv(self._factorial[i]))
            self._size_inv = n+1


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

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

fac = [1 for i in range(N+1)]
for n in range(1,N+1):
    fac[n] = (n*fac[n-1])%MOD

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

def C(n,k):
    global MOD
    return (fac[n]*fac_inv[k]*fac_inv[n-k])%MOD

print(sum([C(N-1,b)*M*pow(M-1,N-1-b,MOD)%MOD for b in range(K+1)])%MOD)

Solution (Python):
n,m,k=map(int,input().split())
mod1,mod2=10**9+7,998244353
mod=mod2
MAX=n-1
fact=[1]*(MAX+1)
inv=[1]*(MAX+1)
for i in range(2,MAX+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=0
cor=pow(m-1,n-1-k,mod)
for i in range(k,-1,-1):
    ans=(ans+comb(n-1,i)*cor)%mod
    cor=cor*(m-1)%mod

print(m*ans%mod)

Solution (Python):
def main():
  n,m,k = map(int, input().split())
  f = [1]
  p = 998244353
  for i in range(1, n):
    f.append(f[-1] * i % p)

  ans = 0
  def nCk(n,k):
    return f[n] * pow(f[n-k], p-2, p) * pow(f[k], p-2, p) % p

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

if __name__ == '__main__':
  main()

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

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

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

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

N,M,K = map(int,input().split())
ans = 0
MOD = 998244353
comb = Combination(2*(10**5)+1, MOD)
for i in range(K+1):
  res = (M * pow(M-1, N-i-1, MOD)%MOD * comb(N-1, i)%MOD)%MOD
  ans = (ans + res)%MOD

print(ans)

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

        return self.fact[k]

    def inverse_factorial(self, k):
        return self.inv_fact[k]

    def permutation(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.mod

    def combination(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.mod

    def combination_large(self, k, r):
        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
cmb = Combination(10**6, mod)

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

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


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 i in range(k+1):
    ans += m*cmb(n-1, i, mod)*pow(m-1, n-1-i, mod)%mod
    ans %= mod

print(ans)

Solution (Python):

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

MOD = 998244353
MAX = 2 * 10 ** 5 + 1


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

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


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


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

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353

class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    n, m, k = map(int, input().split())
    cmb = CmbMod(n, mod)
    cmb.prep()

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


if __name__ == '__main__':
    resolve()

Solution (Python):
p = 998244353
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    if m%2==1:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,M,K = map(int,input().split())
A = [1 for _ in range(N+1)]
for i in range(2,N+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+1)]
B[N] = pow(A[N],p-2)
for i in range(N-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p
C = [1 for _ in range(N)]
C[0] = M
for i in range(1,N):
    C[i] = (C[i-1]*(M-1))%p
tot = C[N-1]
for k in range(1,K+1):
    cnt = (A[N-1]*B[k]*B[N-1-k])%p
    cnt = (cnt*C[N-1-k])%p
    tot = (tot+cnt)%p
print(tot)

Solution (Python):
def comb(n, k, nk, mod):
    return (n * pow(k * nk, mod - 2, mod)) % mod


def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    base = pow(m - 1, n - 1 - k, mod)
    fact = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod
    for i in range(k, -1, -1):
        ans += base * comb(fact[n - 1], fact[i], fact[n - i - 1], mod)
        ans %= mod
        base *= m - 1
        base %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
def combs_mod(n,k,mod):
  
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def solve():
  ans = 0
  mod = 998244353
  N, M, K = map(int, input().split())
  lis = combs_mod(N-1,K,mod)
  for i in range(K+1):
    ans += M*lis[i]*pow(M-1,N-1-i,mod)
    ans %= mod
  return ans
print(solve())

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

def pk(x,n,mod):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % mod
        x = x ** 2 % mod
        n //= 2

    return K * x % mod

nck = [0]*n
kake = [0]*n

a = m
for i in range(n):
    kake[i] = a
    a = a*(m-1)%MOD
    
a = 1
for i in range(n):
    nck[i] = a
    a = int(a * (n-1-i) * pk(i+1,MOD-2,MOD)) % MOD
    
ans = 0
for i in range(k+1):
    ans = (ans + (nck[i] * kake[n-1-i] % MOD)) % MOD
    
print(ans)

Solution (Python):
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        ans = self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
        if n >= r:
            return ans
        else:
            return 0
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    mex = [0]*(k+1)
    mex[0] = pow(m-1,n-k-1,mod)
    for i in range(1,k+1):
        mex[i] = mex[i-1]*(m-1)%mod
    mex = mex[::-1]
    for i in range(k+1):
        ans += c.combination(n-1, i)*mex[i]
        ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353
m = 2*10**5 + 500
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            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):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in 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)


if __name__ == '__main__':
    main()

Solution (Python):
def combs_mod(n,k,mod):
  
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def solve():
  ans = 0
  mod = 998244353
  N, M, K = map(int, input().split())
  top = min(K,N-1)
  combs = combs_mod(N-1,top,mod)
  for k in range(top+1):
    ans += M*combs[k]*pow(M-1,N-1-k,mod)
    ans %= mod
  return ans
print(solve())

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

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

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

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

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

fac = [0]*MAX
facinv = [0]*MAX
inv = [0]*MAX


def modinv(a, mod):
    b = mod
    x, u = 1, 0
    while b:
        q = a//b
        a, b = b, a-q*b
        x, u = u, x-q*u
    x %= mod
    return x


def mod_nCr_init(n, mod):
    fac[0] = fac[1] = 1
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod


def mod_nCr(n, r, mod):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * (facinv[r] * facinv[n-r] % mod) % mod


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

Solution (Python):
N, M, K = map(int, input().split())
mod = 998244353
 
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
 
if N == 1:
  print(M)
  exit()
 
m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)
 
ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)
 
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod
 
ans = ans*M%mod
print(ans)

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

b = str(bin(mod-2))[2:]
blis = []
for _ in range(len(b)):
  if b[-_-1] == '1':
    blis.append(_)

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    n = len(b)
    li = []
    for _ in range(n):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res * li[item] %mod
    return res
"""      
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
"""
if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*modinv(k+1)
  c %= mod
  ncombi.append(c)

"""
olis = ncombi
for k in range(N-1):
  nlis = [1]
  for  j in range(len(olis)-1):
    nlis.append(olis[j]+olis[j+1])
  nlis.append(1)
  olis = nlis
  
ncombi = olis
"""
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

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

b = str(bin(mod-2))[2:]
blis = []
for _ in range(len(b)):
  if b[-_-1] == '1':
    blis.append(_)

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    n = len(b)
    li = []
    for _ in range(n):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res * li[item] %mod
    return res
"""      
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
"""
if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*modinv(k+1)
  c %= mod
  ncombi.append(c)

"""
olis = ncombi
for k in range(N-1):
  nlis = [1]
  for  j in range(len(olis)-1):
    nlis.append(olis[j]+olis[j+1])
  nlis.append(1)
  olis = nlis
  
ncombi = olis
"""
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

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

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

if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod
print(ans)

Solution (Python):
N,M,K = list(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
N1 = 2 * 10 ** 5 + 10  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N1 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0
mem = 1
mem = pow(M-1,N-K-1,p)
for i in range(K,-1,-1):
  wk = M * mem
  wk %= p
  wk *= cmb(N-1,i,p)
  
  mem *= (M-1)
  mem %= p
  ans += wk
  ans %= p
  
print(ans)

Solution (Python):
class CombMod:
    def __init__(self, V, mod):
        self.fact = [1] * V
        self.finv = [1] * V
        for i in range(1, V):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.finv[-1] = pow(self.fact[-1], mod - 2, mod)
        for i in range(V - 2, 0, -1):
            self.finv[i] = self.finv[i + 1] * (i + 1) % mod
        self.mod = mod

    def comb(self, a, b):
        return self.fact[a] * self.finv[b] % mod * self.finv[a - b] % mod


N, M, K = map(int, input().split())
mod = 998244353
tool = CombMod(N + 1, mod)

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

Solution (Python):

import math



def main():
    (N, M, K) = map(int, input().split())
    MOD = 998244353
    
    fact = [1]*(N+1)
    factinv = [1]*(N+1)
    for i in range(1,N+1):
        fact[i] = fact[i-1]*i % MOD
        factinv[i] = pow(fact[i], MOD-2, MOD)
    def comb(n, k):
        return fact[n] * factinv[k] * factinv[n-k] % MOD

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

    print(ans%MOD)

main()

Solution (Python):
N, M, K = map(int, input().split())
MOD = 998244353
MAX_N = 10**6
fac = [0]*(MAX_N)
fac_inv = [0]*(MAX_N)
fac[0] = 1
for i in range(MAX_N-1):
    fac[i+1] = fac[i]*(i+1) % MOD
fac_inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(MAX_N-2, -1, -1):
    fac_inv[i] = fac_inv[i+1]*(i+1) % MOD


def nCk(n, k):
    return fac[n] * fac_inv[k] % MOD * fac_inv[n-k] % MOD


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

Solution (Python):
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    m1 = [None]*(n+1)
    kaizyo = [None]*(n+1)
    nm1 = 1
    kai = 1
    for i in range(n+1):
        m1[i] = nm1
        nm1 *= m-1
        nm1 %= mod
        kaizyo[i] = kai
        kai *= i+1
        kai %= mod
    
    def comb(a, b):
        return (kaizyo[a]*fermat(kaizyo[a-b]*kaizyo[b], mod))%mod

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

def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out



if __name__ == "__main__":
    main()

Solution (Python):


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


fact = [0]*(N+1)
fact_inv = [0]*(N+1)
inv = [0]*(N+1)

mod = 998244353

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

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



pow_M1 = [0]*N
pow_M1[0] = 1

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


ans = 0

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

print(ans)

Solution (Python):

import sys

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


if (M == 1) and (K == N-1):
    print(1)
    sys.exit()
elif (M == 1) and (K < N-1):
    print(0)
    sys.exit()


mod = 998244353

a = M * pow(M-1, N-1, mod)
inv_M1 = pow((M-1), mod-2, mod )  

comb = 1
ans = 0

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


print(ans)

Solution (Python):



class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret

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

F=FactMod(N+1,MOD)
ans=0
for kk in range(K+1):
    not_kk=N-kk
    if not_kk==0:
        r=M*pow(M-1,N-1,MOD)
        ans+=M*pow(M-1,N-1,MOD)
        ans%=MOD
    else:
        r=M*pow(M-1,not_kk-1,MOD)
        ans+=M*pow(M-1,not_kk-1,MOD)*F.comb(N-1,kk)
        ans%=MOD
print(ans)

Solution (Python):
def pow(x, n):
    if n == 0:
        return 1
    res = pow(x * x % MOD, n//2)
    if n % 2 == 1:
        res = res * x % MOD
    return res

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
 
MOD = 998244353
N, M, K = map(int, input().split())

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**8)

MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD) if M>1 else 0
ans = 0
tmp = pow(M-1,N-1,MOD) if M>1 else 0
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
if M==1 and K==N-1:
    ans += 1
print(ans)

Solution (Python):
N,M,K = map(int,input().split())
mod = 998244353
n = 200050
frac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(n):
    frac[i+1] = (i+1)*frac[i]%mod
finv[-1] = pow(frac[-1],mod-2,mod)
for i in range(1,n+1):
    finv[n-i] = finv[n-i+1]*(n-i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or n<r: return 0
    r = min(r,n-r)
    return frac[n]*finv[n-r]*finv[r]%mod



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

Solution (Python):
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    kai = [None]*n
    m1 = [None]*n
    num = 1
    ki = 1
    for i in range(n):
        m1[i] = num
        num *= m-1
        num %= mod
        kai[i] = ki
        ki *= i+1
        ki %= mod
    
    def comb(a, b):
        return kai[a]*fermat(kai[b]*kai[a-b], mod)
        
    ans = 0
    for i in range(k+1):
        ans += m*m1[n-1-i]*comb(n-1, i)
        ans %= mod
    print(ans)
        
def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out

if __name__ == "__main__":
    main()

Solution (Python):
Nn, M, K = map(int, input().split())
MOD = 998_244_353

p = MOD
N = Nn  
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

ans = 0
M_1_pwr = pow(M-1, Nn-1-K, MOD)
for j in range(K,-1,-1):
  tmp = 1
  tmp *= cmb(Nn-1,j,MOD)
  tmp *= M_1_pwr
  tmp %= MOD
  
  
  
  ans += tmp
  ans %= MOD
  
  M_1_pwr *= (M-1)
  M_1_pwr %= MOD
  
ans *= M
ans %= MOD

print(ans)

Solution (Python):
import numpy as np
N, M, K = [int(_) for _ in input().split()]
mod = 998244353


class Factorial:
    def __init__(self, max_fact, mod):
        
        
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = N
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
ans = 0
for r in range(K + 1):
    ans += comb(N - 1, r) * M * pow(M - 1, N - r - 1, mod)
    ans %= mod
print(ans)

Solution (Python):

def pre_combi1(n, p):
    fact = [1]*(n+1)  
    factinv = [1]*(n+1)  
    inv = [0]*(n+1)  
    inv[1] = 1
    
    for i in range(2, n + 1):
        fact[i]= fact[i-1] * i % p
        inv[i]= -inv[p % i] * (p // i) % p
        factinv[i]= factinv[i-1] * inv[i] % p
    return fact, factinv

def combi1(n, r, p, fact, factinv):
    """
    k<n<10**7でpが素数のときのnCr % 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
fact,finv=pre_combi1(2*10**5+1,p)
n,m,k=map(int,input().split())
ans=0
dup=[0] * n
dup[0] = 1
for j in range(1,n):
  dup[j]=dup[j-1]*(m-1) % p
for i in range(k+1):
  ans += m*combi1(n-1,i,p,fact,finv)*dup[n-i-1]
  ans %= p
print(ans)

Solution (Python):

def pre_combi1(n, p):
    fact = [1]*(n+1)  
    factinv = [1]*(n+1)  
    inv = [0]*(n+1)  
    inv[1] = 1
    
    for i in range(2, n + 1):
        fact[i]= fact[i-1] * i % p
        inv[i]= -inv[p % i] * (p // i) % p
        factinv[i]= factinv[i-1] * inv[i] % p
    return fact, factinv

def combi1(n, r, p, fact, factinv):
    """
    k<n<10**7でpが素数のときのnCr % 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
fact,finv=pre_combi1(2*10**5+1,p)
n,m,k=map(int,input().split())
ans=0
dup=[0] * n
dup[0] = 1
for j in range(1,n):
  dup[j]=dup[j-1]*(m-1) % p
for i in range(k+1):
  ans += m*combi1(n-1,i,p,fact,finv)*dup[n-i-1]
  ans %= p
print(ans)

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

list_size = 2*10**5 + 4

f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod

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