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

l_lis = [1]
r_lis = [1]

l, r = 1, 1
for j in range(K+1):
    l = l*(j+1)%mod
    r = r*(N-j-1)%mod
    l_lis.append(l)
    r_lis.append(r)

def comb(a, b):
    global mod
    l = l_lis[b]
    r = r_lis[b]
    return (r*pow(l, mod-2, mod))%mod
 
ans = 0
for i in range(K+1):
    ans += comb(N-1, i)*M*pow((M-1), (N-1-i), mod)%mod

print(ans%mod)

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


fac = [1] * n
finv = [1] * n
inv = [1] * n


def COMinit():
    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 COM(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

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

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)

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

mod = 998244353
NUM = 3*(10**5)
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

for i in range( 2, NUM + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inv.append( ( -inv[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inv[-1]) % mod )

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

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

print(ans)

Solution (Python):
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


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


def comb(n, r):
    ret = fact[n]*inv(fact[r])*inv(fact[n-r])
    return ret % mod


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

print(ans)

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

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

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


def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]


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

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

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

Solution (Python):
N,M,K=map(int, input().split())
mod=998244353
if M==1:
  if N-1<=K:
    print(1)
    exit()
  else:
    print(0)
    exit()
    
MAX_N = 10**6
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

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

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

def f(k,n,m):
  
  a=(pow(m-1,n-k-1,mod)*m)%mod
  b=mod_comb_k(n-1,k,mod)
  return a*b%mod

ans=0
for i in range(0,K+1):
  d=f(i,N,M)
  ans+=d
  ans%=mod
  
print(ans)

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

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

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


def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]


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

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 nCr(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

"""
・思いついた
隣り合うブロックの組であって同じ色で塗られている組の個数を、0~Kまでそれぞれ数え上げて足し合わせる

・思いつかなかった
組みの個数の場合の数を数える方法
-> 11232333 みたいな並びだと、同じ色の組は3つになっている
 これらの組みの選び方は、ブロックN個には間がN-1個あるから、ここからk個選べば良い
 （組の数なので、111だと左の11で1組、右の11で1組になる（111で三つ同じ色じゃん！とか思ってた））
  すると、選んだ間の両側にあるブロックを一つの塊とみなせるので、これはM個の色を選べる。
  残りはM-1個から選べる。
  なので、M * nCr(N-1, k) * (M-1)**(N-1-k)
  (M色取りうる奴の色の選び方 x どの位置で組を作るか x 隣り合うブロックの色が被らないものの選び方)
"""
ans = 0
for k in range(K+1):
    if k == 0:
        ans += M * pow(M-1, N-1, MOD)
        
    else:
        ans += M * nCr(N-1, k) * pow(M-1, N-k-1, MOD) 

    ans %= MOD

print(ans)

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) * comb
   ans %= mod
   comb *= (n-(i+1)) * pow(i+1, mod-2, mod)
   comb %= mod
print(ans)

Solution (Python):
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

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

Solution (Python):
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


powers = {(M-1, N-1): pow(M-1, N-1, mod)}


def power(x, y):
    if y == 0:
        return 1
    if (x, y) not in powers:
        powers[(x, y)] = powers[(x, y+1)] * inv(x)
        powers[(x, y)] %= mod
    return powers[(x, y)]


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

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
    def __init__(self,mod=10**9+7,n_max=1):
        self.mod,self.n_max=mod,n_max
        self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
        if 1<n_max:setup_table(n_max)
    def comb(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[self.mod%i]*(self.mod//i)%self.mod)
            self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
        self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Solution (Python):
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 calc(self, n, k):  
        return self.fac[n] * self.invmod[k] % MOD * self.invmod[n - k] % MOD


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

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

print(ans)

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline




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 = MOD 
N = 5*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 )


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

Solution (Python):
from collections import defaultdict
N,M,K=map(int,input().split())
MOD=998244353
 
def comb(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

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
col=M
 
for x in range(N-1,-1,-1):
  now=col*comb(N-1,x,MOD)%MOD
  if x<=K:
    ans = (ans+now)%MOD
  col =col*(M-1)%MOD

print(ans%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)

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 = 10 ** 6  
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)

result=0

for pair in range(k+1):
    result+=m*pow(m - 1, n - 1 - pair, p) *cmb(n-1, pair, p)
    


print(result%p)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
  def __init__(self,mod=10**9+7,n_max=1):
    self.mod,self.n_max=mod,n_max
    self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
    if 1<n_max:setup_table(n_max) 
  def comb(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[self.mod%i]*(self.mod//i)%self.mod)
      self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
    self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

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



ans = 0

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 = n
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 )






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

print(ans%mod)

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

MOD = 998244353

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

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

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

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

Solution (Python):







DIV = 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 ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV
  
import sys
readline = sys.stdin.readline

N,M,K = map(int,readline().split())
ans = 0
for i in range(K + 1):
  
  a = nCr(N-1,i,DIV)

  
  
  P = N - i
  b = ((M % DIV) * pow(M-1,P-1,DIV)) % DIV
  
  ans += (a * b) % DIV
  ans %= DIV
  
print(ans)

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

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

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
col=M

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

print(ans%MOD)

Solution (Python):
import sys

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 make_combination(n):
        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)

        comb = [0 for _ in range(n+1)]
        for r in range(n+1):
            comb[r] = fact[n] * factinv[r] * factinv[n-r] % MOD

        return list(map(ModInt, comb))

input = sys.stdin.readline

N, M, K = map(int, input().split())
comb = ModInt.make_combination(N-1)

ans = 0

for x in range(K+1):
    ans += comb[x]*M*pow(M-1, N-x-1, MOD)

print(ans)

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

def modpow(x, n, m): 
    if n == 0:
        return 1
    res = modpow(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res


def modInv(x, m):
    return modpow(x, m-2, m) % m

class modComb:
    def __init__(self,maxN,mod=10**9+7):
        self.maxN=maxN
        self.mod=mod
        self.fac=[None]*(maxN+1) 
        self.ifac=[None]*(maxN+1)
    def calc_fact(self): 
        self.fac[0]=1
        for i in range(1,self.maxN+1):
            self.fac[i] = self.fac[i-1]*i % self.mod
        self.ifac[-1] = modInv(self.fac[-1],self.mod)
        for i in range(self.maxN,0,-1):
            self.ifac[i-1] = self.ifac[i]*i % self.mod
    def modnCr(self,n, r,mod=None):
        if mod is None:
            mod=self.mod
        denom = self.fac[n]
        numer = self.ifac[r] * self.ifac[n-r] % mod
        return  denom * numer % mod

table=modComb(n,mod)
table.calc_fact()
ans=0
for i in range(k+1):
    ans += m % mod * modpow(m-1, n-i-1, mod) % mod * table.modnCr(n-1, i)%mod
    ans%=mod
print(ans)

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


MAX_N = 10**6

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

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

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


for x in range(0,k+1):
  ans+=m*pow(m-1,n-1-x,mod)*mod_comb_k(n-1,x,mod)
  ans%=mod
if ans<0:
  ans+=mod
print(ans)

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

mod=998244353
ans=0


MAX_N = 10**6

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

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

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


for x in range(0,k+1):
  ans+=m*pow(m-1,n-1-x,mod)*mod_comb_k(n-1,x,mod)
  ans%=mod
if ans<0:
  ans+=mod
print(ans)

Solution (Python):
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 calc(self, n, k):  
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

n, m, k = map(int, input().split())
C = Combination(n)
ans = 0

for i in range(k+1):
    q = n - i - 1
    tmp = m*pow(m-1, q, mod) * C.calc(n-1, i)%mod
    ans = (ans+tmp)%mod

print(ans)

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

mod=998244353


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

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


def cmb(n,r,mod):
    if r<0 or n<r:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod
    
ans=0
for i in range(k+1):
    ans+=(cmb(n-1,i,mod)*m*pow(m-1,n-i-1,mod))%mod
    ans%mod
print(ans%mod)

Solution (Python):
mod = 998244353


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

power_cache = {}
power_cache[(M-1, 0)] = 1
for i in range(N-1):
    power_cache[(M-1, i+1)] = (power_cache[(M-1, i)]*(M-1)) % mod


def power(x, y):
    return power_cache[(x, y)]


combination_cache = {}
combination_cache[(N-1, 0)] = 1
for i in range(0, K+1):
    i_plus_inverse = pow(i+1, mod-2, mod)
    combination_cache[(N-1, i+1)] = (combination_cache[(N-1, i)
                                                       ]*(N-1-i)*i_plus_inverse) % mod


def combination(n, r):
    return combination_cache[(n, r)]


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

print(ans)

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

c = 1

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

Solution (Python):
import sys
sys.setrecursionlimit(10**5)


geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

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

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % 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[self.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)

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

print(ans)

Solution (Python):


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

modulus = 998244353







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

choose = [1]  
for i in range(1, n):
    choose.append(choose[-1] * (n-1-i+1) * inv(i) % modulus)

def solve(n, k):
    x = m * pow(m-1, n-k-1, modulus)
    return x * choose[n-k-1] % modulus

print(sum(solve(n, i) for i in range(k+1)) % modulus)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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[self.mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=Facts(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.cmb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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[self.mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=Facts(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.cmb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,K = LI()

    d = [0] * N
    d[0] = M

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

    c = 1
    ans = 0
    for i in range(K+1):
        ans = (ans + d[N-1-i] * c) % MOD
        c = (c * (N-1-i) * pow(i+1,MOD-2,MOD)) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def fact(k, mod):
    a = [0] * (k + 1)
    a[0] = 1
    for i in range(1, k + 1):
        a[i] = a[i - 1] * i      
        a[i] = a[i] % mod
    return a
def power(a, n, mod):    
    if n == 0:
        return 1
    if n == 1:
        return a % mod
    if n % 2 == 0:
        return power((a * a) % mod, n // 2, mod) % mod
    else:
        return ((a % mod) * power(a % mod, n - 1, mod)) % mod
def inv(a, mod):
    c = [0] * (len(a))
    for i in range(len(a)):
        c[i] = power(a[i], mod - 2, mod)
    return c
n, m, k = [int(i) for i in input().split()]
mod = 998244353
res = fact(n - 1, mod)
res2 = inv(res, mod)
total = 0
base = power(m - 1, n - 1 - k, mod)
dp = [0] * (k + 1)
dp[0] = base
for i in range(1, k + 1):
    dp[i] = dp[i - 1] * (m - 1)
    dp[i] = dp[i] % mod
for i in range(k + 1):
    fact = (res2[i] * res2[n - 1 - i] * m) % mod
    total += (res[n - 1] * fact * dp[k - i]) % mod
    total = total % mod
print(total)

Solution (Python):
n,m,k=(int(i) for i in input().split())
mod = 998244353
fac=[1]
inv=[]
for i in range(n-1):
  fac.append(fac[-1]*(i+2)%mod)
for i in range(n):
  inv.append(pow(fac[i],mod-2,mod))
def modcom(n,k,fac,inv):
  if k>n or k<0:
    return 0
  elif k==n or k==0:
    return 1
  else:
    return((fac[n-1]*inv[k-1]*inv[n-k-1])%mod)
r=0
for i in range(0,k+1):
  r+=(m%mod)*pow(m-1,n-1-i,mod)*modcom(n-1,i,fac,inv)
print(r%mod)

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*zenpou[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)
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=zenpou[n-x-1:]
zenpou.reverse()




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

print(ans)