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 sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

    N,M,K = LMIIS()
    ans = 0
    cmb = Combinations(N-1,MOD)
    
    powtable = [0] * N
    powtable[N-K-1] = pow(M-1,N-K-1,MOD) % MOD
    for i in range(N-K,N):
        powtable[i] = powtable[i-1] * (M-1) % MOD

    for i in range(K+1):
        ans += powtable[N-i-1] * cmb.nCr(i)
        ans %= MOD
    
    
    
    print(ans*M%MOD)

    

if __name__ == '__main__':
    main()

Solution (Python):
import sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

    N,M,K = LMIIS()
    ans = 0
    cmb = Combinations(N-1,MOD)
    
    powtable = [0] * N
    powtable[N-K-1] = M * pow(M-1,N-K-1,MOD) % MOD
    for i in range(N-K,N):
        powtable[i] = powtable[i-1] * (M-1) % MOD

    for i in range(K+1):
        ans += powtable[N-i-1] * cmb.nCr(i)
        ans %= MOD
    
    
    
    print(ans)

    

if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    N, M, K = map(int, input().split())

    
    mod = 998244353

    n_ = 4*10**5 + 5
    fun = [1]*(n_+1)
    for i in range(1,n_+1):
        fun[i] = fun[i-1]*i%mod
    rev = [1]*(n_+1)
    rev[n_] = pow(fun[n_],mod-2,mod)
    for i in range(n_-1,0,-1):
        rev[i] = rev[i+1]*(i+1)%mod
    def cmb(n,r):
        if n <= 0 or r < 0 or r > n: return 0
        return fun[n]*rev[r]%mod*rev[n-r]%mod

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

    answer %= mod

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

    print(answer)
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

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

    

if __name__ == '__main__':
    main()

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

frac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  frac[i] = i*frac[i-1]%MOD
  
inv[n] = pow(frac[n], MOD-2, MOD)
for i in range(n-1, 0, -1):
  inv[i] = inv[i+1]*(i+1)%MOD
  
def nCr(n,r):
  res = frac[n]*inv[n-r]%MOD
  res = res*inv[r]%MOD
  return res
  
ans  = 0
for i in range(k+1):
  num_pair_block = i + 1
  num_seg = n-i
  ans += m*pow(m-1, num_seg-1, MOD)*nCr(n-1, i)%MOD
  ans %= MOD
  
print(ans)

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


def comb(n,k, mod):
    return (fact[n] * finv[k] * finv[n-k]) % mod



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

Solution (Python):
def main():
    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 comb(n,k): 
        return fact[n] * factinv[n-k] * factinv[k] % MOD

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

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

main()

Solution (Python):
import math
import numpy as np

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

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

class combination:
    def __init__(self, n, mod = 10**9 + 7):
        self.MOD = mod
        self.to = np.ones(n,dtype=np.int64)
        self.rev = np.ones(n,dtype=np.int64)
        for i in range(1, n):
            self.to[i] = self.to[i-1] * i % mod
        self.rev[-1] = inv(int(self.to[-1]),mod)
        for i in range(n-1, 0, -1):
            self.rev[i-1] = self.rev[i] * i % mod
    
    def nCk(self, n ,k):
        return self.to[n] * self.rev[k] % self.MOD * self.rev[n-k] % self.MOD

MOD = 998244353

n,m,k = NextInts()

cob = combination(200200, MOD)
ans = 0

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

print(ans)

Solution (Python):
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

mod = 998244353

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

mc = ModComb(N, mod)

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

print(ans)

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 = n+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[-1]) % p)

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 += m * beki[n-x-1] %p * cmb(n-1,x,p) %p
    ans = ans % p
print(ans)

Solution (Python):
A,B,C=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)

i=0
ans=0
while i<=C:
    ans+=B*pow(B-1,A-1-i,p)*cmb(A-1,i,p)
    i+=1

ans=ans%p
print(ans)

Solution (Python):

import sys
readline = sys.stdin.readline

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


f = [1]
for i in range(N):
    f.append(f[i] * (i+1) % MOD)

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


def comb_mod(n, r, p):
    return (f[n] * f_inv[r] * f_inv[n-r])%p

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

print(ans)

Solution (Python):
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 998244353
class Combination(object):
    def __init__(self, N, MOD):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

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

    print(ans)


if __name__ == '__main__':
    main()

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

mod=998244353

MAX_N=n+5
fac = [1,1] + [0]*MAX_N
finv = [1,1] + [0]*MAX_N
inv = [0,1] + [0]*MAX_N
for i in range(2,MAX_N):
  fac[i] = fac[i-1] * i % mod
  inv[i] = mod - inv[mod % i] * (mod // i) % mod
  finv[i] = finv[i-1] * inv[i] % mod

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

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

print(ans)

Solution (Python):

def binomials_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: [n choose 0 mod p, n choose 1 mod p, ..., n choose k mod p]
    '''
    binomials = [1, n] 
    inv = [0, 1] 
    for i in range(2, k + 1):
        inv.append(( inv[p % i] * (p - p//i) ) % p ) 
        binomials.append(binomials[i - 1] * (n - i + 1) * inv[i] % p)

    return binomials


def exp_by_sq_p(a, n, p):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = a % p
    elif  n % 2 == 0:
        exp = exp_by_sq_p(a * a % p, n // 2, p)
    else:
        exp = a * exp_by_sq_p(a * a % p, (n - 1) // 2, p) % p
    return exp % p

N, M, K = [int(x) for x in input().split()]
p = 998244353

binomials = binomials_p(N - 1, K, p)
ans = 0
pow = 1 
for j in range(K + 1):
    ans = (ans + binomials[K - j] * pow % p) % p
    pow = pow * (M - 1) % p

ans = ans * M * exp_by_sq_p(M - 1, N - K - 1, p) % p

print(ans)

Solution (Python):
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 998244353
class Combination(object):
	def __init__(self, N, MOD):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1
 
		
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % MOD
			self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
			self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    if N == 1:
        print(M)
        return

    Com = Combination(N-1, MOD)
    ans = 0
    for k in reversed(range(K+1)):
        ans += M * pow(M-1, N-k-1, MOD) * Com.com(N-1, k)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  
        self.ifac = [1, 1]  
        self.inv = [0, 1]  

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


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

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  
        self.ifac = [1, 1]  
        self.inv = [0, 1]  

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


mod = 998244353
comb = combination(mod)
n, m, k = inpl()
if m == 1:
    if k >= n - 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
ans = 0
for i in range(min(n, k + 1)):
    ans += m * pow(m - 1, n - 1 - i, mod) * comb.calc(n - 1, i) % mod
    ans %= mod
print(ans)

Solution (Python):
mod=998244353

class Combination:
	def __init__(self,size):
		self.size = size + 2
		self.fact = [1, 1] + [0] * size
		self.factInv = [1, 1] + [0] * size
		self.inv = [0, 1] + [0] * size
		
		for i in range(2, self.size):
			self.fact[i] = self.fact[i - 1] * i % mod
			self.inv[i] = -self.inv[mod % i] * (mod//i) % mod
			self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod
			
	def npk(self,n,k):
		if n < k or n < 0 or k < 0:
			return 0
		return self.fact[n] * self.factInv[n - k] % mod
		
	def nck(self,n,k):
		if n < k or n < 0 or k < 0:
			return 0
		return self.fact[n] * (self.factInv[k] * self.factInv[n - k] % mod) % mod
		
	def nhk(self,n,k):
		return self.nck(n + k - 1, n - 1)


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

comb=Combination(n+k)
res=0

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

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[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Solution (Python):
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

n, m, k = map(int, input().split())
mod = 998244353
all = pow(n, m, mod)
x, y = [0] * (k + 1), [0] * (k + 1)
x[0] = (m * pow(m - 1, n - k - 1, mod)) % mod
y[0] = 1
for i in range(1, k + 1):
    x[i] = (x[i - 1] * (m - 1)) % mod
    y[i] = (pow(i, mod - 2, mod) * y[i - 1] * (n - i)) % mod
y.reverse()
ans = 0
for i in range(k + 1):
    ans += x[i] * y[i]
    ans %= mod
print(ans)

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

def main():
  N, M, K = map(int, readline().split())
  p = 998244353

  cnt = 0
  c = 1
  for i in range(K+1):
    cnt += c * M * pow(M-1, N-1-i, p)
    cnt %= p
    c *= (N - i - 1) * pow(i+1, p-2, p)
    c %= p
  print(cnt)

if __name__ == '__main__':
  main()

Solution (Python):
def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        if K == N - 1:
            return 1
        else:
            return 0
    if N == 1:
        return M
    mod = 998244353
    fact = [1]
    for i in range(1, N):
        fact.append(fact[-1] * i % mod)
    fact_inv = [pow(fact[-1], mod - 2, mod)]
    for n in range(N - 1, 0, -1):
        fact_inv.append(fact_inv[-1] * n % mod)
    fact_inv = fact_inv[::-1]
    m_1_pow = [1]
    for _ in range(N):
        m_1_pow.append(m_1_pow[-1] * (M - 1) % mod)
    count = 0
    for k in range(K + 1):
        current = ((((m_1_pow[N - k - 1] * M) % mod) * fact[N - 1] % mod) * fact_inv[k] % mod) * fact_inv[N - 1 - k] % mod
        count = (count + current) % mod
    return count


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

Solution (Python):

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

mod = 998244353

ans = 0



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

    


M_pow = [0] * num
M_pow[0] = 1
for i in range(1,num):
    M_pow[i] = (M_pow[i-1] * (m-1)) % mod


for i in range(k+1):
    f = M_pow[n-i-1] * pow(fact[i]*fact[n-i-1], mod-2, mod)
    ans += f % mod

ans *= m * fact[n-1]
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 = 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)

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


ans=0


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

print(ans)

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

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


ans=0

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

print(ans)

Solution (Python):
mod = 998244353

class mod_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 = mod_combination(n)
ans = 0
for x in range(k + 1):
    ans = (ans + C.calc(n - 1, n - x - 1) * m * pow(m - 1, n - x - 1, mod) % mod) % mod
print(ans)

Solution (Python):
import sys
 
input = sys.stdin.readline
 
def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod
 
mod = 998244353
N, M, K = map(int, input().split())
 
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod 

revfact = [1] * (N + 1) 
revfact[N] = pow(fact[N], mod - 2, mod) 

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

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

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

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

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

Solution (Python):
def modpow(a, x, mod):
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2, mod)
    else:
        return (modpow((a * a) % mod, x // 2, mod) * a) % mod


N, M, K = map(int, input().split(' '))
max_K = 3 * 10 ** 5
mod = 998244353

inv = [0 for i in range(max_K + 1)]
inv[0] = 1
inv[1] = 1
for i in range(2, K + 1):
    inv[i] = modpow(i, mod - 2, mod)
choose = [0 for i in range(K + 1)]
choose[0] = 1
for i in range(1, K + 1):
    choose[i] = choose[i - 1] * (((N - i) * inv[i]) % mod)
    choose[i] %= mod

ans = 0
for i in range(N - 1 - K, N):
    ans += modpow((M - 1), i, mod) * choose[N - i - 1]
    ans %= mod
print((ans * M) % mod)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *





































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M,K = inputMap()

	cnv = Combination(N, 998244353)

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

		prn = cnv(N-1, i)

		tmp = (tmp * prn) % 998244353
		ans = (ans + tmp) % 998244353

	print(ans)





def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


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):
        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 dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)



if __name__ == "__main__":
	main()

Solution (Python):
import sys
import itertools
import numpy as np

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

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

comInit(MOD)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, k = map(int, readline().split())

ans = 0
col = m
for x in range(n - 1, -1, -1):
    now = col
    now *= com(n - 1, x, MOD) % MOD
    if x <= k:
        ans += now
    col = (col * (m - 1)) % MOD

print(ans % MOD)

Solution (Python):
import sys

input = sys.stdin.readline

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

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

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

revfact = [1] * (N + 1) 
revfact[N] = pow(fact[N], mod - 2, mod) 

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


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

Solution (Python):
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
if m==1:
    if k==n-1:
        print(m)
    else:
        print(0)
    exit(0)
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans%mod)

Solution (Python):
def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


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

    _mod = 998244353
    _mod2 = 998244351

    
    
    

    comb_ar = create_array(n-1, k, _mod, _mod2)
    _z = (m - 1) ** (n - 1 - k)
    res = m * _z * comb_ar[k]
    res %= _mod

    if k > 0:
        for x in range(1, k + 1):
            _z *= m - 1
            _z %= _mod
            res += m * _z * comb_ar[k - x]
            res %= _mod

    print(res)


main()

Solution (Python):
import math



















def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


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

    _mod = 998244353
    _mod2 = 998244351

    
    
    

    
    comb_ar = create_array(n-1, k, _mod, _mod2)
    _z = (m - 1) ** (n - 1 - k)
    res = m * _z * comb_ar[k]
    res %= _mod

    if k > 0:
        for x in range(1, k + 1):
            _z *= m - 1
            _z %= _mod
            res += m * _z * comb_ar[k - x]
            res %= _mod

    

    print(res)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


main()