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



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]*m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%=mod
		cnt*=m*mp[n-kk-1]
		cnt%=mod
		ans+=cnt
	print(ans%mod)













if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
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 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

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

max = max(N,2) 
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Submission status: Accepted

Solution code:
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 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

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

max = N + 1
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Submission status: Accepted

Solution code:
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 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

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

max = N + M + K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Submission status: Accepted

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

MAX = 10**6
def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 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
    return fac, finv, inv



def comb(n, k):
    """
    nCk mod MODを求める.
    この部分はO(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)


fac, finv, inv = COMinit()
ans = 0
for L in range(N-K, N+1):
    tmp = M*pow(M-1, L-1, MOD)%MOD
    tmp *= comb(N-1, L-1)
    ans += tmp % MOD
    ans %= MOD
print(ans%MOD)

Submission status: Accepted

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

facm = 200500
fac = [1] * facm
facinv = [1] * facm
for i in range(facm-1):
    fac[i+1] = (fac[i] * (i + 1)) % mod
    facinv[i+1] = (facinv[i] * pow(i+1, -1, mod)) % mod

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

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

print(ans)

Submission status: Accepted

Solution code:
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):  # nCk
        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
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%mod
for i in range(K+1):
    tmp=M*c[N-i-1]*C.calc(N-1,N-i-1)%mod
    ans=(ans+tmp)%mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

def cin():  return list(map(int,input().split()))
N, M, K = cin()
MOD = 998244353

fac = [1] * (N + 1)
inv = [1] * (N + 1)

for j in range(1, N + 1):  fac[j] = fac[j - 1] * j % MOD

inv[N] = pow(fac[N], MOD - 2, MOD)
for j in range(N - 1, -1, -1):  inv[j] = inv[j + 1] * (j + 1) % MOD
    
def cmb(n, r):
    if r > n or n < 0 or r < 0:  return 0
    return fac[n] * inv[n - r] * inv[r] % MOD

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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
kMod = 998244353

# [100, 0, 0]                                                                                                                                                                                                                                 
# [100, 9900, 0]                                                                                                                                                                                                                              
# [100, 19800, 9900*99]                                                                                                                                                                                                                       

# M, M*(M-1)*C(N-1, 1),M*(M-1)^2*C(N-1, 2),M*(M-1)^3*C(N-1,3)                                                                                                                                                                                 

ans = 0
for i in range(N):
    if i == 0:
        acc = M
    else:
        acc *= (M-1)
        acc %= kMod
        acc *= (N-i)
        acc %= kMod
        acc *= pow(i, kMod-2, kMod)
        acc %= kMod
    if i >= N-K-1:
        ans += acc
        ans %= kMod
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class Combination:
    def __init__(self, n, p):
        self.n = n
        self.p = p
        self.note = [1, 1]
        self.noteinv = [1, 1]
        self.inv = [0, 1]
        self.calc()

    def calc(self):
        for i in range(2, self.n + 1):
            self.note.append((self.note[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.noteinv.append((self.noteinv[-1] * self.inv[-1]) % self.p)
    
    def nCr(self, n, r):
        n = self.n
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return (self.note[n] * self.noteinv[r] * self.noteinv[n - r]) % self.p

def Main():
    n, m, k = read_ints()
    # m * _{n-1}C_k * 1^k * (m-1)^{n-1-k}

    p = 998244353
    modm = [1]
    for _ in range(1, n):
        modm.append((modm[-1] * (m - 1)) % p)
    
    cmb = Combination(n - 1, p)
    ans = 0
    for i in range(k + 1):
        ans += (cmb.nCr(n - 1, i) * m * modm[n - 1 - i]) % p
        ans %= p
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
fac = [1]
mod = 998244353
for i in range(1,N+1):
    fac.append(fac[i-1]*i % mod)
ifac = [None]*(N+1)
ifac[-1] = pow(fac[N], mod-2, mod)
for i in range(N, 0, -1):
    ifac[i-1] = ifac[i]*i % mod
ans = 0
for k in range(K+1):
    t = M*fac[N-1] % mod
    t = t*ifac[N-1-k] % mod
    t = t*ifac[k] % mod
    t = t*pow(M-1,N-1-k, mod)
    t %= mod
    ans = (ans+t) % mod
print(ans)

Submission status: Accepted

Solution code:
n, m, K = map(int, input().split())
mod = 998244353

fac = [1] * (n + 1)
inv = [1] * (n + 1)

for j in range(1, n + 1):
    fac[j] = fac[j - 1] * j % mod

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


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


def paint(k):
    res = (m * comb(n-1, k)) % mod * pow(m-1, n-1-k, mod)
    res %= mod
    return res

ans = 0
for k in range(K+1):
    ans += paint(k)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
fact = [1 for _ in range(200000)]
inv = [1 for _ in range(200000)]
fact_inv = [1 for _ in range(200000)]

mod = 998244353
for i in range(2, 200000):
    fact[i] = (fact[i-1]*i) % mod
    inv[i] = mod - (inv[mod % i] * (mod // i)) % mod
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % mod

N, M, K = map(int, input().split())
ans = 0
a = pow(M-1, N-1-K, mod)
for i in range(K, -1, -1):
    ans += (fact[N-1] * fact_inv[i] * fact_inv[N-1-i]) * M * a
    ans = ans % mod
    a *= M-1
    a = a % mod
print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=998244353
ans=m*pow(m-1,n-1,mod)
ans%=mod

if k==0:
  print(ans)
  exit()

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

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx


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


print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

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

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

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

ans = 0
for i in range(K + 1):
	t = (M * pow_mmm[N - 1 - i]) % MOD
	comb = (fac[N - 1] * pow(fac[N - 1 - i], MOD - 2, MOD) * pow(fac[i], MOD - 2, MOD)) % MOD
	t = (t * comb) % MOD
	ans = (ans + t) % MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,M,K=map(int,input().split())

mod=998244353


fac = [1] * (n + 1)
inv = [1] * (n + 1)

for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


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


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

ans=0
temp=(M*(M-1)**(n-K-1))%mod#1乗
for k in range(K+1)[::-1]:
    ans=(ans+temp*comb(n-1,k))%mod
    temp=(temp*(M-1))%mod

print(ans)

Submission status: Accepted

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

N = 10**5 * 2  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

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

print(ans)

Submission status: Accepted

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

N = 10**6  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

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

print(ans)

Submission status: Accepted

Solution code:
# 隣り合うブロックの組で色が異なるものがk(0,1,2,...,K)個とする。
# (左端の色) × (2~N番目のうち、どのk箇所を選ぶか) × (2~N番目の色)
# = M * N-1_C_k * (M-1)**(N-k-1)

from math import factorial
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


fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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 k in range(K + 1):
    tmp = M * cmb(N - 1, k, p) * pow(M - 1, N - k - 1, p)
    ans += tmp % p

ans = ans % p
print(ans)

Submission status: Accepted

Solution code:
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 *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 逆元事前処理ver
# nが小さい場合に
lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
mod = 998244353

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

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

N, M, K = getNM()

# 隣会うブロックの組みがk個の塗り方の通りの数
# 2つ目以降の塗り方について
# 前の色と違う色を塗る M - 1通り
# 前の色と同じ色を塗る 1通り

# dp[i][j]: iまで塗り進めた時、同じ色の組みがj組のもの
# 今回の問題は対称性があるので、dp使わなくてもいける

# N = 3の時、隣り合うブロックの組であって同じ色で塗られている組が1組以下である通りは
# M * (M - 1) * 1 +
# M * 1 * (M - 1)

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

Submission status: Accepted

Solution code:
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,m,k=map(int,input().split())

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

mod = 998244353
N, M, K = mapint()

pos = {}
neg = {}
pos[0] = 1
neg[0] = 1
for i in range(1, N+1):
    pos[i] = i*pos[i-1]%mod
    neg[i] = pow(pos[i], mod-2, mod)
ans = 0
for i in range(K+1):
    ans += M*pow((M-1), (N-i-1), mod)*pos[N-1]*neg[i]*neg[N-i-1]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
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 = n #Nの最大値
g1 = [0]*(N+1) #元テーブル(p(n,r))
g1[0] = g1[1] = 1
g2 = [0]*(N+1) #逆元テーブル
g2[0] = g2[1] = 1
inverse = [0]*(N+1) #逆元テーブル計算用テーブル
inverse[0],inverse[1] = 0,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

# i組　-> m * (n-1)Ci * (m-1)^(n-1-i)
ans = 0
for i in range(k+1):
    ans += m * cmb(n-1,i,mod) * pow(m-1,n-1-i,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n, r):
    return fact[n] * pow(fact[n-r], mod-2, mod) * pow(fact[r], mod-2, mod) % mod

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

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class youk_prepare:
    def __init__(self, n, mod=pow(10, 9) + 7):
        """
        コンストラクタ
        :n個の物に対する組み合わせを求める(200万くらいなら十分動く。1億とかは無理。)
        :余り 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

        # fn：1～nの階乗のリスト(mod結果) invs：0～nまでの数値の逆数のリスト
        self.factorials = factorials
        self.invs = invs
        self.mod = mod

    def cmb(self, n, r):
        """
        組み合わせ数を求める
        :n個の物からr個を選ぶ
        """
        if len(self.factorials) - 1 < n:
            raise ValueError("コンストラクタで指定した要素数を超えているので無理。")
        return (self.factorials[n] * self.invs[r] * self.invs[n - r]) % self.mod

    def multi_cmb(self, n, r):
        """
        重複組み合わせ数を求める
        :n種類のものから重複を許してr個選ぶ(例3職のボールから5つを選ぶ)
        """
        if len(self.factorials) - 1 < n:
            raise ValueError("コンストラクタで指定した要素数を超えているので無理。")
        return (self.factorials[n] * self.invs[r] * self.invs[n - r]) * (
                self.factorials[n - 1] * self.invs[r] * self.invs[n - 1 - r]) % self.mod


def prepare(n, mod=998244353):
    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 resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    # 全組み合わせ数(重複順列)
    # all_pattern = pow(m, n, 998244353)

    prepare = youk_prepare(200000, 998244353)
    # 使用方法サンプル(10 N 3= 10個の要素から3つを選ぶ場合の組み合わせ数)
    # fns, invs = prepare(200000)

    # さらに6 N 5= 6個の要素から5つを選ぶ場合の組み合わせ数 ->このように、大量のパターンが欲しいときはこっちを使う。
    # aa = (fns[6] * invs[5] * invs[6 - 5]) % 998244353  # ans=120

    # 許容される組み合わせを加算していく
    ans = 0
    for i in range(k + 1):
        # ans += (m * pow(m - 1, m - i - 1, 998244353) * cmb(n - 1, i)) % 998244353
        # ans = (fns[n-1] * invs[k] * invs[n-1 - k]) % 998244353
        # ans += m * pow(m - 1, n - i - 1, 998244353) * (fns[n - 1] * invs[i] * invs[n - 1 - i])
        ans += m * pow(m - 1, n - i - 1, 998244353) * prepare.cmb(n - 1, i)
        ans = ans % 998244353

    print(ans)

    # ans = (m * pow(m - 1, m - k - 1, 998244353) * cmb(n - 1, k)) % 998244353

    # カウント外の組み合わせ数
    # kpl1 = k + 1
    # ng_pattern = m * pow((m - 1), n - (k + 1), 998244353)
    # ng_pattern = ng_pattern % 998244353
    # ans = all_pattern - ng_pattern


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def prepare(n, mod=998244353):
    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 cmb(n, r):
    mod = 998244353
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


# 実装を行う関数
def resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    # 全組み合わせ数(重複順列)
    # all_pattern = pow(m, n, 998244353)

    # 使用方法サンプル(10 N 3= 10個の要素から3つを選ぶ場合の組み合わせ数)
    fns, invs = prepare(2000000)

    # さらに6 N 5= 6個の要素から5つを選ぶ場合の組み合わせ数 ->このように、大量のパターンが欲しいときはこっちを使う。
    # aa = (fns[6] * invs[5] * invs[6 - 5]) % 998244353  # ans=120

    # 許容される組み合わせを加算していく
    ans = 0
    for i in range(k + 1):
        # ans += (m * pow(m - 1, m - i - 1, 998244353) * cmb(n - 1, i)) % 998244353
        # ans = (fns[n-1] * invs[k] * invs[n-1 - k]) % 998244353
        ans += m * pow(m - 1, n - i - 1, 998244353) * (fns[n - 1] * invs[i] * invs[n - 1 - i])
        ans = ans % 998244353

    print(ans)

    # ans = (m * pow(m - 1, m - k - 1, 998244353) * cmb(n - 1, k)) % 998244353

    # カウント外の組み合わせ数
    # kpl1 = k + 1
    # ng_pattern = m * pow((m - 1), n - (k + 1), 998244353)
    # ng_pattern = ng_pattern % 998244353
    # ans = all_pattern - ng_pattern


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()