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):
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def multi_choose(self, n, r):
        """重複組み合わせ nHr """
        return self.combination(n - 1 + r, r)

    def factorial(self, n):
        return self.fact[n]


def main():
    MOD = 998244353

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

    mp = [1]
    t = 1
    for _ in range(N):
        t = t * (M - 1) % MOD
        mp.append(t)

    calc = Calc(max_value=N, mod=MOD)

    ans = mp[N - 1]
    for i in range(1, K + 1):
        ans = (ans + mp[N - 1 - i] * calc.combination(N - 1, i)) % MOD
    ans = ans * M % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353

def cmb(k):
    if k < 0 or k > N-1: return 0
    return factN * fact_inv[k] % MOD * fact_inv[N-1-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.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 ** 6  
fact, fact_inv = make_fact(U, MOD)


N, M, K = lr()
factN = fact[N-1]
answer = 0
for i in range(K+1):
    answer += cmb(i) * pow((M-1), N-1-i, MOD) % MOD
    answer %= MOD

print(answer * M % MOD)

Solution (Python):
max_n=2 * 10**5
mod=998244353
fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
fact[0] = 1
for i in range(max_n):
    fact[i + 1] = fact[i] * (i + 1) % mod

inv_fact[-1] = pow(fact[-1], mod - 2, mod)
for i in reversed(range(max_n)):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

def nCr_mod(n, r):
    res = 1
    while n or r:
        a, b = n % mod, r % mod
        if a < b:
            return 0
        res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
        n //= mod
        r //= mod
    return res
n,m,k = map(int,input().split())


mm1 = [1]

for i in range(1, n+1):
    mm1 += [(mm1[-1] * (m-1)) % mod]

mm = [1]
for i in range(1, n+1):
    mm += [(mm[-1] * (m)) % mod]

ans = 0
for i in range(k+1):
    if i == 0:
        ans += (mm1[n-1] * m ) % mod
        continue
    if i == n-1:
        ans += (m)
        break
    ans += (mm1[n-1-i] * nCr_mod(n-1,i) * m) % mod

ans = (ans)%mod
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    def comb(n,k):
        return f[n]*inv[k]*inv[n-k]%mod
    n,m,k = LI()
    if k == 0:
        print(m*pow(m-1,n-1,mod)%mod)
    else:
        f = [1]
        N = 10**6
        for i in range(1,N+1):
            f.append(f[-1]*i%mod)
        inv = [None]*(N+1)
        inv[N] = pow(f[N],mod-2,mod)
        for i in range(N)[::-1]:
            inv[i] = inv[i+1]*(i+1)%mod
        s = m
        dk = m
        p = m-1
        for i in range(n-1):
            s *= m
            s %= mod
            if i >= k:
                s -= dk
                s %= mod
                dk *= m-1
                dk += comb(i,k-1)*m*p%mod
                dk %= mod
                p *= m-1
                p %= mod
        print(s)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

mod=998244353


def do():
    
    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
    
    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=INTM()
    
    ans=0
    
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n  ):
        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):
        temp=m
        temp=m*power_func(m-1,n-1-i,mod)%mod
        temp=temp*cmb(n-1,i,mod)%mod
        
        ans+=temp
        ans=ans%mod
    print(ans)
    
if __name__ == '__main__':
    do()

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

def modconb(n,k,mod):
    
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+1):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] %mod
    
    if n<k: return 0
    if n<0 or k<0: return 0
    
    modcombs = [1]
    for k in range(1,n+1):
        modcombs.append(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    return modcombs

if n == 1:
    print(m)
    exit()

mods = modconb(n-1,n-1,mod)
cnt = 0
for i in range(k+1):
    cnt += m*mods[i]*pow(m-1,n-i-1,mod)
    cnt %= mod
print(cnt)

Solution (Python):


n, m, k = [0] * 3
mod = 998244353

def format_input(filename = None):
	global n, m, k
	if filename == None:
		n, m, k = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 2 * 10**5)
		m = rng(1, 2 * 10**5)
		k = rng(0, n - 1)
		print(n, m, k)

inv_mod = [0, 1]
fact_mod = [1, 1]
inv_fact_mod = [1, 1]
def init_fact_table(n):
	global inv_mod, fact_mod, inv_fact_mod
	for i in range(1, n):
		inv_mod.append((-inv_mod[mod % (i + 1)] * (mod // (i + 1))) % mod)
		fact_mod.append((fact_mod[-1] * (i + 1)) % mod)
		inv_fact_mod.append((inv_fact_mod[-1] * inv_mod[-1]) % mod)

def combin_mod(n, r):
	return (fact_mod[n] * inv_fact_mod[r] * inv_fact_mod[n-r]) % mod

def get_answer():
	init_fact_table(n-1)
	answer = 0
	for i in range(k+1):
		answer += ((m % mod) * pow(m-1, n-i-1, mod)) * combin_mod(n-1, i)
		answer %= mod
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Solution (Python):

import sys

MOD = 998244353  


def solve(N: int, M: int, K: int):

    ncomb = [0]*N

    ans = 1
    ncomb[0] = 1
    for i in range(1, N):
        ans *= (N- i) * pow(i,MOD-2,MOD)
        ans %= MOD
        ncomb[i] = ans
    
    answer = 0
    for i in range(K+1):
        answer += M*pow(M-1,N-1-i,MOD)*ncomb[i]
        answer %= MOD
    
    print(answer)
    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):

mod = 998244353
fact = [1]
fact_inv = [1]
for i in range(2*10**5+2):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
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())
ans = 0
for i in range(K+1):
    X = mod_comb_k(N-1,i,mod)
    Z = power_func(M-1,N-(i+1),mod)
    
    ans += X * M * Z % mod
ans %= mod
print(ans)

Solution (Python):
import math


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 power_func(a, n, p=998244353):
    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
comb = Combination(n)

ans = 0
if n-1 == k:
    ans += m

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

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

mod = 998244353
ans = m * pow(m-1, n-1, mod)
ans %= mod
ncm = 1
ncm_list = [0 for _ in range(k)]
for i in range(k):
    ncm *= n-1-i
    ncm *= pow(i+1, mod-2, mod)
    ncm %= mod
    ncm_list[i] = ncm

powm_list = [0 for _ in range(k)]
tmp = m * pow(m-1, n-k-1, mod)
if k != 0:
    powm_list[k-1] = tmp
    for i in range(k-2, -1, -1):
        tmp *= (m-1)
        tmp %= mod
        powm_list[i] = tmp

for i in range(k):
    ans += ncm_list[i] * powm_list[i]
    ans %= mod

print(ans)

Solution (Python):
def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

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


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, inv_t[b], mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

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

P = mod
N = max([max([n, m]), k]) + 5
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

powers = [0] * n
a = m
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
comb = 1
kk = 0
a = n - kk
c += powers[a - 1] * comb

for kk in range(1, k + 1):
    a = n - kk
    comb = (div(comb,  kk, mod) * (a))%mod
    c = c + powers[a - 1] * comb
    c = c%mod
print(c)

Solution (Python):

def pow_mod(a, b, m):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = pow_mod(a, b//2, m)
        return (d * d) % m
    else:
        return (a * pow_mod(a,b-1,m))%m

def comb(n, c, m):
    upe = 1
    dow = 1
    for i in range(1,c+1):
        upe = upe * n % m
        dow = dow * i % m
        n -= 1
    return upe * pow_mod(dow, m-2,m)%m

def modinv(a, m):
    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
    u %= m
    if u < 0:
        u += m
    return u

MOD = 998244353
def solve(N, M, K):
    MOD = 998244353
    U = N-1-K
    color = M * pow_mod(M-1, U, MOD) % MOD
    c = comb(N-1, U, MOD) % MOD
    
    answer = (c * color) % MOD
    
    
    for j in range(N-K, N):
        c = ((c * (N-j)%MOD) * modinv(j, MOD)) % MOD
        
        color = (color * (M-1)) % MOD
        a = (c * color) % MOD
        answer += a
    return answer % MOD
N, M, K = map(int, input().split())
print(solve(N, M, K))

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

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

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
ans=0

mo=998244353

n,m,k=LI()
cm=Comb(n+100,mo)


ans=0
N=n-1

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

Solution (Python):
def main():
    mod = 998244353
    fact = [1, 1]
    for i in range(2, 400001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % 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)*nCr(n-1, n-i-1)) % mod

    print(ans)


main()

Solution (Python):
import sys

input = sys.stdin.readline

P = 998244353


def make_fac_tables_mod_p(n, p):
    fac = [0] * (n + 1)
    fac_inv = [0] * (n + 1)
    mod_inv = [0] * (n + 1)
    fac[0] = fac[1] = 1
    fac_inv[0] = fac_inv[1] = 1
    mod_inv[1] = 1
    for i in range(2, n + 1):
        fac[i] = (fac[i - 1] * i) % p
        mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
        fac_inv[i] = fac_inv[i - 1] * mod_inv[i] % p
    return fac, fac_inv


def nCk_mod_p(fac, fac_inv, n, k, p):
    return ((fac[n] * fac_inv[n - k]) % p) * fac_inv[k] % p


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

    fac, fac_inv = make_fac_tables_mod_p(N, P)

    ans = M * pow(M - 1, N - 1, mod=P) % P  
    for k in range(1, K + 1):
        num = M * pow(M - 1, N - 1 - k, mod=P) % P
        num = num * nCk_mod_p(fac, fac_inv, N - 1, k, P) % P
        ans = (ans + num) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 998244353


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

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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


def main():
    N, M, K = map(int, input().split())
    comb = Combination(n_max=N, mod=MOD)
    ans = 0

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(1000000)
N,M,K=map(int,input().split())
MOD=998244353

MAX_N=N+10


def modPow(a,n,p):
    if n==0:
        return 1
    if n == 1:
        
        return a % p

    elif n % 2 == 1:
        
        return a * modPow(a,n-1,p) % p

    else:
        
        t = modPow(a,n//2,p)
        return t * t % p

fac=[None for i in range(MAX_N)]
finv=[None for i in range(MAX_N)]
inv=[None for i in range(MAX_N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        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
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX_N)

ans=0

for i in range(K+1):
    v=COM(N-1,N-1-K+i)%MOD
    v*=M
    v=v%MOD
    v*=modPow(M-1,N-1-K+i,MOD)
    v=v%MOD
    ans+=v
    ans=ans%MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]





def table(n:int, p=998244353):
    global fact, factinv, inv
    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:int, r:int, p=998244353):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

N, M, K = mi()

table(2*10**5 + 1)
ans = 0
for i in range(K+1):
    
    ans = (ans + cmb(N-1, i) * M * pow(M-1, N-i-1, 998244353)) %998244353

print(ans)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

p = 998244353


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


def pow_k(x, n, p):
    if n == 0:
        return 1

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

    return K * x % p


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):
    po = pow_k(M-1, N-i-1, p)
    tmp = po * M % p
    tmp = tmp * cmb(N-1, i, p) % p
    ans = (ans + tmp) % p

print(ans)

Solution (Python):
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict



sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


def nCr_factory(limit, mod):
    """ return a combinatorial number operator with upper bound """

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

    ifact = [1] * (limit + 1)
    ifact[-1] = pow(fact[-1], mod-2, mod)

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

    def calc(n, i):
        """ combinatorial number with modulo """
        if i < 0 or i > n:
            return 0
        return fact[n] * ifact[i] % mod * ifact[n-i] % mod
    return calc



MOD = 998244353

nCr = nCr_factory(2*10**5, MOD)

N, M, K = read_n_item()
dp = [0] * (N+1)
dp[0], dp[1] = 1, M

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

ans = 0
for i in range(K+1):
    remain = N - i
    ans += dp[remain] * nCr(N-1, i)
    ans %= MOD
print(ans)

Solution (Python):
mod = 998244353


class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    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.m)%self.m

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

bicoeff = BiCoeff(10**6, mod)

res = 0
for ki in range(k+1):
    r = bicoeff.calc(n-1, ki)
    if ki==0:
        r = 1
    x = n - ki
    
    res += r * m * pow(m-1, x-1, mod)
    res %= mod
print(res)

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

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

ans = 0

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

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

mm1 = []
div = [0]
conv = [1]
p = 1
d = 1
for i in range(n):
  mm1.append(p)
  p = (p*(m-1))%mod
  div.append(pow(i+1,mod-2, mod))
  conv.append((conv[-1] * (n-i-1) * div[-1])%mod)
  
ans = 0
for i in range(k+1):
  a = m * mm1[n-i-1] * conv[i]
  ans += a%mod
  ans %= mod
print(ans)

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

mod = 998244353

fac = [1, 1]
ifac = [1, 1]
inverse = [0, 1]

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

ans = 0
for i in range(n-k-1, n):
    j = min(i, n-i-1)
    com = fac[n-1] * ifac[j] * ifac[n-j-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)