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:
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


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

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_MAX + 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

    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

    ans = 0
    power = M % MOD
    for k in range(N - 1, -1, -1):
        if k <= K:
            ans += mod_com(N - 1, k) * power % MOD
        power = power * (M - 1) % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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))  # 10
    """
    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):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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

n,m,k = myinput()
mod = 998244353

comb = Combination(n,mod)

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

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def comb_mod_faster(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k = min(n-k,k)
    ans = 1
    inv = [1]*(k+1)
    if k>=1:
        ans *= (n-k+1)%mod
    for i in range(2,k+1):
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        ans = ans*(n-k+i)*inv[i]%mod
    return ans

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

def make_comb_mod_list(n,mod):
    r = n
    ls = [0]*(n+1)
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    ls[0] = 1
    ls[1] = n
    for i in range(2, n + 1):
        fac.append(fac[-1] * i % mod)
        inv.append(-inv[mod % i] * (mod // i) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
        ans = int(fac[n] * finv[r] * finv[n - r] % mod)
        ls[i] = ans
    return ls

# nCrをすべてのr(0<=r<=n)について求める
# nC0, nC1, nC2, ... , nCn を求める
# modinvが必要
def combination_list(n, mod=10**9+7):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst

def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i]=="1":
            res = (res*a) % p
    return res

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))  # 10
    """
    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):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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

n,m,k = myinput()
mod = 998244353

comb = Combination(n,mod)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from functools import reduce
from operator import mul

MOD = 998244353  # type: int

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def solve(N: int, M: int, K: int):
    SUM = ModInt(0)
    n_1Ck = [ModInt(1) for k in range(K + 1)]
    for i in range(1, K + 1):
        n_1Ck[i] = n_1Ck[i-1] * (N-i) / i
    for k in range(0, K + 1):
        SUM += M * n_1Ck[k] * (pow(M - 1, N - 1 - k, MOD))
    print(SUM)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
MOD = 998244353
fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
N,M,K = map(int,input().split())
for i in range(2, N+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
s = 0
for i in range(K+1):
    s += M*pow(M-1,N-1-i,MOD)*comb_mod(N-1,i,MOD)
    s %= MOD
print(s%MOD)

Submission status: Accepted

Solution code:
N, M, K = [int(_) for _ in input().split()]

MOD = 998244353
L = 200001

Fm = {}

inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % MOD

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], MOD - 2, MOD)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % MOD
    return result

result = 0


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

print(result)

Submission status: Accepted

Solution code:
class Combination:
    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):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    MOD = 998244353
    ans = 0
    comb = Combination(1000000, MOD)

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

    print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]

for i in range(1, N+1):
    nCi.append(nCi[i-1]*(N-i) * pow(i, mod-2, mod) % mod)


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

print(ans)

Submission status: Accepted

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

def bin(a, b, p):
    res = 1
    while b > 0:
        if b & 1 > 0:
            res = res * a % p
        a = a * a % p
        b >>= 1

    return res

MOD = 998244353
N = 200000 + 50
f = [0 for i in range(N)]
invf = [0 for i in range(N)]

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

invf[n] = bin(f[n], MOD-2, MOD)
for ri in range(1, N-1):
    i = n - ri
    invf[i] = invf[i+1] * (i+1) % MOD

def binom(n, m):
    if n < m or n < 0 or m < 0:
        return 0
    return f[n] * invf[m] % MOD * invf[n-m] % MOD

def g(n, m):
    return m * bin(m-1, n-1, MOD)

ans = 0
for i in range(0, k+1):
    # print(n-i, i, binom(n-1, i), bin(n-i, m, MOD), n-i, m)
    ans = (ans + binom(n-1, i) * g(n-i, m)) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

def main():
    mod=998244353
    N,M,K=MI()
    
    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

    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)
        
        
    p=[1]*(N+3)#(M-1)^i
    for i in range(N+2):
        p[i+1]=(p[i]*(M-1))%mod
        
    ans=0
    for i in range(K+1):
        temp=M*p[N-1-i]*cmb(N-1,i,mod)
        temp%=mod
        ans=(ans+temp)%mod
        
    print(ans)

main()

Submission status: Accepted

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

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

# --+----+----+----+----+----+----+----+----+
# 予め逆元の階乗をO(n)で計算することにより
# nCr(mod.p)をO(1)で計算する
MOD = 998244353

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

for i in range(2, N+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
# --+----+----+----+----+----+----+----+----+

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

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M, K = map(int, input().split())

if M == 1 :
    if K == N-1:
        print(1)
    else:
        print(0)
    sys.exit()

def power_func(a, n, p):
    bi = str(format(n,"b"))#2進表現に
    if a == 0:
        return 0
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res

P = 998244353
inv_t = [0] + [1]
for i in range(2, max(M,K)+2):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

Submission status: Accepted

Solution code:
import sys

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))  # 10
    """

    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):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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

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

mod = 998244353
ans = 0

comb = Combination(2*10**5)


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

print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
def nCr(n,r,fac,finv):
    mod = 998244353
    ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    return ans
ans = 0
mod = 998244353
fac = [1,1]+[0]*n
finv = [1,1]+[0]*n
inv = [1,1]+[0]*n
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
for i in range(k+1):
    ans += m*pow(m-1,n-1-i,mod)*nCr(n-1,i,fac,finv) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def extgcd1(a0,b0):
    u=1
    v=0
    a=a0
    b=b0
    while b:
        t=a//b
        a-=t*b
        a,b=b,a
        u-=t*v
        u,v=v,u
    if a!=1: 
        #print("not 素")
        return -1
    return u%b0 #a0*u=1(mod b0)

def main():
    mod =998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    # dp=[0]*2
    # ndp=copy(dp)
    # dp[0]=0
    # dp[1]=M
    # for i in range(2,N+1):
    #     if i<=K+1:
    #         ndp[0]=((M-1)*(dp[0]+dp[1])+dp[0])%mod
    #         ndp[1]=dp[1]
    #     else:
    #         ndp[0]=(M*dp[0]+(M-1)*dp[1])%mod
    #         ndp[1]=0

    #     dp=copy(ndp)
    # ans=(dp[0]+dp[1])%mod
    # #print(ans)

    #n0=math.factorial(N-1)
    #ks=[1]*(N-1+1)
    #for k in range(2,N-1+1):
    #    ks[k]=ks[k-1]*k
    ans=0
    c0=1
    c1=pow(M-1,N-1,mod)
    inv=[1,1]+[extgcd1(i,mod) for i in range(2,N)]
    #print("ok1")
    ifac=[1]*(N)
    nfac=1
    for i in range(1,N):
        nfac=(i*nfac)%mod
        ifac[i]=(ifac[i-1]*inv[i])%mod
    #print("ok2")
    #print(ifac)
    
    
    mp=[1]*(N)
    for i in range(1,N):
        mp[i]=(mp[i-1]*(M-1))%mod
    #print("ok3")
    ans=0
    #print(nfac)
    #print(mp)
    
    for k in range(0,K+1):
        #print((n0//ks[k]//ks[N-1-k]))
        ans=ans+(mp[N-1-k]*nfac*ifac[k]*ifac[N-1-k])%mod
        ans%=mod
        #print(ans)
    #print(ks)
    ans=(ans*M)%mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def extgcd1(a0,b0):
    u=1
    v=0
    a=a0
    b=b0
    while b:
        t=a//b
        a-=t*b
        a,b=b,a
        u-=t*v
        u,v=v,u
    if a!=1: 
        #print("not 素")
        return -1
    return u%b0 #a0*u=1(mod b0)

def main():
    mod =998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    # dp=[0]*2
    # ndp=copy(dp)
    # dp[0]=0
    # dp[1]=M
    # for i in range(2,N+1):
    #     if i<=K+1:
    #         ndp[0]=((M-1)*(dp[0]+dp[1])+dp[0])%mod
    #         ndp[1]=dp[1]
    #     else:
    #         ndp[0]=(M*dp[0]+(M-1)*dp[1])%mod
    #         ndp[1]=0

    #     dp=copy(ndp)
    # ans=(dp[0]+dp[1])%mod
    # #print(ans)

    #n0=math.factorial(N-1)
    #ks=[1]*(N-1+1)
    #for k in range(2,N-1+1):
    #    ks[k]=ks[k-1]*k
    ans=0
    c0=1
    c1=pow(M-1,N-1,mod)
    inv=[1,1]+[pow(i,mod-2,mod) for i in range(2,N)]
    #print("ok1")
    ifac=[1]*(N)
    nfac=1
    for i in range(1,N):
        nfac=(i*nfac)%mod
        ifac[i]=(ifac[i-1]*inv[i])%mod
    #print("ok2")
    #print(ifac)
    
    
    mp=[1]*(N)
    for i in range(1,N):
        mp[i]=(mp[i-1]*(M-1))%mod
    #print("ok3")
    ans=0
    #print(nfac)
    #print(mp)
    
    for k in range(0,K+1):
        #print((n0//ks[k]//ks[N-1-k]))
        ans=ans+(mp[N-1-k]*nfac*ifac[k]*ifac[N-1-k])%mod
        ans%=mod
        #print(ans)
    #print(ks)
    ans=(ans*M)%mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

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

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

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0:
            return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k:
            return 1
        if k == 0:
            return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k:
            return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0:
            return 1
        if n % 2 and n >= 3:
            return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


n, m, k = map(int, read().split())
mod = 998244353
comb = Combination(n, mod)
ans = 0
n -= 1
for i in range(k + 1):
    ans += comb.C(n, n - i) * m * pow(m - 1, n - i, mod) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
M = 998244353
n,m,K = map(int,input().split())
ans = 0
c = 1
for k in range(K+1):
    ans += c * m * pow(m-1,n-k-1,M)
    c *= (n-k-1) * pow(k+1,M-2,M)
    ans %= M
    c %= M
print(ans)

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

    N,M,K = LMIIS()
    ans = 0
    cmb = Combinations(N-1,MOD)
    #i個のブロックを連結、全体でN-i個、どこを連結させるかは(N-1)Ci通り
    powtable = [0] * N
    powtable[N-K-1] = pow(M-1,N-K-1,MOD) % MOD
    for i in range(N-K,N):
        powtable[i] = powtable[i-1] * (M-1) % MOD

    for i in range(K+1):
        ans += powtable[N-i-1] * cmb.nCr(i)
        ans %= MOD
    # for i in range(K+1):
    #     ans += M * pow(M-1,N-i-1,MOD) * cmb.nCr(i)
    #     ans %= MOD
    print(ans*M%MOD)

    

if __name__ == '__main__':
    main()