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

modulus = 998244353







def inv(x):
    e = 1
    for b in bin(modulus - 2)[2:]:
        e *= e
        if b == '1':
            e *= x
        e %= modulus
    return e

pow = [1]  
for i in range(n):
    pow.append(pow[-1] * (m - 1) % modulus)
choose = [1]  
for i in range(1, n):
    choose.append(choose[-1] * (n-1-i+1) * inv(i) % modulus)

def solve(n, k):
    x = m * pow[n-k-1]
    return x * choose[n-k-1] % modulus

print(sum(solve(n, i) for i in range(k+1)) % modulus)

Solution (Python):
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1
    
    def __call__(self, n):
        '''n! % mod '''
        return self.fact(n)
    
    def fact(self, n):
        '''n! % mod '''
        if n >= self.mod:
            return 0
        self.make(n)
        return self._factorial[n]
    
    def fact_inv(self, n):
        '''n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self.make_inv(n)
        return self._factorial_inv[n]
    
    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self.fact_inv(n-r)*self.fact_inv(r) % self.mod
        return self(n)*t % self.mod
    
    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self.fact_inv(n-1)*self.fact_inv(r) % self.mod
        return self(n+r-1)*t % self.mod
    
    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod
    
    def modinv(self, n):
        ''' n^-1 (mod p)'''
        n %= self.mod
        if n == 0:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        
        return pow(n, self.mod-2, self.mod)
    
    def make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1
    
    def make_inv(self, n):
        if n >= self.mod:
            n = self.mod
        self.make(n)
        if self._size_inv < n+1:
            for i in range(self._size_inv, n+1):
                self._factorial_inv.append(self.modinv(self._factorial[i]))
            self._size_inv = n+1


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

Solution (Python):
mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def color(n,m):
    return m*(pow_k(m-1, n-1))

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            x %= mod
            n = (n - 1) // 2
        else:
            x = x ** 2
            x %= mod
            n = n // 2

    return (K * x)%mod
invs = [0] * (N + 1)
invs[1] = 1
for i in range(2, N + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod
mod_inv_factorials=[1]*(N+1)

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

def mod_factorial(n, m):
    r = 1
    for i in range(1, n+1):
        r *= i
        r %= m
    return r

upper = mod_factorial(N-1,mod)

for i in range(K+1):
    tmp = color(N-i,M)
    ansk = (upper*mod_inv_factorials[i]*mod_inv_factorials[N-1-i]*tmp)%mod
    ans += ansk
    ans %= mod
print(ans)

Solution (Python):



class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

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

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M,K = map(int,input().split())
MOD=998244353

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            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 ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, r)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    N, M, K = map(int, rl().split())
    MOD = 998244353
    
    com = Combination(N + 10, MOD)
    
    ans = 0
    for x in range(K + 1):
        ans = (ans + com.ncr(N - 1, x) * M * pow(M - 1, N - 1 - x, MOD)) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

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

d = [0] * (N+1)
d[0] = M
for i in range(N):
    d[i+1] = d[i] * (M-1) % mod

def createFacArr(n, mod):
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, 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
    return fac, finv

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

fac, finv = createFacArr(N+10, mod)
ans = d[N-1]

for i in range(K):
    ans += d[N-2-i] * comb(N-1, i+1, mod, fac, finv)
    ans %= mod

print(ans)

Solution (Python):
n,m,k = map(int,input().split())
ans = 0
MOD = 998244353
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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


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

Solution (Python):
MOD = 998244353

m = 2*10**5 + 10
fac = [0] * m
finv = [0] * m
inv = [0] * m


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

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

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            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 COMB(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


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in input().split())
    ans = modint(0)
    for i in range(K+1):
        cur = M*pow(M-1, (N-1-i), MOD)*COMB(N-1, i)
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        if K == N-1:
            print(1)
        else:
            print(0)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*pow(fac[y],MOD-2,MOD)*pow(fac[x-y],MOD-2,MOD))%MOD
    
    ans = 0
    base = [1,pow(M-1,N-K-1,MOD)]
    for i in range(K+1):
        base.append((base[-1]*(M-1))%MOD)

    for i in range(K+1):
        ret = comb(N-1,i)*(M*base[-i-2])
        ans += ret
    
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
class Combination():
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fact = self.make_fact(n)
        self.fact_inv = self.make_fact_inv(n)
    def make_fact(self, n):
        res = [1]*(n+1)
        for i in range(1, n+1):
            res[i] = res[i-1]*i%self.mod
        return res
    def make_fact_inv(self, n):
        fact_inv = [1]*(n+1)
        fact_inv[n] = pow(self.fact[n], self.mod-2, self.mod)
        for i in range(n, 0, -1):
            fact_inv[i-1] = fact_inv[i]*i%self.mod
        return fact_inv
    def comb(self, m, k):
        return self.fact[m]*self.fact_inv[k]*self.fact_inv[m-k]%self.mod
    


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


sum_ = 0
comb=Combination(n,lim)
for j in range(k+1):
    ans = m %lim
    
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb.comb(n-1,j)) % lim
    
    sum_ = (sum_+ans) % lim
print(sum_)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True


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

N = 3 * (10 ** 5)  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

n, m, k = MAP()

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

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

mod = 998244353

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

ans = 0
for i in range(n-k-1, n):
    com = fac[n-1] * finv[i] * finv[n-i-1] % mod
    res = m
    e = m - 1
    while i > 0:
        if i & 1:
            res = res * e % mod
        e = e * e % mod
        i >>= 1
    res = res * com % mod
    ans = (ans + res) % mod

print(ans)

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

start=(M*pow(M-1,N-1,P))%P



if N>=2:
    fac=[0]*N
    finv=[0]*N
    inv=[0]*N
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1
    for i in range(2,N):
        fac[i]=(fac[i-1]*i)%P
        inv[i]=P-(inv[P%i]*(P//i))%P
        finv[i]=(finv[i-1]*inv[i])%P

    def comb(n,k):
        return fac[n]*(finv[k]*finv[n-k]%P)%P



    comp=0
    last=(N-1)-K 
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
    comp=(comp*M)%P

    print((start+comp)%P)

else:
    print(M%P)

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

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

def nCk(n,k):
    return fac[n]*per[k]%mod*per[n-k]%mod

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

Solution (Python):
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    if n==1:
        print(m)
    elif m==1:
        if k==n-1:
            print(1)
        else:
            print(0)
    else:
        comb=Combination(n-1)
        for i in range(n-1):
            mPow=(mPow*(m-1))%mod
            modPow.append(mPow)
        for i in range(n-1-k,n):
            ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
        print(ans%mod)
if __name__=="__main__":
    main()

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

def mod_comb(n,k,mod):
    return fact[n]*fact_inv[k]%mod*fact_inv[n-k]%mod

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

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


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


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)

    res = 0
    for k in range(K + 1):
        res += M * pow(M - 1, N - 1 - k, mod) * C(F, N - 1, k) % mod
        res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

MOD = 998244353
n,m,k = MI()

s = [1]
for i in range(2, n):
    s.append(s[-1]*i%MOD)
if m == 1 and k < n-1:
    print(0)
    exit(0)
elif m == 1 and k == n-1:
    print(1)
    exit(0)
elif k == n-1:
    print(pow(m, n, MOD))
    exit(0)
ans = m*pow(m-1, n-1, MOD)%MOD
for i in range(1, k+1):
    tmp = m*pow(m-1, n-1-i, MOD)*s[n-2]*pow(s[n-2-i], MOD-2, MOD)*pow(s[i-1], MOD-2, MOD)
    ans += tmp
    ans %= MOD
print(ans)

Solution (Python):
n,m,k=map(int,open(0).read().split())
p=998244353
'''
c=[1]*(k+1)
for i in range(1,k+1):
  c[i]=c[i-1]*(n-i)//i
  c[i-1]%=mod
'''
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  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-1-i,p)*cmb(n-1,i, p)
  ans%=p
print(ans)

Solution (Python):
MOD = 998244353
lim = 10 ** 5*2+1
fac = [0] * lim
finv = [0] * lim
inv = [0] * lim

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            self.x
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def __ifloordiv__(self, other):
        self.x *= pow(int(other), MOD - 2, MOD)
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)

def COMinit():
    fac[0] = ModInt(1)
    fac[1] = ModInt(1)
    finv[0] = ModInt(1)
    finv[1] = ModInt(1)
    inv[1] = ModInt(1)
    for i in range(2,lim):
        fac[i] = ModInt(fac[i - 1] * i)
        inv[i] = ModInt(MOD - inv[MOD%i] * (MOD // i))
        finv[i] = ModInt(finv[i - 1] * inv[i])

def cmb(n,k) -> ModInt:
    if int(n) < int(k):
        return ModInt(0)
    if int(n) < 0 or int(k) < 0:
        return ModInt(0)
    if fac[0] == 0:
        COMinit()
    tmp = ModInt(finv[int(k)] * finv[int(n - k)])
    tmp *= fac[int(n)]
    return tmp


        
if __name__ == "__main__":
    n,m,k = map(int,input().split())
    n = ModInt(n)
    m = ModInt(m)
    ans = ModInt(0)
    for i in range(k+1):
        ans += cmb(n-1,i) * m * pow(m-1,n-i-1)
    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

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
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 += pow(M-1, N-1-i, mod) * pow(M, 1, mod) * cmb(N-1, i, mod)
    ans %= mod
ans %= mod
print(ans)

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

    def __call__(self, n, r):
        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_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res


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

Solution (Python):
n,m,k=map(int,open(0).read().split())
p=998244353
'''
c=[1]*(k+1)
for i in range(1,k+1):
  c[i]=c[i-1]*(n-i)//i
  c[i-1]%=mod
'''
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  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-1-i,p)*cmb(n-1,i, p)
  ans%=p
print(ans)

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

    def __call__(self, n, r):
        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_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res


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

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

mod = 998244353
N = 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))
  exit()

ans = 0
a= m*pow(m-1,n-1-k-1,mod)

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

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
ans = 0
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 = mod
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)
for i in range(0,k+1):
  ans += m*pow(m-1,n-1-i,mod)*cmb(n-1,i,p)
  ans %= mod
print(ans)

Solution (Python):
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
n,m,k=map(int,input().split())
w=998244353
t=0
c=1
b=m*((m-1)**(n-1))%w
g=power_func(m-1,w-2,w)
for i in range(k+1):
    t += c * b
    t %= w
    if i<k:
        c*=(n-1-i)
        c*=power_func(i+1,w-2,w)
        c%=w
        b*=g
        b%=w
if m==1 and k==n-1:
    print(1)
else:
    print(t)

Solution (Python):

import sys

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

    
    X = max(N,M)+1
    a = [None] * X
    inva = [None] * X
    a[0] = 1

    for i in range(1, X):
        a[i] = i * a[i-1] % p

    inva[X-1] = pow(a[X-1],p-2,p)
    for i in range(X-1):
        inva[X-i-2] = inva[X-i-1] * (X-i-1) % p

    ans = 0
    for i in range(K+1):
        tmp = (a[N-1] * inva[i] % p) * inva[N-1-i] % p
        tmp = tmp * (M * pow(M-1,N-i-1,p) % p) % p 
        ans = (ans + tmp) % p
    print(ans % p)

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

dp = [0]*(N+1)

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

ans = 0

for i in range(0,K+1):
    ans += cmb(N-1,i,mod)*dp[N-i]
    ans %= mod

print(ans)