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):
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * m.i % MOD)
    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)
    def __truediv__(self, m):
        return mint(self.i * (m ** (MOD - 2)).i % MOD)
    def __repr__(self):
        return repr(self.i)

fact_range = 200005
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % MOD

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], MOD - 2, MOD)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % MOD

def comb(n, k):
    if k < 0 or n < k:
        return mint(0)
    else:
        return mint(facts[n] * ifacts[n-k] % MOD * ifacts[k] % MOD)

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



l = [mint(m) * (mint(m-1) ** (n-1-i)) * comb(n-1, n-1-i) for i in range(n)]
ans = mint(0)
for i in range(k+1):
    ans = ans + l[i]
print(ans)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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




def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L ** 0.5 + 1)
    arr = np.resize(arr, Lsq ** 2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n - 1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n - 1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = (10 ** 5) * 2 + 100
fact, fact_inv = make_fact(U, MOD)


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


ans = 0
t = M

if K == (N - 1):
    ans += M

for i in range(1, N):
    kumi = N - i - 1
    t *= M - 1
    t %= MOD
    if K < kumi:
        continue

    c = mod_comb_k(N - 1, i, MOD)
    ans += c * t
    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

D = {}
def inv(a):
    if a in D:
        return D[a]
    
    d = pow(a, mod - 2, mod)
    D[a] = d
    return d


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):
N,M,K = map(int,input().split())
mod = 998244353

if M == 1 and K == N-1:
    print(1)
    exit()

A = [0]*(K+1)
A[0] = (M*pow(M-1,N-1,mod)) % mod

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

ans = A[0]
for i in range(K):
    ans = (ans + A[i+1]) % mod

print(ans)

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
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 = 2
N = 10 ** 6 + 2
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)

'''










n,m,k = list(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 + 2
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)





total = 1
for i in range(n):
    total *= m
    total %= p

powm1 = [1]
now = 1
for i in range(3*10**5):
    now *= m-1
    now %= p
    powm1.append(now)

ans = 0
for i in range(k+1):
    parts = n-i
    alloc = cmb(n-1,parts-1,p)
    col = m * powm1[parts-1] % p
    
    ans += alloc * col % p
    ans %= p

print(ans)

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

DIVIDER = 998244353
bit_pow = []
tmp = DIVIDER - 2
while tmp > 0:
    bit_pow.append(tmp % 2)
    tmp >>= 1
N_pow = len(bit_pow)

def myinv(arg):
    global DIVIDER
    ret = 1
    arg_pow = arg
    for i in range(N_pow):
        if bit_pow[i] > 0:
            
            ret = (ret * arg_pow) % DIVIDER
        arg_pow = (arg_pow * arg_pow) % DIVIDER
    
    
    return ret

def mydiv(a, b):
    b_inv = myinv(b)
    
    ret = (a * b_inv) % DIVIDER
    return ret

tab_comb = [1]
tmp = 1
for i in range(N - 1):
    tmp = (tmp * (N - 1 - i)) % DIVIDER
    tmp = mydiv(tmp, (i + 1))
    tab_comb.append(tmp)


tab_Mpow = [1]
tmp = 1
for i in range(N - 1):
    tmp = (tmp * (M - 1)) % DIVIDER
    tab_Mpow.append(tmp)


ans = 0
for i in range(K + 1):
    ans_tmp = M
    ans_tmp = (ans_tmp * tab_comb[i]) % DIVIDER
    ans_tmp = (ans_tmp * tab_Mpow[N - 1 - i]) % DIVIDER
    
    ans = (ans + ans_tmp) % DIVIDER

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 998244353  

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs_(n, k):
    '''
        make [C(0, k), C(1, k), C(2, k) ..... C(n, k)]
    '''
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    ret = [0] * (n + 1)
    for i in range(k, n + 1):
        a = fact[i]
        b = (fact[k] * fact[i - k]) % MOD
        ret[i] = get_fraction_mod(a, b)
    return ret

def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] 
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        
        
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret

def solve(N: int, M: int, K: int):
    pows = []
    for i in range(N + 1):
        t = pow(M - 1, i, MOD)
        pows.append(t)
    s = pow(M, N, MOD)
    
    coms = make_combs(N - 1, N - 1)
    
    for i in range(K + 1, N):
        c = coms[i]
        ss = M * pows[N - i - 1]
        
        s -= c * ss
        s %= MOD
    print(s)
    return

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

if __name__ == '__main__':
    main()

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

C = [1]
for i in range(N):
    if i == 0:
        C.append(M)
    else:
        C.append((C[i] * (M-1)) % 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 )


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


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

if M == 1:
    if N - 1 <= K:
        print(1)
    else:
        print(0)
elif N == 1:
    print(M)
else:
    print(ans % MOD)

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


if M>1:
    mod = 998244353
    comb = [1]
    c = 1
    for i in range(N-1):
        c *= N-1-i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb.append(c)
    
    M1 = [1]
    m = 1
    for i in range(N):
        m*=M-1
        m%=mod
        M1.append(m)
    
    ans = 0
    
    for i in range(K+1):
        ans += M1[N-1-i]*comb[i]
        ans %= mod
    ans *= M
    ans %= mod
    print(ans)
else:
    if N==K+1:
        print(1)
    else:
        print(0)

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

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

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

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

def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

fac, inv = prepare(n,mod)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

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

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

MOD = 998244353
N = 3 * 10**5

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD


def perm(n, k):
  return fact[n] * rfact[n-k] % MOD


def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

print(ans)

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

Solution (Python):
class PERM_COMB_MOD():
    
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

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

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

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

mod = 998244353

PCM = PERM_COMB_MOD(n+10, mod)

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

print(ans)

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


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

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


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

ans = 0
for i in range(k+1):
    kosu = n - i
    ans = (ans + m*m_1_i[kosu-1] * comb(n-1, kosu-1, mod)) % mod

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f


def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv


def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

N,M,K = LI()

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

fl = fact_all(N)
il = fact_inv_all(fl)

ans = 0
for j in range(K+1):
    ans += nCk(N-1,j,fl,il)*Ma[N-1-j]*M
    ans %= mod

print(ans)

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,k = map(int,input().split())
class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 10**6)


A = pow(m,n,mod) 
count = 0
for i in range(n-k-1,0,-1):
  count += invt.cmb(n-1,i-1) * m * pow(m-1,i-1,mod)
  count %= mod

print((A-count) % mod)

Solution (Python):
from collections import Counter

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

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

ans = 0
for j in range(K + 1):
    ans += (
        pow(M - 1, N - 1 - j, MOD)
        * factorial[N - 1]
        * inv_factorial[j]
        * inv_factorial[N - 1 - j]
        % MOD
    )
    if ans >= MOD:
        ans -= MOD
ans = ans * M % MOD
print(ans)

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

ans = pow(M, N, MOD)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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


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

print(ans)

Solution (Python):
X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - K - 1, -1):
	c = (c * i) % X
	f_cache.append(c)



def C(n, m):











	return (f_cache[m] * inv_f_cache[m]) % X


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

	

print(total)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

N, M, K = MAP()

lim = 2*10**5+10  
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = (fact[n-1] * n) % mod
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = (n * fact_inv[n]) % mod
def C(n, r):
    return (((fact[n] * fact_inv[r]) % mod) * fact_inv[n-r]) % mod

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

print(ans)

Solution (Python):
MOD = 998244353

list_size = 10**5*5   

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if n < r:
        return 0
    if n == 0 or r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD


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

X = [M]
for i in range(N-1):
    X.append((X[-1]*(M-1)) % MOD)

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

print(ans)

Solution (Python):
MOD = 998244353


def pow(a, b):
	if b == 0:
		return 1

	if (b % 2) == 0:
		x = pow(a, b // 2) % MOD
		return x * x % MOD
	else: 
		return a * pow(a, b - 1) % MOD

def inverse(x):
	return pow(x, MOD - 2)

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

result = 0

bin_coeff = 1

for k in range(K + 1):
	incr = (((bin_coeff * m % MOD)) % MOD) * pow(m - 1, n - k - 1) % MOD
	
	result = (result + incr)  % MOD
	bin_coeff = ((bin_coeff * (n - k - 1) % MOD) * inverse(k + 1)) % MOD

print(result)

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

N = n + 5
bikkuri = [0 for i in range(N)]
bikkuri[0] = 1
gyaku = [0 for i in range(N)]
gyaku[0] = 1
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
    gyaku[i] = pow(bikkuri[i], mod - 2, mod)


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    if r == 0 or n - r == 0:
        return 1
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0

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

Solution (Python):
nn = 200200
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
    exit()
ans = 0
t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
for i in range(K+1):
    ans = (ans + t * C(N-1, i)) % P
    t = t * m % P
print(ans * M % P)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


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



def main():
    N, M, K = [int(x) for x in input().split()]

    MOD = 998244353

    global fact, factinv, inv
    for i in range(2, 10 ** 6 + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)


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

    print(ans % MOD)


if __name__ == '__main__':
    main()

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

def make_table(n, mod = MOD):
    
    g1 = [0] * (n + 1)
    g1[0] = 1
    g1[1] = 1

    
    g2 = [0] * (n + 1)
    g2[0] = 1
    g2[1] = 1

    
    inverse = [0] * (n + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)

g1, g2, inverse = make_table(N)

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

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

print(ans)

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 998244353
INF = 10 ** 18
SIZE = 10 ** 6

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 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
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

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

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

MAX = 2 * 10 ** 5 + 10

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


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

print(ans)

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

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

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

def chng2(n): 
    ans = list(bin(n))
    return ans

def pwr(n,k): 
    memo = chng2(k)
    lng = len(memo)

    li = [0 for i in range(lng-1)]
    li[0] = 1
    
    a = n
    ans = 1
    for i in range(1,lng-1):
        li[i] = a%p
        a *= a
        a %= p
 
    for i in range(1,lng-1):
        if memo[-i]=='1':
            ans *= li[i]
            ans %= p

    return ans



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

ans = 0
for k in range(K+1):
    memo1 = cmb(N-1,k,p)
    memo2 = pwr(M-1,N-k-1)*M
    ans += memo1*memo2
    ans %= p
    

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
INF=998244353
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
if m==1:
    if k==n-1:
        print(m)
    else:
        print(0)
    sys.exit()
for i in range(k+1):
    if i==0:
        c=1
        temp=(m*pow(m-1,n-1))%INF
    else:
        x=modinv(i,INF)
        c=(c*x*(n-i))%INF
        temp=(temp*modinv(m-1,INF))%INF
    ans=(ans+c*temp)%INF
print(ans)

Solution (Python):

p=998244353
N,M,K=map(int,input().split())
power=[0 for i in range(N)]
power[0]=1
for i in range(1,N):
    power[i]=(power[i-1]*(M-1))%p
ans=M*power[N-1]
ans%=p
pre_compute=[0 for i in range(K+1)]
num = den = 1
for i in range(1,K+1):
    num*=(N-i)
    den*=i
    num%=p
    den%=p
    pre_compute[i]=(num * pow(den, p - 2, p)) % p 
for i in range(1,K+1):
    ans+=M*power[N-1-i]*pre_compute[i]
    ans%=p
print(ans)

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

memo = [0]*n


def com(n, r):
    if n < r or r < 0:
        return 0
    if n-r < r:
        r = n-r
    if r == 0:
        memo[r] = 1
        return memo[r]
    if memo[r] != 0:
        return memo[r]
    X = Y = 1
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
        memo[i] = X*pow(Y, MOD-2, MOD)
    return memo[r]


com(n-1, n//2)

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

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

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

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

Solution (Python):
def solve():
    N, M, K = map(int, input().split())
    mod = 998244353
    dp = [1]*(K+1)
    for i in range(1,K+1):
        dp[i] = dp[i-1]*(N-i)*pow(i,mod-2,mod)%mod
    ans = 0
    for i in range(K+1):
        ans += dp[i]*M*pow(M-1,N-1-i,mod)
        ans %= mod
    return ans
print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,m,k = map(int, input().split())
mod = 998244353
ans = 0

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