Problem:
 Score : 500 points    Problem Statement There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:   For each block, use one of the M colors, Color 1 through Color M , to paint it. It is not mandatory to use all the colors.  There may be at most K pairs of adjacent blocks that are painted in the same color.   Since the count may be enormous, print it modulo 998244353 .      Constraints  All values in input are integers.  1 \leq N, M \leq 2 \times 10^5  0 \leq K \leq N - 1         Input Input is given from Standard Input in the following format:  N  M  K       Output Print the answer.        Sample Input 1 3 2 1      Sample Output 1 6  The following ways to paint the blocks satisfy the conditions: 112 , 121 , 122 , 211 , 212 , and 221 . Here, digits represent the colors of the blocks.       Sample Input 2 100 100 0      Sample Output 2 73074801       Sample Input 3 60522 114575 7559      Sample Output 3 479519525

Solution (Python):

import os
import sys
from io import BytesIO, IOBase





def main():
    mod=998244353

    def po(a,n):
        ans=1
        while n:
            if n&1:
                ans=(ans*a)%mod
            a=(a*a)%mod
            n//=2
        return ans


    n,m,k=[int(x) for x in input().split()]
    
    f=[1]
    for i in range(1,n+5):
        f.append(f[-1]*i%mod)

    def fac(n):
        if n<0:
            return 0
        return f[n]
    
    def nCr(n,r):
        if n<0 or r>n or r<0:
            return 0
        return fac(n)*po(fac(r)*fac(n-r),mod-2)%mod

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



BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

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

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

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


    return  0

if __name__ == "__main__":
    solve()

Solution (Python):
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    mod = 998244353
    comb = Combination(N + 10, mod)

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

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

mod = 998244353 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

N,M,K = map(int,input().split())
MOD = 998244353
ans = 1
for i in range(K+1):
  m = M
  m *= cmb(N-1,i,mod)
  m *= pow(M-1,N-1-i,mod)
  ans += m
  ans %= mod
print(ans-1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



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

N = 2*10**5 

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

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M 
    g2[i] = (g2[i-1] * inverse[i]) % M
    
def sub(x):
    return m * pow(m-1, x-1, M)

s = 0
for i in range(k+1):
    if k>0:
        tmp = cmb(n-1, i, M) * sub(n-i)
    else:
        tmp = sub(n)
    s += tmp
    s %= M

print(s)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 998244353
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N,M,K = inputIL()

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

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

MOD = 998244353

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD


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):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 510000

fac  = [0]*MAX
finv = [0]*MAX
inv  = [0]*MAX

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

def mod_com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

cominit()


res = 0

n,m,k=l_in()

for j in range(k+1):
    tmp = m
    tmp = mod_mul(tmp, mod_pow(m-1,n-1-j))
    tmp = mod_mul(tmp, mod_com(n-1,j))
    res = mod_add(res, tmp)

print(res)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 998244353

MAX_N = 2 * 10**5 + 10

fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

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

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

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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1],mod)

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

def comb(x,y):
    if x < 0 or y < 0 or x < y:
        return 0
    else:
        return fact[x] * ifact[y] * ifact[x-y] % mod


ans = 0

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

print(ans)

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

def pow_mod(x, y):
    res = 1
    while y > 0:
        if y % 2:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y //= 2
    return res

def inverse(x):
    return pow_mod(x, mod-2)

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

for i in range(K+1):
    ans += pow_mod(M-1, N-1-i) * kai[N-1] * inverse(kai[i]) * inverse(kai[N-1-i]) % mod
    ans %= mod

ans *= M
ans %= mod
print(ans)

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



max = 3 * 10**5
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)


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


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

ans %= mod
print(ans)

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

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

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

Solution (Python):
n,m,k=map(int,input().split())
mod=998244353
N=n
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod
ans=pow(m,n,mod)
for i in range(k+1,n):
    ans-=comb(n-1,i)*m*pow(m-1,n-i-1,mod)%mod
    ans%=mod
print(ans)

Solution (Python):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

ans = 0

P = [M] * (N)

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

com = comb(N, MOD)
for i in range(K + 1):
  t = P[-1 -i] * com.com(N - 1, i) % MOD
  ans = (ans + t) % MOD

print(ans)

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

mod = 998244353

l = 3*10**5 + 3

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

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



MI = [0] * (l-1) +[inv(M[l-1], mod)]  
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  
    if y < 0 or y > x:
        return 0
    elif x > l:  
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return (ans * MI[y]) % mod
    else:  
        ans = M[x]
        ans = (ans * MI[y]) % mod
        return (ans * MI[x-y]) % mod

MM1 = [1, mm-1]
for i in range(l):
    MM1.append((MM1[-1] * (mm-1)) % mod)


ans = 0
for i in range(k+1):
    
    ans = (ans + (mm * MM1[n-i-1] * C(n-1, i))) % mod
    

print(ans%mod)

Solution (Python):
n, m, k = [int(i) for i in input().split()]
mod = 998244353
kkai = [1]
for i in range(1, n + 10):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


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

Solution (Python):
MOD = 998244353
max = (10**5)*2 + 1
facts = [1 for i in range(max)]
invs = [1 for i in range(max)]

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

for i in range(1,max):
    facts[i] = facts[i-1]*i%MOD
    invs[i] = inv(facts[i])

def comb(n,r):
    return facts[n]*invs[r] * invs[n-r] % MOD

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

Solution (Python):
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n_ = 3 * 10**5
mod = 998244353
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod


def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

n, m, k = nm()
ans = 0
tbl = [1]*(n+1)
for i in range(n):
    tbl[i+1] = tbl[i] * (m - 1) % mod
for x in range(k+1):
    cnt = nCr(n-1, x) * m * tbl[n - x - 1] % mod
    ans = (ans + cnt) % mod
print(ans)

Solution (Python):
MOD = 998244353
fac = [1] * (3 * 10 ** 5)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def comb(n, k):
    return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD


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

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
l = 10**6
fac = [1]*l
facr = [1]*l

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

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

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

Solution (Python):


def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod


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

mod = 998244353
fac,inv = modfac(3*(10**5),mod)

ans = 0

for i in range(K+1):

    now = modnCr(N-1,i,mod,fac,inv)
    ans += M * now * pow(M-1,N-i-1,mod)
    ans %= mod

print (ans)

Solution (Python):

mod = 998244353
def cmb(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

NN = 10**6 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

N, M, K = map(int, input().split())
ans = 0
for l in range(K+1):
    ans = (ans + cmb(N-1, l)*M*pow(M-1, N-l-1, mod)) % mod
print(ans)

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

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Solution (Python):
def main():
    mod=998244353
    n,m,k=map(int,input().split())
    inv=lambda x: pow(x,mod-2,mod)
    Fact=[1] 
    l=max(n,m)
    for i in range(1,l+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(l+1) 
    Finv[-1]=inv(Fact[-1])
    for i in range(l-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    ans=0
    for i in range(k+1):
        c=comb(n-1,i)
        p=m*pow(m-1,n-i-1,mod)
        
        ans+=c*p
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
M = 998244353
n, m, k = map(int, input().split())
k = n - k - 1
p = n - 1
F = [1]
for i in range(n + 1091):
    F.append((F[-1] * (i + 1)) % M)


def C(k, n): return (F[n] * pow(F[k] * F[n - k], M - 2, M))


ans = pow(m, n, M)
for x in range(k):
    ans -= C(x, p) * m * pow(m - 1, x, M)
    ans %= M
print(ans)

Solution (Python):
n,m,k = map(int,input().split())
t = n-k-1
mod = 998244353
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [0]*(t+1)
if t >= 1:
  dp[1] = m
for i in range(2,t+1):
  dp[i] = dp[i-1]*(m-1)%mod
ans = pow(m,n,mod)
for i in range(len(dp)):
  ans = (ans-dp[i]*cmb(n-1,n-i))%mod
print(ans%mod)

Solution (Python):
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    
    nmax = 2 * 10 ** 5 + 10  
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % 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)%mod) % mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

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

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

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

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

print(ans)

Solution (Python):
MOD = 998244353

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

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

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

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

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

def C(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

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

Solution (Python):
class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

N, M, K = map(int, input().split())
if N == M == K == 0:
    exit()
MOD = 998244353
comb = Combination(N + K)

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

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

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    n, m, k = map(int, input().split())
    mf = modfact(n)
    res = 0
    for i in range(k + 1):
        res += m * pow(m - 1, n - i - 1, MOD) % MOD * mf.comb(n - 1, i)
        res %= MOD
    print(res)
resolve()

Solution (Python):

mod = 998244353


class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


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

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

print(ans)

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