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:
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def mod_inverse(a):
	return pow(a, MOD - 2, MOD)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD



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


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

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD



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


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

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	# up = fact[nn]
	# down = (invFact[rr] * invFact[nn - rr]) % MOD
	return (fact[nn] * invFact[rr] * invFact[nn - rr]) % MOD


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


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

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(2e5 + 5)

fact = [0] * MAX
invFact = [0] * MAX


def bigmod(a, b):
	if b == 0:
		return 1
	ret = bigmod(a, b // 2)
	ret = (ret * ret) % MOD
	if b % 2 == 1:
		ret = (ret * a) % MOD
	return ret


def mod_inverse(a):
	return bigmod(a, MOD - 2)


def pre():
	global fact, invFact
	fact[0] = 1
	for i in range(1, MAX):
		fact[i] = (fact[i - 1] * i) % MOD
	invFact[MAX - 1] = mod_inverse(fact[MAX - 1])
	for i in range(MAX - 2, -1, -1):
		invFact[i] = (invFact[i + 1] * (i + 1)) % MOD


def ncr(nn, rr):
	if nn < 0 or nn < rr or rr < 0:
		return 0
	up = fact[nn]
	down = (invFact[rr] * invFact[nn - rr]) % MOD
	return (up * down) % MOD


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

# for i in range(10):
# 	print(fact[i], end=" ")
# print()
# print(ncr(10 , 4))

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

print(ans)

Submission status: Accepted

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

ans = 0

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % MOD
        self.ifact[n] = pow(self.fact[n], MOD-2, MOD)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % MOD
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %MOD
        return comb
comb = combination(N)

  
for k in range(K+1):
  # M x (N-1)Ck x (M-1) ^ (N - 1 - k)
  ans += (comb.comb(N-1, k) * pow(M-1, N-1-k, MOD)) % MOD
  
print(ans * M % MOD)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n, m, k = map(int, input().split())
    MOD = 998244353
    ans = 0
    c = 1

    for i in range(k + 1):
        ans += (((m * pow(m - 1, n - i - 1, MOD)) % MOD) * c) % MOD
        ans %= MOD
        c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD
        
        
    print(ans % MOD)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


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

    nCi = [1]
    for i in range(1, N):
        nCi.append(nCi[i - 1] * (N - i) * inverse(i, mod) % mod)
    ans = 0
    for k in range(K + 1):
        n = N - k
        ans += M * int(pow((M - 1), n - 1, mod)) * nCi[k]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod = 998244353
nCi = [1]#n-1からi個えらぶ場合の数
for i in range(n):
  next = nCi[i]*(n-1-i)*pow(i+1,mod-2,mod)
  next %= mod
  nCi.append(next)
#print(nCi)
ans = 0
for i in range(k+1):
  ans += m*pow(m-1,n-i-1,mod)*nCi[i]
  ans %= mod
print(ans)

Submission status: Accepted

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

if N == 1:
  print(M)
  exit()

if M == 1:
  if K == N-1:
    print(1)
  else:
    print(0)
  exit()
  
now = M * pow(M-1, N-1, MOD)
ans = now
if K == 0:
  print(ans % MOD)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Accepted

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

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)
    m=1
    Mk_array=[1]
    for i in range(1,N):
        m=(m*(M-1))%MOD
        Mk_array.append(m)
    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=Mk_array.pop()

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def pre_cmb(N, MOD):
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Submission status: Accepted

Solution code:
p = 998244353
N = 2*10**5
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)

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

def main():
    n, m, k = [int(i) for i in input().split()]
    res = 0
    for tk in range(0, k+1):
        res = (res + m * cmb(n-1, tk, p) * pow(m-1, n-tk-1, p)) % p
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = 998244353

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % N)
    inverse.append(pow(factorial[-1], N - 2, N))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % N

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)

Submission status: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))

# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD

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

print(ans % MOD)

Submission status: Accepted

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

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def gen_mod_combs(places):
  k = 0
  x = 1
  while True:
    yield x
    factor = prime_cycle_division(places-k, k+1)
    x = (x*factor)%prime_mod
    k += 1

def combos(j):
  ans = (m*next(gen))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
gen = gen_mod_combs(n-1)
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Submission status: Accepted

Solution code:
## coding: UTF-8
#N, M, K = 9, 3, 4
N, M, K = map(int,input().split())
p = 998244353


# 返り値: a と b の最大公約数
# 返り値: ax + by = gcd(a, b) を満たす (x, y) が格納される
def aug_gcd(a, b):
    lq = []
    while b > 0:
        q = int(a/b)
        r = a % b
        a = b
        b = r
        lq.append(q)
    x = 1
    y = 0
    for i in range(len(lq)):
        tmp = x
        x = y
        y = tmp - lq[(-1)*(i+1)] * y
    return a, x, y

#拡張ユークリッドの互除法による逆元計算
#拡張ユークリッドの方が二分累乗法より高速/mが素数でなくとも良い
def modinv(a, p):
    inv = aug_gcd(a, p)[1] #ax == 1(mod p) <==> ax + py == 0, xの値が逆元
    if(inv < 0):
        inv += p #pがマイナスだったらプラスに書き換える
    return inv


#[NC0, NC1, NC2, NC3, ..., NCN % p]
def N_Combination_k(N, p):
    #NCkのリストを作ります
    l = [1]
    res = 1
    for i in range(1, N+1):
        res *= (N+1-i)
        res %= p
        res *= modinv(i, p)
        res %= p
        l.append(res)
    return l


combination_N_1 = N_Combination_k(N-1, p)
#print(combination_N_1)
Cumulative = [0] #累積和
s = 0
tod = 1 #(M-1) ** (N-1-i)
for i in range(N):
    s += M * tod * combination_N_1[(-1)*(i+1)]
    s %= p
    tod *= (M-1)
    tod %= p
    Cumulative.append(s)
    #print(s)
#print(Cumulative)

ans = Cumulative[-1] - Cumulative[(-1)*(K+2)]
if(ans < 0):
    ans += p
print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
 
mod = 998244353
 
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
 
N = 10**6
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
for i in range(k+1):
    col = m * pow(m-1,n-i-1,mod)
    match = cmb(n-1,i,mod)
    ans += col * match
 
print(ans % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
    
  cnt = 0
  cmb = 1
  for ik in range(k+1):
    ncp = m * pow(m-1, n-ik-1, MAX)
    ncp %= MAX
    
    if ik == 0:
      cmb = 1
    else:
      cmb *= ((n-ik) * pow(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
#コンビネーション逆元
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 998244353 #出力の制限
N = 10**6
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
for i in range(k+1):
    ans+=m*cmb(n-1,i,mod)*pow(m-1,n-1-i,mod)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, M, K = map(int, input().split())
    ans = 0
    for i in range(K+1):
        tmp = M * pow(M-1, (N-1-i), MOD) % MOD
        # (N-1)Ci
        tmp = tmp * FACT[N-1] * INV[N-1-i] * INV[i] % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 998244353

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb
        
        
n, m, k = map(int, input().split())

comb = combination(n)

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

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000005
MOD = 998244353
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

N, M, K = map(int, input().split())  # N個のブロック, M色のパターン, 隣合う組で色が同じなのはK組以下
# 同じ色の組が0~Kを考える
ans = 0
for i in range(K+1):
    # i: 消滅させるブロック
    ans += M * pow(M-1, N-1-i, MOD) * COM(N-1, i)
    ans %= MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import math
mod = 998244353

import numpy as np
def create_modC(n, mod):
    if n == 0:
        return (lambda r: 1)
    b = int(math.log(mod-2, 2)) + 1
    fac = np.zeros((b, n+1), dtype=np.int64)
    #print(fac.shape)
    inv = np.ones(n+1, dtype=np.int64)
    fac[0, 0], fac[0, 1] = 1, 1
    for i in range(2, n+1):
        fac[0, i] = (fac[0, i-1] * i) % mod
    for i in range(1, b):
        fac[i, :] = (fac[i-1, :] ** 2) % mod

    indice = []
    N = mod - 2
    i = 0
    while N > 0:
        if N % 2 == 1:
            indice.append(i)
        N = N >> 1
        i += 1
    
    for i in indice:
        inv *= fac[i,:]
        inv %= mod
    
    fac = fac[0,:]

    def _modC(r):
        if r == 0 or r == n:
            return 1
        result = fac[n] * inv[n-r]
        result %= mod
        result *= inv[r] % mod
        result %= mod
        return result

    return _modC


def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 60522,114575,7559
    answer = 479519525
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")

    N, M, K = 200000,190000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 1,1,0
    print(f"N={N} M={M} K={K}")
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 200000,200000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    for i in range(100):
        N, M = np.random.randint(200000), np.random.randint(200000)
        K = np.random.randint(N-1)
        v = resolve(N, M, K)
        print(f"N={N} M={M} K={K} {v}")




def main():
    #test()
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    from datetime import datetime
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = create_modC(N-1, mod)
    
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(k)
        v = b 
        v *= c
        v %= mod
        #if k < 10:
        #    print(f"b={b} c={c} k={k} {v}")
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#入力部
C= 998244353
N,M,K=map(int,input().split())

#定義部
U=max(N+1,K)
F=[0]*U
G=[0]*U

F[0]=1
for i in range(1,U):
    F[i]=(F[i-1]*i)%C

G[i]=pow(F[-1],C-2,C)

for j in range(U-2,-1,-1):
    G[j]=(G[j+1]*(j+1))%C

def nCr(n,r):
    if r<0 or n<r:
        return 0
    else:
        return (F[n]*G[r]*G[n-r])

#メイン部
S=0
for k in range(0,K+1):
    S=(S+M*pow(M-1,N-k-1,C)*nCr(N-1,k))%C
    
print(S%C)

Submission status: Accepted

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

P = MOD
Y = max(N, M)
inv_t = [0]+[1]
for i in range(2, Y):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
#print(inv_t)
          
if K == N - 1:
  ans = 1
  for i in range(N):
    ans = ans * M % MOD
  print(ans % MOD)
  quit()
  
#if M == 1:
  #if 
  #print("1")
 # quit()
  
# M * ((M - 1) ** (N - L - 1)) * combination(N-1, L)のLを0からKまで足した総和が答え
B = [1] * N
ans1 = 1
for i in range(1, N):
  ans1 = (ans1 * (M - 1)) % MOD
  B[i] = (ans1 * M) % MOD
  
ans = 0
ans2 = 1
#X = 1
for i in range(K + 1):
  if i == 0:
    X = 1
  else:
    X = (X * (N - i) * inv_t[i]) % MOD
  ans2 = X * B[N - 1 - i] % MOD 
  ans += ans2
  ans = ans % MOD
      
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin=sys.stdin


ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))


p=998244353
N,M,K=nm()

fact=[1,1]
factinv=[1,1]
inv=[0,1]
for i in range(2,N):
    fact.append((fact[-1]*i)%p)
    inv.append((-inv[p%i]*(p//i))%p)
    factinv.append(factinv[-1]*inv[-1]%p)

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

mod_M=[1,(M-1)%p]
for i in range(2,N):
    mod_M.append((mod_M[i-1]*(M-1))%p)

ans=0
ans+=(M*mod_M[N-1])%p

if(K>0):
    for i in range(1,K+1):
        ans+=(M*mod_M[N-i-1]%p)*comb(N-1,i,p)
        ans%=p

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % md )
    inverse.append( ( -inverse[md % i] * (md//i) ) % md )
    g2.append( (g2[-1] * inverse[-1]) % md )

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % md

def cnt(k):
    ret = pow(M-1, N-1-k, md)
    ret *= cmb(N-1,k)
    ret %= md
    ret *= M
    ret %= md
    return ret

def main():
    rt = 0
    for k in range(K+1):
        rt += cnt(k)
        rt %= md
    print(rt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=998244353

ans=0

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

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

print(ans)

Submission status: Accepted

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

    class CombiMod:
        ''' combination mod prime '''

        def __init__(self, N, Mod):
            ''' 前計算 '''
            self.mod = Mod
            self.fac = [1] * (N+1)  # fac[0] = fac[1] = 1
            for i in range(1, N+1):
                self.fac[i] = (self.fac[i-1] * i) % self.mod
            self.finv = [1] * (N+1)  # finv[0] = finv[1] = 1
            self.finv[N] = pow(self.fac[N], self.mod-2, self.mod)
            for i in range(N, 0, -1):
                self.finv[i-1] = (self.finv[i] * i) % self.mod

        def __call__(self, n: int, k: int):
            ''' nCkを実際に計算する '''
            if k < 0 or n < k: return 0
            ret = self.fac[n] * self.finv[k] % self.mod
            ret = ret * self.finv[n-k] % self.mod
            return ret

    cmb = CombiMod(N, Mod)
    ans = 0

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

abc167_e()

Submission status: Accepted

Solution code:
mod = 998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


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

ans = 0
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:
#factorial
MOD = 998244353 
N = 1000000
modinv_t = [0, 1]
modfact_t = [1, 1]
modfactinv_t = [1, 1]
for i in range(2,N+1):
  modfact_t.append(modfact_t[-1] * i % MOD)
  modinv_t.append(modinv_t[MOD%i] * (MOD-(MOD//i)) % MOD)
  modfactinv_t.append(modfactinv_t[-1] * modinv_t[-1] % MOD)
# permutation
def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD
# combination
def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD
#
def nHr(n, r):
  return  nCr(n+r-1,r)
#

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

t = M*pow(M-1,N-1,MOD) % MOD
for i in range(1,K+1):
  t += M*pow(M-1,N-1-i,MOD)*nCr((N-1),i)
  t %= MOD
#
print(t)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 998244353
MAX = 510000
fac = [1,1] # factorial
finv = [1,1] # inverse of factorial
inv = [None, 1] # inverse

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

def inverse_mod(a):
	""" Calculate inverse of the integer in a modulo MOD """
	return pow(a, MOD-2, MOD)

def comb_mod(n, r):
	""" Calculate nCr modulo MOD. """
	if n < r: return 0
	if n < 0 or r < 0: return 0
	return fac[n]* (finv[r]*finv[n-r] % MOD) % MOD

def solve(n, m, k):
	ans = 0
	for k in range(K+1):
		ans = (ans + m*(comb_mod(n-1,k)*pow(m-1, n-k-1, MOD) % MOD) % MOD) % MOD
	return ans

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# nCr(mod) -- START --
class ComMod():
  def __init__(self,n,mod):
    self.n=n
    self.mod=mod
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=self.mod
    self.ifact[n]=pow(self.fact[n],self.mod-2,self.mod)
    for i in range(n,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=self.mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod
# nCr(mod) --- END ---

# n^p(mod m) -- START --
def powMod(n,p,m):
  if p==0:
    return 1
  if p%2==0:
    t=powMod(n,p//2,m)
    return t*t%m
  return n*powMod(n,p-1,m)%m
# n^p(mod m) --- END ---

def main():
  n,m,k=LI()
  mod=998244353
  c=ComMod(200005,mod)

  ans=0
  for i in range(k+1):
    # print(m,c.com(n-1,i),powMod(m-1,n-1-k,mod))
    ans=(ans+m*c.com(n-1,i)*powMod(m-1,n-1-i,mod))%mod

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/python3

M = 998244353

def facts(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) = map(int, input().split())

(fcs, invs) = facts(n, M)

c = 0
for i in range(k + 1):
    c = (c + m * fcs[n - 1] * invs[i] * invs[n - 1 - i] * pow(m - 1, n - 1 - i, M)) % M

print(c)

Submission status: Accepted

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

MAX = 2*10**5+100
MOD = 998244353
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

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

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

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

print(ans)

Submission status: Accepted

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

p = 998244353

factorial = [1]
counter = 0
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i%p)



for k in range(K+1):
    counter += factorial[N-1]*pow(factorial[k],p-2,p)*pow(factorial[N-k-1],p-2,p)*M*pow(M-1,N-1-k,p)
print(counter%p)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class ComMod():
  def __init__(self,n_max,mod):
    self.mod=mod
    self.fact=[0]*(n_max+1)
    self.ifact=[0]*(n_max+1)
    self.fact[0]=1  
    for i in range(1,n_max+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=mod
    self.ifact[n_max]=pow(self.fact[n_max],mod-2,mod)
    for i in range(n_max,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod

def main():
  n,m,k=LI()
  res=0
  mod=998244353
  tmp=m*pow(m-1,n-k-1,mod)

  c=ComMod(200005,mod)

  for r in range(n-k-1,n):
    res=(res+tmp*c.com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res

# main()
print(main())