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())
MOD = 998244353

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

fact[0] = fact[1]  = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD 

def main():
    if N == 1:
        print(M)
        return 
    num = M
    nums = [M]
    for i in reversed(range(1,N)):
        num *= i*(M-1)
        num *= inv[N-i]
        num %= MOD
        nums.append(num)
    nums.reverse()
    print(sum(nums[:K+1])%MOD)

    
if __name__ == "__main__":
    main()

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

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]



MOD = 998244353
INF = int(1e15)


def solve():
    MAX = 200010
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * 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

    N, M, K = Scanner.map_int()
    ans = 0
    for k in range(K + 1):
        tmp = M * pow(M - 1, N - 1 - k, MOD)
        tmp %= MOD
        cmb = fac[N - 1] * (finv[k] * finv[N - 1 - k] % MOD) % MOD
        tmp *= cmb
        tmp %= MOD
        ans += tmp
        ans %= MOD
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

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

mod = 998244353
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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


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


mm = [1]
for _ in range(n + 1):
    mm.append(mm[-1] * (m - 1) % mod)

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

print(ans)

Solution (Python):

class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod



N, M, K = map(int, input().split())
mod = 998244353
ans = 0
C = Combi(2*10**5, mod)
for i in range(K+1):
    ans += M*C.com(N-1, i)*pow(M-1, N-1-i, mod)
print(ans % mod)

Solution (Python):

















import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    n, m, K = map(int, input().split())
    class Combination:
        """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""

        def __init__(self, n, MOD):
            self.fact = [1]
            for i in range(1, n + 1):
                self.fact.append(self.fact[-1] * i % MOD)
            self.inv_fact = [0] * (n + 1)
            self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
            for i in reversed(range(n)):
                self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
            self.MOD = MOD

        def factorial(self, k):
            """k!を求める O(1)"""
            return self.fact[k]

        def inverse_factorial(self, k):
            """k!の逆元を求める O(1)"""
            return self.inv_fact[k]

        def permutation(self, k, r):
            """kPrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

        def combination(self, k, r):
            """kCrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

        def combination2(self, k, r):
            """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
            if k < r:
                return 0
            res = 1
            for l in range(r):
                res *= (k - l)
                res %= self.MOD
            return (res * self.inv_fact[r]) % self.MOD
    MOD = 998244353
    comb = Combination(10 ** 6, MOD)

    ans = 0
    df=m*pow(m-1,n-1-K,MOD)

    now = df
    for i in range(K, -1, -1):
        now = comb.combination(n-1, i)
        ans += now*df
        ans %= MOD
        df *= (m-1)
        df%=MOD

    print(ans)

resolve()

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

mod=998244353

com=1
ans=0

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

print(ans)

Solution (Python):
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def solve():
    n, m, k = rl()
    mod = 998244353
    ans = 0
    C = 1
    for d in range(k + 1):
        
        ans += m * pow(m - 1, n - 1 - d, mod) * C
        ans %= mod
        C = (C * (n - 1 - d) * modinv(d + 1, mod)) % mod
    print (ans)





mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Solution (Python):
import sys, math, itertools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def factorialMod(n, p):
    fact = [0] * (n+1)
    fact[0] = fact[1] = 1
    factinv = [0] * (n+1)
    factinv[0] = factinv[1] = 1
    inv = [0] * (n+1)
    inv[1] = 1
    for i in range(2, n + 1):
        fact[i] = (fact[i-1] * i) % p
        inv[i] = (-inv[p % i] * (p // i)) % p
        factinv[i] = (factinv[i-1] * inv[i]) % p
    return fact, factinv

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

def resolve():
    N, M, K = LI()

    ans = 0
    fact, factinv = factorialMod(N, MOD)

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

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import numpy as np
MAX = 200002
MOD = 998244353
fac = np.zeros(MAX)
finv = np.zeros(MAX)
inv = np.zeros(MAX)

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

def COM(N,K):
    return  int(fac[N]) * (int(finv[K]) * int(finv[N - K]) % MOD) % MOD

def resolve():
    N,M,K = map(int,input().split())
    ans = 0
    for i in range(K + 1):
        ans_k = M * COM(N-1, i )
        ans_k = ans_k * pow(M-1,N-1-i, MOD) % MOD
        ans = (ans + ans_k) % MOD
    print(ans)
resolve()

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

MOD = 998244353
fact = [1] * (n+1) 
factinv = [1] * (n+1) 
for i in range(n):
    fact[i+1] = fact[i] * (i+1) % MOD 
    factinv[i+1] = pow(fact[i+1], MOD-2, MOD)

def nCk(n,k): 
    return fact[n] * factinv[n-k] * factinv[k] % MOD

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

print(ans % MOD)

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

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

    return fact, factinv

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    return f[n] * v[r] * v[n - r] % p

f,v = prepare(n)

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

print(ans)

Solution (Python):
N,M,K = map(int,input().split())
MOD = 998244353
if M==1:
    print(1 if K==N-1 else 0)
    exit()

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

cs = []
ms = [(M * pow(M-1, N-1-K, MOD)) % MOD]
for i in range(K+1):
    cs.append(comb(N-1, i))
    if i:
        ms.append((ms[-1] * (M-1)) % MOD)

ans = 0
for c,m in zip(cs, ms[::-1]):
    ans += c*m
print(ans%MOD)

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

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


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

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

Solution (Python):
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    if m == 1:
        if k == n-1 or n == 1:
            print(1)
        else:
            print(0)
        return
        
    ans = 0
    m1 = [None]*n
    kai = [None]*n
    mi = 1
    ki = 1
    for i in range(n):
        m1[i] = mi
        mi *= m-1
        mi %= mod
        kai[i] = ki
        ki *= (i+1)
        ki %= mod
        
    def comb(a, b):
        return kai[a]*fermat(kai[a-b]*kai[b], mod)
        
    def fermat(x, p):
        """
        1/x (mod p) を返す
            x**(p-1) ≡ 1    [if gcd(x, p) == 1]
            x**(p-2) ≡ 1/x
            繰返し二乗法 
                ex: x**50  = (x**25)**2
                    x**25  = (x**12)**2 * x
                    x**12  = (x**6)**2
                    x**6   = (x**3)**2
        """
        times = []
        mod = p
        p -= 2
        while p > 1:
            times.append(p%2)
            p //= 2
        x %= mod
        out = x
        for i in times[::-1]:
            if i:
                out = (x*pow(out, 2, mod))%mod
            else:
                out = pow(out, 2, mod)
        return out
               
    for i in range(k+1):
        ans += m*comb(n-1, i)*m1[n-i-1]
        ans %= mod
    print(ans)

    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np

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

MOD = 998_244_353

def fact_table(N, MOD):
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1] = 1
    for n in range(2, N):
        q, r = divmod(MOD, n)
        inv[n] = inv[r] * (-q) % MOD
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[0] = 1
    for n in range(1, N):
        fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
    return fact, fact_inv, inv

def main(N, M, K):
    if N == 1:
        return M
    fact, fact_inv, inv = fact_table(N, MOD)
    f = fact[N - 1] * fact_inv[:N] % MOD * fact_inv[:N][::-1] % MOD
    f = f * M % MOD
    x = 1
    for n in range(1, N):
        x = x * (M - 1) % MOD
        f[n] *= x
    f %= MOD
    f = f[::-1]
    return f[:K + 1].sum() % MOD

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    fact_table = cc_export(fact_table, (i8, i8))
    main = cc_export(main, (i8, i8, i8))
    cc.compile()

from my_module import main

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

print(main(N, M, K))

Solution (Python):
N,M,K = map(int,input().split())
MOD = 998244353
if M==1:
    print(1 if K==N-1 else 0)
    exit()

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

cs = []
ms = [(M * pow(M-1, N-1-K, MOD)) % MOD]
for i in range(K+1):
    cs.append(comb(N-1, i))
    if i:
        ms.append((ms[-1] * (M-1)) % MOD)

ans = 0
for c,m in zip(cs, ms[::-1]):
    ans += c*m
print(ans%MOD)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353



















N, M, K = getNM()



Y = N + K + 1
fact =[1] 
for i in range(1, Y + 1):
    fact.append(fact[i - 1] * i % mod)

facv = [0] * (Y + 1) 
facv[-1] = pow(fact[-1], mod - 2 , mod)

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

def cmb(n, r):
    if n < r:
        return 0
    return fact[n] * facv[r] * facv[n - r] % mod

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

Solution (Python):

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

m = 998244353

result = 0
n = 1
k = 1
for i in range(K + 1):
    
    result += n * pow(k, m - 2, m) * pow(M - 1, N - 1 - i, m)
    result %= m
    n *= N - 1 - i
    n %= m
    k *= i + 1
    k %= m
result *= M
result %= m
print(result)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline


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


def make_table2(n, mod=10 ** 9 + 7):
    
    g1 = [0] * (n + 1)
    g1[0] = 1
    g1[1] = 1
    tmp = 1

    for i in range(2, n + 1):
        tmp = tmp * i % mod
        g1[i] = tmp

    
    g2 = [0] * (n + 1)
    g2[-1] = pow(g1[-1], mod - 2, mod)
    tmp = g2[-1]

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

    return g1, g2


N, M, K = map(int, read().split())
mod = 998244353
g1, g2 = make_table2(N, mod)
answer = 0
for i in range(K + 1):
    answer = (answer + cmb(N - 1, i, mod) * M * pow(M - 1, N - i - 1, mod)) % mod

print(answer)

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

MOD = 998244353


def prepare(n, MOD):
    fac = [None] * (n + 2)
    finv = [None] * (n + 2)
    inv = [None] * (n + 2)
    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
    return fac, finv


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


fac, finv = prepare(n, MOD)

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

print(ans)

Solution (Python):
N_MAX = 10**6
MOD = 998244353
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX


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


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


def main():
    com_init()
    n, m, k = map(int, input().split()) 

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



if __name__ == "__main__":
    main()

Solution (Python):
MOD = 998244353

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

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

print(ans)

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

MAXN = 2*(10**5)+10
p = 998244353
MOD = p
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % 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

out = 0
for i in range(K+1):
    out += M*nCr(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)

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

Solution (Python):
from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    
    
    
    
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


if __name__ == '__main__':
    main()

Solution (Python):
class Combination():  
    def __init__(self, N, MOD):  
        self.mod = MOD
        self.FACT = [1, 1]  
        self.INV = [0, 1]  
        self.FACTINV = [1, 1]  
        for i in range(2, N + 1):
            self.FACT.append((self.FACT[-1] * i) % self.mod)
            self.INV.append(pow(i, self.mod - 2, self.mod))
            self.FACTINV.append((self.FACTINV[-1] * self.INV[-1]) % self.mod)

    def calculate(self, N, R):  
        if (R < 0) or (N < R):
            return 0
        R = min(R, N - R)
        return self.FACT[N] * self.FACTINV[R] * self.FACTINV[N-R] % self.mod



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

cmb = Combination(n,mod)

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

print(cnt % mod)

Solution (Python):
class Combination:
    def __init__(self, max_n, _mod):
        self.mod = _mod

        self.fac = [0 for _ in range(max_n + 10)]
        self.finv = [0 for _ in range(max_n + 10)]
        self.inv = [0 for _ in range(max_n + 10)]

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

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

    def mod_comb(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0

        res = self.fac[n] * (self.finv[k] * self.finv[n - k] % self.mod)
        res %= self.mod

        return res


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

    comb = Combination(N, mod)

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

    print(ans)


main()

Solution (Python):
import math

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

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

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

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

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

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

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

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

print(ans)

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16

MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    def fast_pow(num, kata, mod):
        if kata == 0:
            return 1

        res = 1
        while kata > 0:
            if kata & 1 == 1:
                res = res * num % mod
            num = num * num % mod

            kata >>= 1
        return res

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

    n, m, k = ns()

    p, i = prepare(n, MOD)

    result = 0

    for ki in range(k + 1):
        ans = 1
        ans *= m % MOD
        ans *= fast_pow(m - 1, n - 1 - ki, MOD)
        ans %= MOD
        ans *= p[n - 1] * i[ki] * i[n - 1 - ki]
        ans %= MOD

        result += ans
        result %= MOD

    print(result)


if __name__ == '__main__':
    main()

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

t,c=(M*pow(~-M,~-N,P)),1
for k in range(1,K+1):
  c=(c*(N-k)*pow(k,P-2,P))%P
  t=(t+M*c*pow(~-M,(~-N-k),P))%P
print(t%P)

Solution (Python):
from sys import stdin
N,M,K = [int(x) for x in stdin.readline().rstrip().split()]
mod = 998244353
maxn = 2*10**5+1

fac  = [0 for _ in range(maxn)]
finv = [0 for _ in range(maxn)]
inv  = [0 for _ in range(maxn)]

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

for i in range(2,maxn):
    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 combinations(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

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

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

c = 1
answer = 0

for i in range(K+1):
    answer += (M * c  * pow(M-1, N - i - 1, mod)) % mod
    answer %= mod
    c = (c * (N-i-1) * pow(i+1, mod-2, mod)) % mod
    
print(answer)

Solution (Python):
def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装
    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく
        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            self.inverses.append(
                self.mod - self.inverses[self.mod % i] *
                (self.mod // i) % self.mod
            )
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する
        :param n: n
        :param k: k
        :return: nCk (mod m)
        """

        if k == 0:
            return 1
        if n == 0:
            return 0

        denominator = self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


MOD = 998244353

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

ans = 0
comb = ModCombination(mod=MOD, n_max=N)
for k in range(0, K + 1):
    ans += (M * comb.mod_combination(N - 1, k)) % MOD * mod_pow(M - 1, N - 1 - k, MOD)
    ans %= MOD

print(ans)

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

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

Solution (Python):
n, m, k = [int(t) for t in open(0).read().split()]
mod = 998244353
mem = [0] * max(k + 3, n + 1)
for i in range(k + 2):
    mem[i] = pow(m, i, mod)
c = 1
for i in range(k + 2, n + 1):
    mem[i] = (m * mem[i - 1] - m * c * pow(m - 1, i - k - 2, mod)) % mod
    c = (c * (i - 1) * pow(i - k - 1, - 1, mod)) % mod
print(mem[n])