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 bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


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

N = 10**5*2+100
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(k):
    tmp=cmb(n-1,i+1)*m*pow(m-1,n-(i+2),mod)
    
    
    tmp%=mod
    ans+=tmp
    ans%=mod
    
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

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


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

Solution (Python):
MOD = 998244353
def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    fu = FactorialUtils(N)
    ans = Mint()
    for i in range(K + 1):
        tmp = Mint(1)
        tmp *= fu.choose(N - 1, i)
        tmp *= M
        tmp *= pow(M - 1, N - 1 - i, MOD)
        ans += tmp
    print(ans)

class FactorialUtils:
    def __init__(self, n, mod=MOD):
        self.__mod = mod
        self.fac = [1] * (n + 1)
        self.ifac = [1] * (n + 1)
        for i in range(2, n + 1): self.fac[i] = self.fac[i - 1] * i % mod
        self.ifac[n] = pow(self.fac[n], mod - 2, mod)
        for i in range(n, 1, -1): self.ifac[i - 1] = self.ifac[i] * i % mod

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n - r] % self.__mod) * self.ifac[r] % self.__mod

    def multichoose(self, u, k):
        return (self.fac[u + k - 1] * self.ifac[u - 1] % self.__mod) * self.ifac[k] % self.__mod

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()

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

fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)

def combination(n,fact,ifact):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%MOD
        inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
        ifact[i] = (ifact[i-1]*inv[i])%MOD
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%MOD
combination(N,fact,ifact)

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

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
ans = 0
now = m
c = 1
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,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
for i in range(n):
    if n-i-1 <= k:
        ans += now*c
        ans %= mod
    now *= (m-1)
    now %= mod
    c = c*(n-1-i)%mod
    c = c*mod_inv(i+1,mod)%mod
print(ans%mod)

Solution (Python):
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

        self.fac[0], self.fac[1] = 1, 1
        self.finv[0], self.finv[1] = 1, 1
        self.inv[1] = 1

        for i in range(2, max_num):
            self.fac[i] = self.fac[i-1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

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


def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


n, m, k = map(int, input().split())
com = Combination(998244353, 510000)
all_ptn = modpow(m, n, 998244353)
exct_ptn = 0

for i in range(k+1, n):
    cnt = com.calc(n-1, i) * m * modpow(m - 1, n - 1 - i, 998244353)
    exct_ptn += cnt
    exct_ptn %= 998244353

ret = all_ptn - exct_ptn
if ret < 0:
    ret += 998244353

print(ret)

Solution (Python):
F = 2*10**5+5
mod = 998244353
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

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

ans=0

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

Solution (Python):
import sys
mod = 998244353
sys.setrecursionlimit(pow(10, 8))

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-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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]

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 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())
r = 0
for i in range(K+1):
    r += (cmb(N-1, i) * M * pow(M-1, N-i-1, mod)) % mod
    r %= mod
print(r)

Solution (Python):
N,M,K=map(int,input().split())
m=998244353
max_n=4*10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
a=0
for i in range(K+1):
    a=(a+M*pow(M-1,N-1-i,m)*comb(N-1,N-i-1))%m
print(a)

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

num = 200010
fact = [1] * (num+1)
ifact = [1] * (num+1)
inv = [pow(i,MOD-2,MOD) for i in range(num+1)]
for i in range(1,num+1):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = (ifact[i-1] * inv[i]) % MOD

def nCr(n,r):
    return (fact[n] * ifact[r] * ifact[n-r]) % MOD

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

Solution (Python):
N, M, K = map(int, input().split())
MOD = 998244353
n = N
fac = [1]
caf = [1]


def pow(n, p):
    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


for i in range(1, n):
    fac.append((fac[i - 1] * i) % MOD)
    caf.append(pow(fac[i], MOD - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return fac[n] * caf[r] * caf[n - r]


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

Solution (Python):
N, M, K = map(int, input().split())
MOD = 998244353
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)

comb = [M] * (K + 1)
for i in range(1, K + 1):
    comb[i] = comb[i - 1] * (N - i) % MOD
    comb[i] = comb[i] * modinv(i) % MOD

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

Solution (Python):
from collections import defaultdict
mod = 998244353
def factrial(N):
    fc = [1, 1] + [None] * N
    inv = [0, 1] + [None] * N
    fcInv = [1, 1] + [None] * N
    for i in range(2, N+1):
        fc[i] = i*fc[i-1]%mod
        inv[i] = mod-(inv[mod%i]*(mod//i))%mod
        fcInv[i] = fcInv[i-1]*inv[i]%mod
    return fc, fcInv

def modCom(n, k):
    return 0 if n < k else fc[n] * fcInv[k] * fcInv[n-k] % mod

N, M, K = map(int, input().split())
fc, fcInv = factrial(N+1)
ans, C = 0, 0
for k in range(K+1):
    C = modCom(N-1, k)
    C %= mod
    ans += C * M * pow(M-1, N-k-1, mod)
    
    ans %= mod
print(ans)

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

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

facts_1 = [pow(facts[i], MODULO-2, MODULO) for i in range(n+1)]

def C(n, k):
	if k > n:
		print("C is 0")
		return 0
	else:
		to_ret = (facts[n] * facts_1[k] * facts_1[n-k]) % MODULO
			
		return to_ret

pow_m1 = [pow(m-1, n-i-1,  MODULO) for i in range(0, k+1)]

ans = 0
for pair in range(0, k+1):
	
	choose_pairs = C(n-1, pair)
	

	color_blocks = m
	color_blocks *= pow_m1[pair]
	color_blocks %= MODULO
	
	ans += (choose_pairs * color_blocks) % MODULO
	ans %= MODULO
	
print(ans)

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


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res

def main():
    n,m,k = inpm()
    if k == 0:
        print((m*pow(m-1,n-1,mod))%mod)
        return
    if m == 1:
        if n-1 > k:
            print(0)
            return
        print(1)
        return

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

if __name__ == "__main__":
    main()

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

mod = 998244353

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

factorial = [1]
for i in range(1, n):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * n
inverseFactorial[n - 1] = power(factorial[n - 1], mod - 2)
for i in range(n - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod



tmp = [m]

for i in range(n):
    t = tmp[-1] * (m - 1) % mod
    tmp.append(t)


ans = 0

for kk in range(k + 1):
    c = comb(n - 1, kk)
    c *= tmp[n - kk - 1]
    ans += c
    ans %= mod

print(ans)

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

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

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

ans = 0
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
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

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

cb = Comb(200005)

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

for i in range(k+1):
    ad = mint(m)
    ad *= pow(m-1,n-1-i,MOD)
    ad *=  cb.calc(n-1,i)
    ans += ad

print(ans)

Solution (Python):
class ModCombination:
    def __init__(self,n,m=10**9+7):
        self.num = n
        self.mod = m
        self.f = self.factorials()
        self.g = self.inverse()

    def factorials(self):
        
        f = [1, 1]
        for i in range(2, self.num + 1):
            f.append(f[-1] * i % self.mod)
        return f

    def inverse(self):
        
        g = [1]
        for i in range(self.num):
            g.append(pow(self.f[i + 1], self.mod - 2, self.mod))
        return g

    def combination(self, n, r):
        
        nCr = self.f[n] * self.g[n - r] * self.g[r]
        nCr %= self.mod
        return nCr

    def permutation(self, n, r):
        
        nPr = self.f[n] * self.g[n - r]
        nPr %= self.mod
        return nPr

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

a = ModCombination(n,mod)

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

print(ans%mod)

Solution (Python):
MOD = 998244353

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

combination_N_1_ = [1]
for k in range(1, K+1):
    tmp = combination_N_1_[-1] * (N-k) * pow(k, MOD-2, MOD)
    tmp %= MOD
    combination_N_1_.append(tmp)

counter = 0
for i in range(K+1):
    counter += pow(M-1, N-i-1, MOD) * M * combination_N_1_[i]
    counter %= MOD

print(counter)

Solution (Python):
def solve():
    MOD = 998244353

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

    
    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs
    invs = getInvs(N+3, MOD)

    nums = []
    num = M
    for x in reversed(range(1, N)):
        nums.append(num)
        num *= x*(M-1)
        num *= invs[N-x]
        num %= MOD
    nums.append(num)
    nums.reverse()
    

    ans = sum(nums[:K+1])
    ans %= MOD
    print(ans)

solve()

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

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

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


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

Solution (Python):
MOD = 998244353
MOD_t_MAX = 2 * (10**5) + 100
fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_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 MOD_COM(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
def main():
    n, m, k = map(int, input().split())
    MOD_COM_init()
    lim = n-1-k

    ans = 0
    for i in range(lim, n):
        x = m * pow(m-1, i, MOD)
        y = MOD_COM(n-1, i)
        z = x*y % MOD
        ans += z
        ans %= MOD

    print(ans % MOD)

if __name__ == "__main__":
    main()

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

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

if K==N-1:
    print(pow(M,N,mod))
else:
    S={i:0 for i in range(K+1,N+1)}
    S[K+1]=pow(M,K+1,mod)
    for i in range(K+2,N+1):
        S[i]=M*S[i-1]-M*pow(M-1,i-2-K,mod)*cmb(i-2,K,mod)
        S[i]%=mod
    print(S[N])

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

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

max_len = n+10  
mod = 998244353


def modinv(x):
    '''
    xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
    Python標準のpowは割った余りを出すことも可能。
    '''
    return pow(x, mod-2, mod)





modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1
for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod


def binomial_coefficients2(n, k):
    '''
    (n * (n-1) * ... * (n-k+1)) / (1 * 2 * ... * k)
    '''
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans


mod = 998244353

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

print(ans)

Solution (Python):
Q = 998244353
def main():
    N, M, K = map( int, input().split())
    ans = 0
    cmb = 1
    for k in range(K+1):
        ans += M*pow(M-1,N-1-k,Q)%Q*cmb%Q
        ans %= Q
        cmb *= (N-k-1)*pow(k+1,Q-2,Q)%Q
        cmb %= Q
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.fct[m]

    def invf(self, m):
        return self.inv[m]

    def perm(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[m - k] % self.mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

    def hcmb(self, m, k):
        if m + k == 0: return 1
        return self.comb(m + k - 1, k)

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

F = Factorial(max(N, M) + 1, MOD)

res = pow(M, N, MOD)

for i in range(N - 1 - K):
    res -= F.comb(N - 1, i) * M * pow(M - 1, i, MOD)
    res %= MOD

print(res)

Solution (Python):
def main():

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

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

    v = 1
    base = [1, M]
    for i in range(N):
        base.append(base[-1] * (M-1) % mod)

    

    ans = 0
    for j in range(K+1):
        v = base[N-j]
        u = combi(N-1, j)
        ans += (v * u) % mod
        ans %= mod
    return ans


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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

md = 998244353

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,m,k=MI()
    ans=mint(0)
    for i in range(k+1):
        ans+=m*pow(m-1,n-1-i,md)*nCr(n-1,i)
    print(ans)

main()

Solution (Python):
N,M,K = map(int,input().split())
MOD = 998244353
MAX = 2*(10**5) + 1

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

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

def pow(n, k):
	ans = 1
	while k > 0:
		if k % 2 == 1:
			ans = ans * n % MOD
		n = n * n % MOD
		k = k // 2
	return ans

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

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

def comb_list(n, r, mod):
    ret = [1]
    for i in range(1, r+1):
        ret.append(ret[-1] * (n+1-i) * pow(i, mod-2, mod) % mod)
    return ret

ans = 0

mod = 998244353

c_list = comb_list(N-1,K,mod)

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

Solution (Python):
mod = 998244353

SIZE = 2 * 10 ** 5 + 1
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod

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


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

ans = 0
for x in range(k+1):
    pattern = nCr(n-1, x) * m * pow(m-1, n-x-1, mod) % mod
    ans = (ans + pattern) % 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

n,m,k=map(int,input().split())
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):
  x=n-i
  ct=pow(m-1,x-1,mod)
  ct*=m
  ct*=cmb(n-1,i,mod)
  ct%=mod
  ans+=ct
  ans%=mod
print(ans)