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
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [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)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv
 
    # 二項係数計算
    def Combination(n, k, MOD=998244353):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret
 
    MOD = 998244353
    N, M, K = map(int, inp().split())
 
    # テーブルを作成し、K回使いまわす
    fac, finv = COMinit(N-1, MOD)
 
    ans = 0
    for k in range(K+1):
        cmb = Combination(N-1, k)
        m_pow = pow(M-1, (N-k-1), MOD)
        ans += M * m_pow * cmb
        ans %= MOD
 
    print(ans)
  
if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

mod = 998244353
fact = [1, 1]
factinv = [1, 1]
inv = [0,1]
rui = [1,m-1]

for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    rui.append(rui[-1]*(m-1) % mod)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, K = lr()
    MOD = 998244353
    SIZE = 4*10**5+1
    SIZE += 1
    inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0]*SIZE  # fac[j] = j! mod MOD
    finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2,SIZE):
        inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
        fac[i] = fac[i-1]*i%MOD
        finv[i]= finv[i-1]*inv[i]%MOD
    def choose(n,r): # nCk mod MOD の計算
        if 0 <= r <= n:
            return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
        else:
            return 0
    ans = 0
    for i in range(K+1):
        ans += choose(N-1, i)*M*pow((M-1), N-1-i, MOD)%MOD
        ans %= MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353
 
MAX_N = 2 * 10**5 + 10
 
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
 
fac_inv = [1] + [0] * MAX_N
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD
 
ans = 0
n, m, k = map(int, input().split())
 
for i in range(k + 1):
    orig = n - i
    cnt = m * pow(m - 1, orig - 1, MOD)
    cnt = cnt * mod_nCr(n-1, i)
    ans += cnt
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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

Submission status: Accepted

Solution code:

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [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)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=998244353):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    # テーブルを作成し、K回使いまわす
    fac, finv = COMinit(N-1, MOD)

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

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
MOD=998244353
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;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,inv

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

N,M,K=map(int,input().split())
fac,finv,inv=facinv(N)
mm=[1]
for i in range(N+1):
    mm.append(mm[-1]*(M-1)%MOD)
ans=0
for i in range(K+1):
    ans=(ans+(COM(N-1,N-i-1)*M%MOD*mm[N-i-1]%MOD))%MOD
print(ans)

Submission status: Accepted

Solution code:
U = 2*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Submission status: Accepted

Solution code:
import math


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):
        if n < r:
            return 0
        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


def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    ans = 0
    comb = Combination(10**6)
    for k in range(K+1):
        tmp = M * pow(M-1,N-(k+1),MOD)
        tmp %= MOD
        ans += tmp * comb(N-1,k)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def power(n,r):
    res = 1
    for i in range(r):
        res *= n
        res %= p
    return res

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

p = 998244353

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)

num = 0

pw = (m-1)**(n-k-1) % p

for i in range(k+1):
    num += m * pw * binom(n-1, k - i)
    num %= p
    pw *= m-1
    pw %= p

print(num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
inv = [1] * N
FAC = factorial(N - 1) % MOD
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for i in range(1, N):
        inv[i] = (inv[i - 1] * pow(i, MOD - 2, MOD)) % MOD
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        # punc = (N-1)!/k!/(N-k-1)!
        # punc = factorial(
        #     k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        punc = FAC
        # punc *= pow(factorial(k), MOD - 2, MOD)
        punc *= inv[k]
        punc = punc % MOD
        # punc *= pow(factorial(N - k - 1), MOD - 2, MOD)
        punc *= inv[N - k - 1]
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')

Z = 998244353


class Comb:
    def __init__(self, n):
        self.n = n
        self.e = [1] * (n + 1)
        for j in range(n):
            self.e[j + 1] = (self.e[j] * (j + 1)) % Z
    
    def z_pow(self, a, n):
        # a ^ n
        if n == 0:
            return 1
        if n == 1:
            return a % Z
        m = n // 2
        i = n - m * 2
        x = self.z_pow(a, m)
        return (x * x * self.z_pow(a, i)) % Z

    def get(self, i):
        if self.n - i < i:
            return self.get(self.n - i)
        return (self.e[self.n] * self.z_pow(self.e[i], Z - 2) * self.z_pow(self.e[self.n - i], Z - 2)) % Z


def calc(N, M, K):
    comb = Comb(N - 1)
    p = (M * (M - 1) ** (N - 1 - K)) % Z
    r = 0
    for x in range(K, -1, -1):
        r = (r + comb.get(x) * p) % Z
        p = (p * (M - 1)) % Z
    return r
    

(N, M, K) = tuple([int(s) for s in input().split()])
print(calc(N, M, K))

Submission status: Accepted

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

l_lis = [1]
r_lis = [1]

l, r = 1, 1
for j in range(K+1):
    l = l*(j+1)%mod
    r = r*(N-j-1)%mod
    l_lis.append(l)
    r_lis.append(r)

def comb(a, b):
    global mod
    l = l_lis[b]
    r = r_lis[b]
    return (r*pow(l, mod-2, mod))%mod
 
ans = 0
for i in range(K+1):
    ans += comb(N-1, i)*M*pow((M-1), (N-1-i), mod)%mod

print(ans%mod)

Submission status: Accepted

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


fac = [1] * n
finv = [1] * n
inv = [1] * n


def COMinit():
    for i in range(2, n):
        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 < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


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

Submission status: Accepted

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

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

Submission status: Accepted

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

mod = 998244353
NUM = 3*(10**5)
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

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

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

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

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


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


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


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

print(ans)

Submission status: Accepted

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

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

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


def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,M,K=map(int, input().split())
mod=998244353
if M==1:
  if N-1<=K:
    print(1)
    exit()
  else:
    print(0)
    exit()
    
MAX_N = 10**6
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

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

def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

def f(k,n,m):
  #a=(pow(m-1,n-k)*m//(m-1))%mod
  a=(pow(m-1,n-k-1,mod)*m)%mod
  b=mod_comb_k(n-1,k,mod)
  return a*b%mod

ans=0
for i in range(0,K+1):
  d=f(i,N,M)
  ans+=d
  ans%=mod
  #print(d)
print(ans)

Submission status: Accepted

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

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

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


def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]


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

Submission status: Accepted

Solution code:

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

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

"""
・思いついた
隣り合うブロックの組であって同じ色で塗られている組の個数を、0~Kまでそれぞれ数え上げて足し合わせる

・思いつかなかった
組みの個数の場合の数を数える方法
-> 11232333 みたいな並びだと、同じ色の組は3つになっている
 これらの組みの選び方は、ブロックN個には間がN-1個あるから、ここからk個選べば良い
 （組の数なので、111だと左の11で1組、右の11で1組になる（111で三つ同じ色じゃん！とか思ってた））
  すると、選んだ間の両側にあるブロックを一つの塊とみなせるので、これはM個の色を選べる。
  残りはM-1個から選べる。
  なので、M * nCr(N-1, k) * (M-1)**(N-1-k)
  (M色取りうる奴の色の選び方 x どの位置で組を作るか x 隣り合うブロックの色が被らないものの選び方)
"""
ans = 0
for k in range(K+1):
    if k == 0:
        ans += M * pow(M-1, N-1, MOD)
        
    else:
        ans += M * nCr(N-1, k) * pow(M-1, N-k-1, MOD) 

    ans %= MOD

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


powers = {(M-1, N-1): pow(M-1, N-1, mod)}


def power(x, y):
    if y == 0:
        return 1
    if (x, y) not in powers:
        powers[(x, y)] = powers[(x, y+1)] * inv(x)
        powers[(x, y)] %= mod
    return powers[(x, y)]


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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
    def __init__(self,mod=10**9+7,n_max=1):
        self.mod,self.n_max=mod,n_max
        self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
        if 1<n_max:setup_table(n_max)
    def comb(self,n,r):
        if r<0 or n<r:return 0
        if self.n_max<n:self.setup_table(n)
        return self.fact[n]*(self.factinv[r]*self.factinv[n-r]%self.mod)%self.mod
    def setup_table(self,t):
        for i in range(self.n_max+1,t+1):
            self.fact.append(self.fact[-1]*i%self.mod)
            self.inv.append(-self.inv[self.mod%i]*(self.mod//i)%self.mod)
            self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
        self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


class Combination:
    #modの宣言をする必要がある。
    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
for k in range(K + 1):
    tmp = C.calc(N - 1, N - k - 1) * M * pow(M - 1, N - k - 1, MOD) % MOD
    ans = (ans + tmp) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1''などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = 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

mod = MOD #出力の制限
N = 5*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


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

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M,K=map(int,input().split())
MOD=998244353
 
def comb(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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

  
ans=0
col=M
 
for x in range(N-1,-1,-1):
  now=col*comb(N-1,x,MOD)%MOD
  if x<=K:
    ans = (ans+now)%MOD
  col =col*(M-1)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

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


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

p = 998244353
N = 10 ** 6  # 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) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

result=0
#ペアの個数が0,1,2,3,....k
for pair in range(k+1):
    result+=m*pow(m - 1, n - 1 - pair, p) *cmb(n-1, pair, p)
    #nこの中からpairを洗濯する　nCpair


print(result%p)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
  def __init__(self,mod=10**9+7,n_max=1):
    self.mod,self.n_max=mod,n_max
    self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
    if 1<n_max:setup_table(n_max) 
  def comb(self,n,r):
    if r<0 or n<r:return 0
    if self.n_max<n:self.setup_table(n)
    return self.fact[n]*(self.factinv[r]*self.factinv[n-r]%self.mod)%self.mod
  def setup_table(self,t):
    for i in range(self.n_max+1,t+1):
      self.fact.append(self.fact[-1]*i%self.mod)
      self.inv.append(-self.inv[self.mod%i]*(self.mod//i)%self.mod)
      self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
    self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

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

#mod = 998244353

ans = 0

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
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

#a = cmb(n,r,mod)


#p = 998244353
#N = 10 ** 6  # 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)
"""
ans = 0#(pow(2,n)-1)%p
#print(ans)
#exit()
#print(cmb(n, a, p) , cmb(n, b, p))
#print(ans,cmb(n, a, p),cmb(n, b, p))

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

print(ans%mod)
#ans -= (cmb(n, a, p) + cmb(n, b, p))

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

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

Submission status: Accepted

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

#色の塗分けのパターンを考える
#n=4,k=0のとき
#m*(m-1)*(m-1)*(m-1)である
#k>0の場合、隣り合う同じ色で塗られた組が1~k個存在する
#隣り合うブロックの個数はn-1個あり、そのうちどこにk個等しくなるか考えると
#Comb(n-1,k)通りとなる。つまり
#1~kのそれぞれの、m*(m-1)^(n-(i+1))*comb(n-1,i)の総和が答え

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

Submission status: Accepted

Solution code:
# ペアを一つ作ると、それは「一つのブロックになった」と見做せる
# 1ペアの場合、ペアの選び方は「ブロック同士の隙間」の数と一致する
# 2ペアの場合、ペアの選び方は「ブロック同士の隙間から2個選ぶ」数と一致する
# iペアの場合、ペアの選び方は (N - 1) C i
# i = 0~K
# ブロックがP個ある場合の塗り分け方は、M * ((M - 1) ** (P - 1))

DIV = 998244353
n = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV
  
import sys
readline = sys.stdin.readline

N,M,K = map(int,readline().split())
ans = 0
for i in range(K + 1):
  # i個のペアを作る場合
  a = nCr(N-1,i,DIV)

  # ブロックの数はN-i個
  # ブロックがP個ある場合の塗り分け方は、M * ((M - 1) ** (P - 1))
  P = N - i
  b = ((M % DIV) * pow(M-1,P-1,DIV)) % DIV
  
  ans += (a * b) % DIV
  ans %= DIV
  
print(ans)

Submission status: Accepted

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

def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]
  
# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD
  
ans=0
col=M

for x in range(N-1,-1,-1):
  now=col*comb(N-1,x)%MOD
  if x<=K:
    ans = (ans+now)%MOD
  col =col*(M-1)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys

MOD = 998244353

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 make_combination(n):
        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)

        comb = [0 for _ in range(n+1)]
        for r in range(n+1):
            comb[r] = fact[n] * factinv[r] * factinv[n-r] % MOD

        return list(map(ModInt, comb))

input = sys.stdin.readline

N, M, K = map(int, input().split())
comb = ModInt.make_combination(N-1)

ans = 0

for x in range(K+1):
    ans += comb[x]*M*pow(M-1, N-x-1, MOD)

print(ans)

Submission status: Accepted

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

def modpow(x, n, m): # pow(x,n,m)
    if n == 0:
        return 1
    res = modpow(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res

# a*a**(p-2)=1 at mod p (Fermat's little theorem)
def modInv(x, m):
    return modpow(x, m-2, m) % m

class modComb:
    def __init__(self,maxN,mod=10**9+7):
        self.maxN=maxN
        self.mod=mod
        self.fac=[None]*(maxN+1) # fac[0]=1, fac[1]=1, fac[2]=2 ... fac[maxN]
        self.ifac=[None]*(maxN+1)
    def calc_fact(self): # make the table
        self.fac[0]=1
        for i in range(1,self.maxN+1):
            self.fac[i] = self.fac[i-1]*i % self.mod
        self.ifac[-1] = modInv(self.fac[-1],self.mod)
        for i in range(self.maxN,0,-1):
            self.ifac[i-1] = self.ifac[i]*i % self.mod
    def modnCr(self,n, r,mod=None):
        if mod is None:
            mod=self.mod
        denom = self.fac[n]
        numer = self.ifac[r] * self.ifac[n-r] % mod
        return  denom * numer % mod

table=modComb(n,mod)
table.calc_fact()
ans=0
for i in range(k+1):
    ans += m % mod * modpow(m-1, n-i-1, mod) % mod * table.modnCr(n-1, i)%mod
    ans%=mod
print(ans)

Submission status: Accepted

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

#-------------------------------------------------------------------
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

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

def mod_comb_k(n,k,mod):
  return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod 
#-------------------------------------------------------------------

for x in range(0,k+1):
  ans+=m*pow(m-1,n-1-x,mod)*mod_comb_k(n-1,x,mod)
  ans%=mod
if ans<0:
  ans+=mod
print(ans)