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

def prepare(n, MOD):
    
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-1,MOD))%MOD
for x in range(k,-1,-1):
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
    s*=(m-1)
    s%=MOD
print(ans)

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

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


def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r==0 or r==n:
        return 1
    else:
        return fac[n] * inv[r] * inv[n - r] % mod

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

print(ans)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353
numden = [(1, 1)]


def combmod(n, k, mod=MOD):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    
    if k < len(numden):
        num, den = numden[k]
    else:
        
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % mod
            den = den * (i + 1) % mod
            numden.append((num, den))
    
    
    
    inv_dev = pow(den, mod - 2, mod)
    return num * inv_dev % mod


def solve():
    ans = 0
    for i in range(K + 1):
        cs = combmod(N - 1, i)
        ans += cs * M % MOD * pow(M - 1, N - 1 - i, MOD) % MOD
        ans %= MOD
    return ans


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

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 998244353

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class Combination:
    def __init__(self, max_n=100007, mod=mod):
        self.mod = mod
        self.fac = [0] * max_n
        self.finv = [0] * max_n
        self.inv = [0] * max_n

        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, max_n):
            self.fac[i] = self.fac[i - 1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % self.mod
    
    def choose(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.mod) % self.mod
    

def modpow(n, p, m):
    if p == 0:
        return 1
    if p % 2 == 0:
        t = modpow(n, p // 2, m)
        return t * t % m
    return n * modpow(n, p - 1, m) % m

n, m, k = na()
C = Combination(10 ** 5 * 4)
ans = 0
for i in range(k + 1):
    ans += C.choose(n - 1, i) * m % mod * modpow(m - 1, n - i - 1, mod) % mod

print(ans % mod)

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

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


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

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

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

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

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

comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p

print(res)

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 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


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

Solution (Python):
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())
mod = 998244353
c = Combination(n)

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

print(ans)

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

MOD = 998244353




NN = N-1
MAX = K + 1
com = [0] * MAX
def COM2init():
    com[0] = 1
    for i in range(1, MAX):
        if i > NN: break
        com[i] = (com[i-1] * (NN-i+1) % MOD) * pow(i, MOD-2, MOD) % MOD
COM2init()

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

Solution (Python):
def cmb(n,r,p):
    if r<0 or r>n:
        return 0
    r = min(r,n-r)
    return fact[n] * factinv[r] *factinv[n-r] % p
p =  998244353
N = 2*(10**5)+1

fact=[1,1] 
factinv = [1,1] 
inv = [0,1] 

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


    

n,m,k = map(int,input().split())
ans = 0
beki = [1,m-1]
for i in range(2,N+1):
    beki.append(((beki[-1]*(m-1)) % p))
for x in range(k+1):
    ans += (((cmb(n-1,n-x-1,p) * m) %p)*beki[n-x-1]) %p
    ans = ans % p
print(ans)

Solution (Python):
import math
N,M,K=map(int,input().split())
mod=998244353
ans=0
d=[1]+[1]
e=[0]+[1]
f=[0]+[1]

for i in range(2,N+1):
  d += [d[i-1]*i%mod]
  e += [ e[mod % i] * (mod - int(mod / i)) % mod]
  f += [ f[i-1]*e[i]%mod]
def combinations_count(n, r):
  if r==n or r==0:
    return 1
  return d[n] * f[n-r] * f[r]%mod

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

Solution (Python):
n, m, k = map(int, input().split())
MOD = 998244353
class Combination:
    def __init__(self, N=5*10**5, mod=MOD):
        self.mod = mod
        self.N = N
        self.fact = [1, 1]  
        self.factinv = [1, 1]  
        self.inv = [0, 1]  
        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)
    def nCr(self, n, r):
        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.mod

comb = Combination(2 * 10**5)
ans = 0
for i in range(k+1):
    ans += m * pow(m-1, n-1-i, MOD) * comb.nCr(n-1, i)
    ans %= MOD
print(ans)

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

if m == 1 and n-1 == k:
    print(1)
    sys.exit()



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

count_all = 0
pre_pow = pow(m-1,n-1,mod)
inv_m_mai1 = pow(m-1,mod-2,mod)
for i in range(k+1):
    pattern_color = m*pre_pow%mod
    pattern_place = kai[n-1]*inv[n-1-i]*inv[i]%mod
    count_all = (count_all+pattern_color*pattern_place)%mod
    pre_pow = pre_pow * inv_m_mai1 %mod

print(count_all)

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

p = 998244353

def comb(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%p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1]*inv[i])%p)
ans = 0

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

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


mod=998244353
n,m,k=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

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

print(ans%mod)

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


mod=998244353
n,m,k=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

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

print(ans%mod)

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


def inpl():
    return list(map(int, input().split()))




def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]

    while w[2] != 1:
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]




def mod_inv(a, m):
    x, _ = extGCD(a, m)
    return (x + m) % m


def main():
    MOD = 998244353

    N, M, K = inpl()
    m1 = {}
    m1[0] = 1
    n_comb = {}
    n_comb[0] = 1
    for i in range(1, N + 1):
        m1[i] = (m1[i - 1] * (M - 1)) % MOD
        n_comb[i] = (n_comb[i - 1] * mod_inv(i, MOD) * (N - i)) % MOD

    ans = 0
    for i in range(K + 1):
        ans = (ans + M * n_comb[i] * m1[N - 1 - i]) % MOD

    print(ans)

    return


if __name__ == '__main__':
    main()

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


fact = [1] * (N+1) 
factinv = [1] * (N+1) 



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

def nCk(n,k): 
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD) * nCk(N-1,k)
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

Solution (Python):
MOD = 998244353


def modinv(a):
    return pow(a, MOD - 2, MOD)


def make_tables(N):
    fac = [1, 1]
    inv = [1, 1]
    for i in range(2, N + 1):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(modinv(fac[i]))
    return fac, inv


def ncr(n, r):
    return int(fac[n] * inv[r] * inv[n - r]) % MOD


if __name__ == '__main__':

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

    fac, inv = make_tables(N)

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

    print(ans % MOD)

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

framod=[0]*(2*10**5+1)
framod[0]=1
def xframod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
        framod[i]=a
xframod(2*10**5,mod)

def combmod(n, k, mod):
    a=framod[n]
    b=framod[k]
    c=framod[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
ans=0

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

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

fact = [1,1]
finv = [1,1]
inv = [0,1]

for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

x = m%mod

a = pow(m-1,n-1,mod)
x = (a*x)%mod

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

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

MOD =  998244353
mod = MOD
MAX = N+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

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

print(ans)

Solution (Python):
import math

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

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

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

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

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

mod = 998244353
size = 2*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 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 = map(int,input().split())

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

print(ans)

Solution (Python):
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 2):
    next = C[-1] * (N-i) * pow(i, mod-2, mod)
    C.append(next % mod)

res = 0

for x in range(K+1):
    crt =  (pow(M-1, N-x-1, mod) * M) % mod 
    crt %= mod
    
    idx = min(x, N-1-x)
    crt *= C[idx]
    
    crt %= mod
    res += crt
    res %= mod

print(res)

Solution (Python):

def modpow(x, y, mod):
    ret = 1
    z = x
    n = len(bin(y)) - 2
    for i in range(n):
        if ((y >> i) & 1):
            ret = ret * z % mod
        z = z * z % mod
    return ret

def modinv(x, mod):
    return modpow(x, mod-2, mod)

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

    c1 = 1
    c2 = 1
    for i in range(1, n):
        c1 = c1 * i % mod
        if i == k:
            c2 = modinv(c1, mod)
    c3 = modinv(c1, mod)
    c3_list = [0] * (k+1)
    c3_list[k] = c3
    for i in range(k-1, -1, -1):
        c3 = c3 * (n-(k-i)) % mod
        c3_list[i] = c3
    comb = (c1 * c2 % mod) * c3_list[0] % mod

    x = m * modpow(m-1, n-k-1, mod) % mod

    ret = x * comb % mod

    for i in range(1, k+1):
        c2 =c2 * (k-i+1) % mod
        comb = (c1 * c2 % mod) * c3_list[i] % mod
        x = x * (m-1) % mod

        ret += x * comb % mod
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

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

f = [(1,1), ]

def ncr(n,r,p):
    num = (f[-1][0] * (n-(r-1))) % p
    den = (f[-1][1] * ((r-1) + 1)) % p
    f.append([num, den])
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0

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

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

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

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

Solution (Python):

import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)
def run():
    N,M,K = map(int, input().split())
    mod = 998244353
    modM = [1]
    for x in range(1,N):
        val = modM[-1] * (M-1)
        val %= mod
        modM.append(val)

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        if n < 2:
            return ret[:n+1]

        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(N-1, mod)

    combs = []
    def comb_mod(n, a, mod):
        """
        return: [n, a] % mod
        Note: mod must be a prime number
        """
        combs.append(1)
        ret = 1
        for i in range(1, a+1):
            ret *= n-i+1
            ret %= mod
            ret *= inv[i]
            ret %= mod
            combs.append(ret)
        return None
    comb_mod(N-1, N-1, mod)


    ret = 0
    for k in range(K+1):
        tmp = (modM[N-1-k] * M) % mod
        tmp *= combs[k]
        tmp %= mod
        ret += tmp
        ret %= mod
    print(ret%mod)

if __name__ == "__main__":
    run()

Solution (Python):
mod = 998244353

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

frac = [0] * (n + 1)
frac[0] = frac[1] = 1

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

inv_frac = [0] * (n + 1)
inv_frac[n] = pow(frac[n], mod - 2, mod)

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

ans = 0

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

print(ans)

Solution (Python):

def resolve():
    
    def COMinit(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 Combination(n, k, MOD=998244353):
        
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    
    fac, finv = COMinit(N-1, MOD)
    m_mod = [1]
    for _ in range(N):
        m_mod.append(m_mod[-1] * (M - 1) % MOD)

    ans = 0
    for k in range(K+1):
        cmb = Combination(N-1, k)
        ans += (M%MOD) * (m_mod[N-k-1]%MOD) * cmb
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

def resolve():
    
    def COMinit(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 Combination(n, k, MOD=998244353):
        
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret
 
    MOD = 998244353
    N, M, K = map(int, inp().split())
 
    
    fac, finv = COMinit(N-1, MOD)
 
    ans = 0
    for k in range(K+1):
        cmb = Combination(N-1, k)
        m_pow = pow(M-1, (N-k-1), MOD)
        ans += M * m_pow * cmb
        ans %= MOD
 
    print(ans)
  
if __name__ == "__main__":
    resolve()

Solution (Python):
def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

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

mod = 998244353
fact = [1, 1]
factinv = [1, 1]
inv = [0,1]
rui = [1,m-1]

for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    rui.append(rui[-1]*(m-1) % mod)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, K = lr()
    MOD = 998244353
    SIZE = 4*10**5+1
    SIZE += 1
    inv = [0]*SIZE  
    fac = [0]*SIZE  
    finv = [0]*SIZE 
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    def choose(n,r): 
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = 0
    for i in range(K+1):
        ans += choose(N-1, i)*M*pow((M-1), N-1-i, MOD)%MOD
        ans %= MOD
    print(ans)
resolve()

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 998244353
 
MAX_N = 2 * 10**5 + 10
 
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
 
fac_inv = [1] + [0] * MAX_N
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD
 
ans = 0
n, m, k = map(int, input().split())
 
for i in range(k + 1):
    orig = n - i
    cnt = m * pow(m - 1, orig - 1, MOD)
    cnt = cnt * mod_nCr(n-1, i)
    ans += cnt
    ans %= MOD
print(ans)

Solution (Python):
MOD = 998244353
list_size = 200001

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

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

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

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

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

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

Solution (Python):

def resolve():
    
    def COMinit(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 Combination(n, k, MOD=998244353):
        
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    
    fac, finv = COMinit(N-1, MOD)

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

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
MOD=998244353
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

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

N,M,K=map(int,input().split())
fac,finv,inv=facinv(N)
mm=[1]
for i in range(N+1):
    mm.append(mm[-1]*(M-1)%MOD)
ans=0
for i in range(K+1):
    ans=(ans+(COM(N-1,N-i-1)*M%MOD*mm[N-i-1]%MOD))%MOD
print(ans)

Solution (Python):
U = 2*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Solution (Python):
import math


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        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


def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    ans = 0
    comb = Combination(10**6)
    for k in range(K+1):
        tmp = M * pow(M-1,N-(k+1),MOD)
        tmp %= MOD
        ans += tmp * comb(N-1,k)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def binom(n,r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def power(n,r):
    res = 1
    for i in range(r):
        res *= n
        res %= p
    return res

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

p = 998244353

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

num = 0

pw = (m-1)**(n-k-1) % p

for i in range(k+1):
    num += m * pw * binom(n-1, k - i)
    num %= p
    pw *= m-1
    pw %= p

print(num)

Solution (Python):
def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans



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


ans=0
for i in range(0,K+1):
  R = ( (M%p) *pow(M-1,N-1-i,p) )%p
  L = combi(N-1,i)
  ans = (ans + (R*L)%p)%p
  
print(ans)

Solution (Python):
n,m,k=map(int,input().split())
ans=0
mod=998244353
c=1
for i in range(k+1):
    ans+=c*m*pow(m-1,n-i-1,mod)
    ans%=mod
    c*=(n-i-1)*pow(i+1,mod-2,mod)
    c%=mod
print(ans)

Solution (Python):
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
inv = [1] * N
FAC = factorial(N - 1) % MOD
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for i in range(1, N):
        inv[i] = (inv[i - 1] * pow(i, MOD - 2, MOD)) % MOD
    for k in range(K + 1):
        
        
        
        
        punc = FAC
        
        punc *= inv[k]
        punc = punc % MOD
        
        punc *= inv[N - k - 1]
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)

Solution (Python):
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

Z = 998244353


class Comb:
    def __init__(self, n):
        self.n = n
        self.e = [1] * (n + 1)
        for j in range(n):
            self.e[j + 1] = (self.e[j] * (j + 1)) % Z
    
    def z_pow(self, a, n):
        
        if n == 0:
            return 1
        if n == 1:
            return a % Z
        m = n // 2
        i = n - m * 2
        x = self.z_pow(a, m)
        return (x * x * self.z_pow(a, i)) % Z

    def get(self, i):
        if self.n - i < i:
            return self.get(self.n - i)
        return (self.e[self.n] * self.z_pow(self.e[i], Z - 2) * self.z_pow(self.e[self.n - i], Z - 2)) % Z


def calc(N, M, K):
    comb = Comb(N - 1)
    p = (M * (M - 1) ** (N - 1 - K)) % Z
    r = 0
    for x in range(K, -1, -1):
        r = (r + comb.get(x) * p) % Z
        p = (p * (M - 1)) % Z
    return r
    

(N, M, K) = tuple([int(s) for s in input().split()])
print(calc(N, M, K))