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

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):
mod = 998244353
max = (10**5)*2 + 1
facts = [1 for i in range(max)]
invs = [1 for i in range(max)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,r):
    return facts[n]*invs[r] * invs[n-r] % mod



N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
    ans += pow(M-1, N-1-i, mod) * nCk(N-1, i)
    ans %= mod
ans *= M
print(ans%mod)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,K=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=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
    
    fac,finv,inv=COMinit(N+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for i in range(K+1):
        ans+=COM(N-1,i)*M*pow(M-1,N-i-1,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

MOD = 998244353  


class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  
        self.invModulos = [0, 1]  
        self.invFactorial_ = [1, 1]  

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def choose_k_from_n(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, M: int, K: int):
    sum = 0
    C = Combination(MOD)
    for i in range(K+1):
        sum = (sum+C.choose_k_from_n(N-1,i)*M*powm(M-1,N-1 - i,MOD))%MOD
    print(sum)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, M, K)

if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys


sys.setrecursionlimit(2000)

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

mod = 998244353
n, m, k = [int(_) for _ in input().split()]


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 += g1[n-1] * g2[n-1-i] * m * pow(m-1, n-1-i, mod) * g2[i]
    ans %= mod


print(ans)

Solution (Python):
class combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

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


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

ans = 0
for k in range(K+1):
    ncr = c.choose(N-1, k) if k > 0 else 1
    t = ncr*M*pow(M-1, N-k-1, MOD)
    ans = (ans+t) % MOD
print(ans)

Solution (Python):
def gcd(a, b):
	'''最大公約数'''
	while b != 0:
		a, b = b, a % b
	return a

def lcm(a, b):
	'''最小公倍数'''
	return (a * b) // gcd(a, b)

def ex_gcd(a, b):
	'''拡張ユークリッドアルゴリズム'''
	x1, x2 = 0, 1
	y1, y2 = 1, 0
	q = 0
	while b != 0:
		x1, x2 = x2, x1 - q * x2
		y1, y2 = y2, y1 - q * y2
		q = a // b
		a, b = b, a % b
	return a, x2, y2

def gcd_n(a, *numbers):
	'''複数の数の最大公約数'''
	d = a
	for b in numbers:
		d = gcd(d, b)
	return d

def lcm_n(a, *numbers):
	'''複数の数の最小公倍数'''
	m = a
	for b in numbers:
		m = lcm(m, b)
	return m

def factorize(n):
	'''素因数分解'''
	factor = 2
	factors = []
	while factor * factor <= n:
		if n % factor == 0:
			count = 1
			n //= factor
			while n % factor == 0:
				n //= factor
				count += 1
			factors.append((factor, count))
		factor += 1
	if n != 1:
		factors.append((n, 1))
	return factors

def totient(n):
	'''オイラーのトーシェント関数'''
	phi = 1
	for prime, count in factorize(n):
		phi *= (prime - 1) * (prime ** (count - 1))
	return phi

def carmichael(n):
	'''カーマイケル関数'''
	prime_carmichaels = [1]
	for prime, count in factorize(n):
		if prime == 2:
			prime_carmichaels.append(count if count <= 2 else (2 ** (count - 2)))
		else:
			prime_carmichaels.append((prime - 1) * (prime ** (count - 1)))
	return lcm_n(*prime_carmichaels)


class Modulo (object):
	def __init__(self, mod):
		self.mod = mod
		self.carmichael = carmichael(mod)
	
	def add(self, x, y):
		return (x + y) % self.mod
	
	def sub(self, x, y):
		return (x - y) % self.mod
	
	def mul(self, x, y):
		return (x * y) % self.mod
	
	def div(self, x, y):
		return self.mul(x, self.inv(y))
	
	def inv(self, x):
		return self.pow(x, self.carmichael - 1)
	
	def pow(self, x, count):
		return pow(x, count, self.mod)


from functools import reduce


MOD = Modulo(998244353)

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

F = [1] * N
for n in range(1, N):
	F[n] = MOD.mul(F[n-1], n)

print(
	reduce(
		MOD.add,
		(
			MOD.mul(
				MOD.div(
					F[N-1],
					MOD.mul(F[k], F[(N-1)-k])
				),
				MOD.mul(
					M,
					MOD.pow(M-1, (N-k)-1)
				)
			)
			for k in range(K+1)
		)
	)
)

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

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

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

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

Solution (Python):
MOD = 998244353

N, M, K = map(int, input().split())
frac = [1]
for i in range(N):
    frac.append(frac[i]*(i+1)%MOD)


def comb(n, k, mod):
    a=frac[n]
    b=frac[k]
    c=frac[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
  
def main():
  ans = [0] * (K+1)
  temp = 1
  for i in range(N):
    if i == 0:
      temp*=M
      temp %= MOD
    else:
      temp *= (M-1)
      temp %= MOD
    if i+1 >= N-K:
      ans[i+1-N+K] = temp
  t_ans = 0
  for i in range(len(ans)):
    key = comb(N-1, i, MOD)
    t_ans += (ans[-1-i]*key)
    t_ans %= MOD
  print(t_ans)
if __name__ == "__main__":
  main()

Solution (Python):

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
POWER = []
cur = 1
for k in range(K+1):
    NcK.append(cur)
    cur *= (N-1-k)* mod_inv(k+1,MOD)
    cur %= MOD    

ans = 0
Power = 1
for k in range(N-1-K):
    Power *= M-1
    Power %= MOD

for k in range(K,-1,-1):
    ans += Power * NcK[k]
        
    if k:
        Power *= M-1
        Power %= MOD
    

print((M*ans)%MOD)

Solution (Python):
N,M,K = map(int,(input().split()))
MOD = 998244353
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

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

print(ans)

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

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

Solution (Python):
mod = 998244353 
N = 2 * (10**5)
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

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

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

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

if __name__ == '__main__':
    main()

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

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

cmbarr = [1] * N
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD

A = [M*pow(M-1,N-1-i,MOD)*cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)

Solution (Python):
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


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

MOD = 998244353
modFacts, invs = prepare(2 * N)
ans = 0
for k in range(K + 1):
    num = N - k
    cnt = 1
    if num >= 0:
        cnt *= modFacts[N - 1] * invs[N - 1 - (num - 1)] * invs[num - 1]
        cnt %= MOD
        cnt *= M * pow(M - 1, num - 1, MOD)
        cnt %= MOD
    ans += cnt
    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)
f = pow(m-1,mod-2,mod) 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

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

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

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

p = 998244353

cnt = 0
com = 1
for k in range(K+1):
    l = N-k
    
    
    
    x = pow((M-1),(l-1),p)
    cnt += M * x * com
    cnt %= p

    
    com *= N-(k+1)
    com *= pow(k+1,p-2,p)
    com %= p


print(cnt)

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-(i+1), MOD) % MOD * COM(N-1, i)
print(ans % MOD)

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

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1:
  if K<N-1:
    print(0)
  else:
    print(1)
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if r >= n:
        return 1
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod

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

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

Solution (Python):
mod=998244353




def find_power(n,mod):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod):
    
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)



N,M,K=map(int,input().split())
dp=[0 for i in range(N+1)]

ans=M*pow(M-1,N-1,mod)

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

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

N = 10 ** 6


inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]


kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)


def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

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

if m == 1 and k == n-1:
    print(1)
else:
    print(ans)

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

def fn(n, m):
  return (m*pow(m-1, n-1, MOD))%MOD

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n):
  fact.append((fact[-1]*i) % MOD)
  inv.append((-inv[MOD % i] * (MOD // i) % MOD))
  factinv.append((factinv[-1] * inv[-1]) % MOD)
  
def nCr(n, r):
    return fact[n] * factinv[r] * factinv[n-r] % MOD

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

Solution (Python):
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

ans=0
a=1
MOD=998244353
fac, ifac = make_tables(MOD, n-1)
        
for i in range(k+1):
    ans+=m*pow(m-1,n-1-i,998244353)*cmb(n-1, i, MOD, fac, ifac)
print(ans%998244353)

Solution (Python):
n,m,k=[int(x) for x in input().split()]

if m==1:
  if k==n-1: print(1)
  else: print(0)
  exit()
sumi=0
mod=998244353
prodi=pow(m-1,n-1,mod)
invi=pow(m-1,mod-2,mod)
for j in range(n-1,n-1-k-1,-1):
  sumi+=prodi
  sumi%=mod
  prodi*=j
  prodi%=mod
  prodi*=pow(n-j,mod-2,mod)
  prodi%=mod
  prodi*=invi
  prodi%=mod 
sumi*=m
sumi%=mod
print(sumi)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353


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

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

print(ans*m%mod)

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

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

for i in range( 2, N + 1 ):
    fac.append( ( fac[-1] * i ) % MOD )
    inv.append( ( -inv[MOD % i] * (MOD//i) ) % MOD )
    facinv.append( (facinv[-1] * inv[-1]) % MOD )

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n-r] % MOD

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

print(sum % MOD)

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


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, readline().split())
mod = 998244353
comb = Combination(n)
ans = 0
n -= 1
for i in range(k + 1):
    ans += comb.calc(n, n - i) * m * pow(m - 1, n - i, mod) % mod
    ans %= mod
print(ans)

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

mod = 998244353
inv_t = [0]+[1]
inv_te = [0 for i in range(n+1)]
inv_te[0] = 1
inv_te[1] = 1
for i in range(2,n+1):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
  inv_te[i] = (inv_te[i-1] * inv_t[i]) % mod

n_minus1_mod = 1
for i in range(2,n):
    n_minus1_mod *= i
    n_minus1_mod %= mod

ans = 0

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

print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,k = map(int,readline().split())
mod = 998244353
 
if m == 1:
    if k < n-1:
        print(0)
    else:
        print(1)
    exit()

def pow(n,p,mod=mod): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def factrial_memo(n=2*10**5,mod=mod):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
fact = factrial_memo()

def fermat_cmb(n, r, mod=mod): 
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
ans = 0
for i in range(k+1):
    res = m*pow(m-1,n-1-i) 
    ans += res*fermat_cmb(n-1,i)%mod
print(ans%mod)

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

Solution (Python):
def a():
    mod = 998244353
    o = [0] * 63

    def bi(x):
        i = 0
        while x != 0:
            o[i] = x%2
            x //= 2
            i += 1

    bi(mod-2)

    def modinv(m):
        b = 1
        p = m
        for i in range(63):
            if i:
                p = (p * p)%mod
            if o[i]:
                b *= p
                b %= mod
        return b

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

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

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

    ans = 0
    for k in range(0,K+1):
        ans += C[k] * M * M1[N-k-1]
        ans %= mod

    print(ans)

a()

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    
    
    
    
    import math
    
    input = stdin.readline

    p = 998244353

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

    
    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)

    def pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

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

        return (K * x)%p

    n, m, k = map(int, input().split())
    if m == 1:
        if k < n-1:
            print(0)
        else:
            print(1)
        exit()

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


    ans = ans*m
    print(ans%p)

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

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

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 )



ans = 0
rbase = 1
for i in range(n-1-k):
    rbase *= (m-1)
    rbase %= mod

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

print(ans%mod)

Solution (Python):
def main():
  mod=998244353
  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
  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=m*pow(m-1,n-1,mod)
  ans%=mod
  for i in range(1,k+1):
    ans+=(m*pow(m-1,n-1-i,mod))%mod*cmb(n-1,i,mod)
    ans%=mod
  print(ans)
  
if __name__=='__main__':
  main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


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=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        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 power(a, n):
    x = 1
    while n:
        if n & 1:
            x = x * a % MOD
        n >>= 1
        a = a * a % MOD
    return x


def main():
    N, M, K = map(int, input().split())
    answer = 0
    combination = Combination(2 * 10 ** 5 + 1, MOD)
    for i in range(K + 1):
        answer += M * power(M - 1, N - i - 1) * combination(N - 1, i) % MOD
    print(answer % MOD)


if __name__ == "__main__":
    main()