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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

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

cms = 10**6
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod2

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod2) * inv(cm[b]) % mod2

def main():
    n,m,k = LI()
    comb_init()

    a = [0] * n
    a[0] = m
    for i in range(1,n):
        a[i] = a[i-1] * (m-1) % mod2

    r = 0
    for i in range(k+1):
        r += a[n-i-1] * comb(n-1, i)
        r %= mod2

    return r

print(main())

Solution (Python):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n, m, k = map(int, input().split())
ans = 0
c = 998244353

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

Solution (Python):
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


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


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD



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


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

print(ans)

Solution (Python):
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD



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


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

print(ans)

Solution (Python):
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	
	
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD


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


ans = 0
for i in range(k + 1):
	tmp = m * bigmod(m - 1, n - 1 - i) * ncr(n - 1, i)
	tmp %= MOD
	ans = (ans + tmp) % MOD

print(ans)

Solution (Python):
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	up = fact[nn]
	down = (invFact[rr] * invFact[nn - rr]) % MOD
	return (up * down) % MOD


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






ans = 0
for i in range(k + 1):
	tmp = m * bigmod(m - 1, n - 1 - i) * ncr(n - 1, i)
	tmp %= MOD
	ans = (ans + tmp) % MOD

print(ans)

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

ans = 0

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % MOD
        self.ifact[n] = pow(self.fact[n], MOD-2, MOD)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % MOD
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %MOD
        return comb
comb = combination(N)

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

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

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

Solution (Python):
def main():
    n, m, k = map(int, input().split())
    MOD = 998244353
    ans = 0
    c = 1

    for i in range(k + 1):
        ans += (((m * pow(m - 1, n - i - 1, MOD)) % MOD) * c) % MOD
        ans %= MOD
        c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD
        
        
    print(ans % MOD)
    
if __name__ == '__main__':
    main()

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

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

Solution (Python):
def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


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

    nCi = [1]
    for i in range(1, N):
        nCi.append(nCi[i - 1] * (N - i) * inverse(i, mod) % mod)
    ans = 0
    for k in range(K + 1):
        n = N - k
        ans += M * int(pow((M - 1), n - 1, mod)) * nCi[k]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n,m,k=map(int,input().split())
mod = 998244353
nCi = [1]
for i in range(n):
  next = nCi[i]*(n-1-i)*pow(i+1,mod-2,mod)
  next %= mod
  nCi.append(next)

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

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

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

if M == 1:
  if K == N-1:
    print(1)
  else:
    print(0)
  exit()
  
now = M * pow(M-1, N-1, MOD)
ans = now
if K == 0:
  print(ans % MOD)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

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

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)
    m=1
    Mk_array=[1]
    for i in range(1,N):
        m=(m*(M-1))%MOD
        Mk_array.append(m)
    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=Mk_array.pop()

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Solution (Python):
def pre_cmb(N, MOD):
    FACT = [1, 1]  
    INV = [0, 1]  
    FACTINV = [1, 1]  

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Solution (Python):
def pre_cmb(N, MOD):
    FACT = [1, 1]  
    INV = [0, 1]  
    FACTINV = [1, 1]  

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Solution (Python):
def pre_cmb(N, MOD):
    FACT = [1, 1]  
    INV = [0, 1]  
    FACTINV = [1, 1]  

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Solution (Python):
def pre_cmb(N, MOD):
    FACT = [1, 1]  
    INV = [0, 1]  
    FACTINV = [1, 1]  

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Solution (Python):
p = 998244353
N = 2*10**5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

def main():
    n, m, k = [int(i) for i in input().split()]
    res = 0
    for tk in range(0, k+1):
        res = (res + m * cmb(n-1, tk, p) * pow(m-1, n-tk-1, p)) % p
    print(res)

if __name__ == '__main__':
    main()

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

N = 998244353

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % N)
    inverse.append(pow(factorial[-1], N - 2, N))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % N

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)

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


factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD

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

print(ans % MOD)

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

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def gen_mod_combs(places):
  k = 0
  x = 1
  while True:
    yield x
    factor = prime_cycle_division(places-k, k+1)
    x = (x*factor)%prime_mod
    k += 1

def combos(j):
  ans = (m*next(gen))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
gen = gen_mod_combs(n-1)
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Solution (Python):


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




def aug_gcd(a, b):
    lq = []
    while b > 0:
        q = int(a/b)
        r = a % b
        a = b
        b = r
        lq.append(q)
    x = 1
    y = 0
    for i in range(len(lq)):
        tmp = x
        x = y
        y = tmp - lq[(-1)*(i+1)] * y
    return a, x, y



def modinv(a, p):
    inv = aug_gcd(a, p)[1] 
    if(inv < 0):
        inv += p 
    return inv



def N_Combination_k(N, p):
    
    l = [1]
    res = 1
    for i in range(1, N+1):
        res *= (N+1-i)
        res %= p
        res *= modinv(i, p)
        res %= p
        l.append(res)
    return l


combination_N_1 = N_Combination_k(N-1, p)

Cumulative = [0] 
s = 0
tod = 1 
for i in range(N):
    s += M * tod * combination_N_1[(-1)*(i+1)]
    s %= p
    tod *= (M-1)
    tod %= p
    Cumulative.append(s)
    


ans = Cumulative[-1] - Cumulative[(-1)*(K+2)]
if(ans < 0):
    ans += p
print(ans)

Solution (Python):
n, m, k = map(int, input().split())
 
mod = 998244353
 
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
 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
ans = 0
for i in range(k+1):
    col = m * pow(m-1,n-i-1,mod)
    match = cmb(n-1,i,mod)
    ans += col * match
 
print(ans % mod)

Solution (Python):



def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
    
  cnt = 0
  cmb = 1
  for ik in range(k+1):
    ncp = m * pow(m-1, n-ik-1, MAX)
    ncp %= MAX
    
    if ik == 0:
      cmb = 1
    else:
      cmb *= ((n-ik) * pow(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

if __name__=='__main__':
  main()

Solution (Python):

import sys

MOD = 998244353  


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]

    
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD

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

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


if __name__ == '__main__':
    main()

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

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


mod = 998244353 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 


for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
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)

Solution (Python):
MOD = 998244353
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


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


if __name__ == "__main__":
    main()

Solution (Python):
mod = 998244353

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb
        
        
n, m, k = map(int, input().split())

comb = combination(n)

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

Solution (Python):

from collections import Counter
MAX = 1000005
MOD = 998244353
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX



def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD



def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD



COMinit()

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

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

print(ans%MOD)

Solution (Python):
import math
mod = 998244353

import numpy as np
def create_modC(n, mod):
    if n == 0:
        return (lambda r: 1)
    b = int(math.log(mod-2, 2)) + 1
    fac = np.zeros((b, n+1), dtype=np.int64)
    
    inv = np.ones(n+1, dtype=np.int64)
    fac[0, 0], fac[0, 1] = 1, 1
    for i in range(2, n+1):
        fac[0, i] = (fac[0, i-1] * i) % mod
    for i in range(1, b):
        fac[i, :] = (fac[i-1, :] ** 2) % mod

    indice = []
    N = mod - 2
    i = 0
    while N > 0:
        if N % 2 == 1:
            indice.append(i)
        N = N >> 1
        i += 1
    
    for i in indice:
        inv *= fac[i,:]
        inv %= mod
    
    fac = fac[0,:]

    def _modC(r):
        if r == 0 or r == n:
            return 1
        result = fac[n] * inv[n-r]
        result %= mod
        result *= inv[r] % mod
        result %= mod
        return result

    return _modC


def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 60522,114575,7559
    answer = 479519525
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")

    N, M, K = 200000,190000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 1,1,0
    print(f"N={N} M={M} K={K}")
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 200000,200000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    for i in range(100):
        N, M = np.random.randint(200000), np.random.randint(200000)
        K = np.random.randint(N-1)
        v = resolve(N, M, K)
        print(f"N={N} M={M} K={K} {v}")




def main():
    
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    from datetime import datetime
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = create_modC(N-1, mod)
    
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(k)
        v = b 
        v *= c
        v %= mod
        
        
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

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

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

    MOD = 998244353

    class Comb:
        def __init__(self, N):
            self.fac = [1] * (N+1)
            for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

        def __call__(self, n, r):
            return self.comb(n, r)

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

        def permutation(self, n, r):
            if r == 0: return 1
            return self.fac[n] * pow(self.fac[n-r], MOD-2, MOD) % MOD

    comb = Comb(N)

    ans = 0

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

    print(ans)

if __name__ == '__main__':
    main()

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

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

Solution (Python):

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


U=max(N+1,K)
F=[0]*U
G=[0]*U

F[0]=1
for i in range(1,U):
    F[i]=(F[i-1]*i)%C

G[i]=pow(F[-1],C-2,C)

for j in range(U-2,-1,-1):
    G[j]=(G[j+1]*(j+1))%C

def nCr(n,r):
    if r<0 or n<r:
        return 0
    else:
        return (F[n]*G[r]*G[n-r])


S=0
for k in range(0,K+1):
    S=(S+M*pow(M-1,N-k-1,C)*nCr(N-1,k))%C
    
print(S%C)

Solution (Python):

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

P = MOD
Y = max(N, M)
inv_t = [0]+[1]
for i in range(2, Y):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

          
if K == N - 1:
  ans = 1
  for i in range(N):
    ans = ans * M % MOD
  print(ans % MOD)
  quit()
  

  
  
 
  

B = [1] * N
ans1 = 1
for i in range(1, N):
  ans1 = (ans1 * (M - 1)) % MOD
  B[i] = (ans1 * M) % MOD
  
ans = 0
ans2 = 1

for i in range(K + 1):
  if i == 0:
    X = 1
  else:
    X = (X * (N - i) * inv_t[i]) % MOD
  ans2 = X * B[N - 1 - i] % MOD 
  ans += ans2
  ans = ans % MOD
      
print(ans)

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


ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))


p=998244353
N,M,K=nm()

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

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

mod_M=[1,(M-1)%p]
for i in range(2,N):
    mod_M.append((mod_M[i-1]*(M-1))%p)

ans=0
ans+=(M*mod_M[N-1])%p

if(K>0):
    for i in range(1,K+1):
        ans+=(M*mod_M[N-i-1]%p)*comb(N-1,i,p)
        ans%=p

print(ans)

Solution (Python):



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

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % md )
    inverse.append( ( -inverse[md % i] * (md//i) ) % md )
    g2.append( (g2[-1] * inverse[-1]) % md )

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

def cnt(k):
    ret = pow(M-1, N-1-k, md)
    ret *= cmb(N-1,k)
    ret %= md
    ret *= M
    ret %= md
    return ret

def main():
    rt = 0
    for k in range(K+1):
        rt += cnt(k)
        rt %= md
    print(rt)

if __name__ == '__main__':
    main()

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

if __name__ == '__main__':
    main()

Solution (Python):



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

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % md )
    inverse.append( ( -inverse[md % i] * (md//i) ) % md )
    g2.append( (g2[-1] * inverse[-1]) % md )

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

def cnt(k):
    ret = pow(M-1, N-1-k, md)
    ret *= cmb(N-1,k)
    ret %= md
    ret *= M
    ret %= md
    return ret

def main():
    rt = 0
    for k in range(K+1):
        rt += cnt(k)
        rt %= md
    print(rt)

if __name__ == '__main__':
    main()

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

mod=998244353

ans=0

comb=[1]
for i in range(K):
    comb_temp=comb[i]*(N-1-i)*pow(i+1,-1,mod)
    comb_temp%=mod
    comb.append(comb_temp)

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

print(ans)

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

    class CombiMod:
        ''' combination mod prime '''

        def __init__(self, N, Mod):
            ''' 前計算 '''
            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.finv = [1] * (N+1)  
            self.finv[N] = pow(self.fac[N], self.mod-2, self.mod)
            for i in range(N, 0, -1):
                self.finv[i-1] = (self.finv[i] * i) % self.mod

        def __call__(self, n: int, k: int):
            ''' nCkを実際に計算する '''
            if k < 0 or n < k: return 0
            ret = self.fac[n] * self.finv[k] % self.mod
            ret = ret * self.finv[n-k] % self.mod
            return ret

    cmb = CombiMod(N, Mod)
    ans = 0

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

abc167_e()

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

MOD = 998244353 
N = 1000000
modinv_t = [0, 1]
modfact_t = [1, 1]
modfactinv_t = [1, 1]
for i in range(2,N+1):
  modfact_t.append(modfact_t[-1] * i % MOD)
  modinv_t.append(modinv_t[MOD%i] * (MOD-(MOD//i)) % MOD)
  modfactinv_t.append(modfactinv_t[-1] * modinv_t[-1] % MOD)

def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD

def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD

def nHr(n, r):
  return  nCr(n+r-1,r)


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

t = M*pow(M-1,N-1,MOD) % MOD
for i in range(1,K+1):
  t += M*pow(M-1,N-1-i,MOD)*nCr((N-1),i)
  t %= MOD

print(t)

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