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:
# ライブラリ改変テスト
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)
######################

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
        # print (d)
        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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)# MODを法とした逆元（フェルマーの小定理）

def nCk(n,k): # 組み合わせ(MOD)を返却する
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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  # N は必要分だけ用意する
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)%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)

Submission status: Accepted

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

Submission status: Accepted

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

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


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

# N:ブロック
# M:色（バリエーション）
# K:隣合う組み
# N, M, K = 6, 2, 3のとき
# K = 0 のとき
# 121212, 212121
# K = 1のとき,
# 12121 のどこかに同じ数字を挟み込めば
# 112121, 122121という風にできる
# K = 2のとき
# 1212 のどこかに同じ数字を挟む　を２回行う
# 112212, 112122もできるし
# 111212, 122212もできる
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)

Submission status: Accepted

Solution code:
# フェルマーの小定理
N, M, K = map(int, input().split())

m = 998244353

result = 0
n = 1
k = 1
for i in range(K + 1):
    # result += M * mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # return fac[n] * (finv[k] * finv[n - k]) % 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()

Submission status: Accepted

Solution code:
MOD = 998244353

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

ans = 0
NCi = 1#nからi選ぶ組み合わせ
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)

Submission status: Accepted

Solution code:
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"))#2進表現に
  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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Combination():  # nCr(mod p) #n<=10**6
    def __init__(self, N, MOD):  # cmbの前処理
        self.mod = MOD
        self.FACT = [1, 1]  # 階乗
        self.INV = [0, 1]  # 各iの逆元
        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):  # nCr(mod p) #前処理必要
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod MOD)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod MOD)
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)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
# MOD = 10 ** 9 + 7
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()))


# ===CODE===


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def modpow(a, n, mod):
    if n == 0:
        return 1
    else:
        if n % 2 == 0:
            return (modpow((a * a)%mod, n//2, mod)) % mod
        else:
            return ((a%mod) * modpow(a, n-1, mod)) % mod

# modが素であるとする
def modinv(a, mod):
    return modpow(a, mod-2, mod) % mod

def moddiv(a, b, mod):
    return ((a%mod) * modinv(b, mod)) % mod

def modbase(n, k, mod):
    fact = [1 for _ in range(n+1)]
    inv = [1 for _ in range(n+1)]
    finv = [1 for _ in range(n+1)]

    for i in range(2, n+1):
        fact[i] = (fact[i-1] * i) % mod
        inv[i] = (-inv[mod % i] * (mod // i)) % mod
        finv[i] = (finv[i-1] * inv[i]) % mod
    return fact, inv,finv


N, M, K = [int(i) for i in input().split()]
mod = 998244353
# N-1 V K
fact, inv, finv = modbase(N-1, K, mod)
dic = {}
dic[0] = 1
for k in range(1, K+1):
    dic[k] = fact[N-1] * (finv[k] * finv[N-k-1] % mod) % mod

sum = 0
for k in range(K+1):
    sum += M * (modpow(M-1 , N-1-k, mod) * dic[k] % mod) % mod
    sum %= mod
print(sum)

Submission status: Accepted

Solution code:
mod=998244353
n,m,k=map(int,input().split(' '))
F=[1 for i in range(n+1)]
for i in range(1,n+1):
    F[i]=F[i-1]*i%mod
I=[1 for i in range(n+1)]
for i in range(2,n+1):
    I[i]=(mod-int(mod/i))*I[mod%i]%mod
for i in range(2,n+1):
    I[i]=I[i]*I[i-1]%mod
def binom(n,k):
    return F[n]*I[k]%mod*I[n-k]%mod
pw=[1 for i in range(n+1)]
for i in range(1,n+1):
    pw[i]=pw[i-1]*(m-1)%mod
ans=0
for i in range(k+1):
    sz=n-i
    ans+=binom(n-1,i)*m%mod*pw[sz-1]%mod
    ans%=mod
print(ans)

Submission status: Accepted

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

def inv(a):
  return pow(a,MOD-2,MOD)
fact=[0,1]
for i in range(2,N+1):
  fact.append((fact[-1]*i)%MOD)
def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD
exp=[1]

def pow_k(x,n):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=K*x%MOD
            x=x**2%MOD
            n=(n-1)//2
        else:
            x=x**2%MOD
            n=n//2
    return K*x%MOD 

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

Submission status: Accepted

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

#逆元を定義する
def inv(a):
  return pow(a,MOD-2,MOD)

#「n!」の剰余を求める
fact=[0,1]
for i in range(2,N+1):
  fact.append((fact[-1]*i)%MOD)

#nCr(MOD)を求める
def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD

#(M-1)**n(MOD)を求める
exp=[1]
for i in range(1,N):
  exp.append((exp[-1]*(M-1))%MOD)  
  

#答えを計算する
ans=0
for i in range(K+1):
  ans+=(M*choose(N-1,i)*exp[N-1-i]%MOD)  
  ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


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


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m, k = [int(_) for _ in input().split()]
ans = 0
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    # print(ans)
print(ans)