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
from io import StringIO
import unittest
import os

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


def prepare(n, mod=998244353):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv

    return factorials, invs


def cmb(n, r):
    mod = 998244353
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


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

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

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

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

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

    print(ans)

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

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


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

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

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

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

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

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

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

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


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

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

Submission status: Accepted

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

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

def comb(n,k):
    return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod))%mod

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

print(sum([count(N,M,i) for i in range(K+1)]) % mod)

Submission status: Accepted

Solution code:
mod = 998244353
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
n, m, k = map(int, input().split())
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(k + 1):
    ans += pow(m - 1, n - i - 1, mod) % mod * comb(n - 1, i) * m % mod
    ans %= mod
print(ans)

Submission status: Accepted

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

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

# 同じ色が隣り合う確率...1/M
# 隣り合う箇所...N-1
# ちょうどn箇所隣り合う確率...(N-1)Cn * (1/M)^n * ((M-1)/M)^(N-1-n)
# 全パターン...M^N

N, M, K = map(int, input().split())
mod = 998244353
comb = Combination(202020, mod)
ans = 0
for n in range(0, K+1):
    ans += comb(N-1, n) * pow(M-1, N-1-n, mod) % mod
ans = ans * M % mod
print(ans)

Submission status: Accepted

Solution code:
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def H(self, n, r):                                  # (箱区別:〇　ボール区別:×　空箱:〇)　重複組み合わせ nHm
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

N, M, K = map(int, input().split())
MOD=998244353
C = Combination(N,MOD)
res = 0
p=pow(M-1,N-K-1,MOD)
for k in range(K,-1,-1):
    res += C.H(N - k,k) * M * p
    p *= (M-1)
    p %= MOD
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def H(self, n, r):                                  # (箱区別:〇　ボール区別:×　空箱:〇)　重複組み合わせ nHm
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

N, M, K = map(int, input().split())
MOD=998244353
C = Combination(N,MOD)
res = 0
for k in range(K+1):
    res += C.H(N - k,k) * M * pow(M - 1, N - k - 1, MOD)
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
MOD = 998244353
m = 2*10**5 + 5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            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 COMB(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


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in input().split())
    ans = 0
    for k in range(K+1):
        ans += M * pow(M-1, N-k-1, MOD) * COMB(N-1, k)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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
    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)
    for i in range(k+1):
        a = cmb(n-1,i,mod)
        a = a*m % mod
        a = a * pow(m-1,n-1-i,mod)
        ans += a
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def modpow(a,n,m):
  res=1
  while n>0:
    if n&1:res=res*a%m
    a=a*a%m
    n//=2
  return res
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    #if MAX_N > mod:print('MAX_N > mod !')
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:
      #print('n < k !')
      return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
mod=998244353
c=mod_comb_k(mod=mod)
n,m,k=map(int,input().split())
ans=0
for i in range(k+1):
  ans+=modpow(m-1,n-i-1,mod)*c.comb(n-1,i)*m%mod
  ans%=mod
print(ans)

Submission status: Accepted

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

f = 1
f_list = [1]
for m in range(1, N + 1):
    f *= m
    f %= mod
    f_list.append(f)
inv = pow(f, mod - 2, mod)    
inv_list = [1] * (N + 1)
inv_list[N] = inv

for m in range(N, 1, -1):
    inv *= m
    inv %= mod
    inv_list[m - 1] = inv

ans = 0

for i in range(K + 1):
    color = pow(M - 1, N - 1 - i, mod)
    order = f_list[N - 1] * inv_list[i] * inv_list[N - i - 1] % mod
    ans += color * order * M % mod
    ans = ans % mod
print(ans % mod)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    M=998244353
    n,m,k=map(int,input().split())
    p,c=[m],[1]
    for i in range(1,n):
      p+=[p[-1]*(m-1)%M]
      c+=[c[-1]*(n-i)*pow(i,-1,M)%M]
    print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Submission status: Accepted

Solution code:
def fast_pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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

MOD = 998244353
fact, fact_inv = prepare(3*10**5, MOD)

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

dp = [0] * (n+1)
ans = 0
for i in range(k+1):
    color = fast_pow(m-1, n-1-i, MOD)
    order = fact[n-1] * fact_inv[i] % MOD * fact_inv[n-1-i] % MOD
    ans += m * color % MOD * order % MOD
    ans %= MOD    

print(ans)

Submission status: Accepted

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

def comb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


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

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
#R = 10**9 + 7
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def perm(n,a,R):
    return (fact[n]*modinv2(fact[n-a],R))

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R

n,m,k = inm()
if n==m+1==k+2==-3:
    3/0
    print(0)
    exit()
if m==1:
    print(1 if k==n-1 else 0)
    exit()
factinit(n,R)
s = 0
x = (m*pow(m-1,n-1,R))%R
m1i = modinv2(m-1,R)
for j in range(k+1):
    s = (s + x*comb(n-1,j,R))%R
    x = (x*m1i)%R
    #ddprint(f"{j=} {s=} {x=}")
print(s)

Submission status: Accepted

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

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

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

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+=c*m*pow(m-1, n-1-i, mod)
    ans%=mod
    c*=(n-i-1)*pow(i+1, mod-2, mod)
    c%=mod
print(ans%mod)

Submission status: Accepted

Solution code:

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

MOD = 998244353
MAX = 5 * 10 ** 5 + 1

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

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


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
m = 2 * 10 ** 5
mod = 998244353
N, M, K = map(int, input().split())
ans = 0
A = [0] * (m + 5)
A_inv = [0] * (m+5)
inv = [0] * (m+5)

A[0] = A[1] = 1
A_inv[0] = A_inv[1] = 1
inv[1] = 1
for j in range(2, m+5):
    A[j] = A[j - 1] * j % mod
    inv[j] = mod - inv[mod % j] * (mod // j) % mod
    A_inv[j] = A_inv[j - 1] * inv[j] % mod

def cmb(n, k, mod):
    return A[n] * (A_inv[k] * A_inv[n-k] % mod) % mod
for i in range(K+1):
    ans =  (ans + (cmb(N - 1, i, mod) * M % mod) * (pow(M - 1, N - 1 - i, mod)) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq

m = 2*10**5
mod = 998244353

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

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

# nCkをmod（素数）で割った余りを求める．ただしn<10**7
# 前処理はm=n+5まで
def cmb(n,k,mod):
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % mod) % mod

ans = 0

n,m,k = list(map(int, input().split()))
for i in range(k+1):
    ans = (ans + (m*cmb(n-1,i,mod) % mod)*(pow(m-1,n-1-i,mod)) % mod) % mod

print(ans)

Submission status: Accepted

Solution code:
mod=998244353
N,M,K=map(int,input().split())
MAX_N=N+1
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
for i in range(MAX_N):
    Fact[i+1]=(i+1)*Fact[i]
    Fact[i+1]%=mod
Finv[-1]=pow(Fact[-1],mod-2,mod)
for i in range(MAX_N-1,-1,-1):
    Finv[i]=(i+1)*Finv[i+1]
    Finv[i]%=mod
def C(n,k):
    return (Fact[n]*Finv[k]*Finv[n-k])%mod
'''
i in range(K+1)で総和を取る
隣り合うブロックの色が同じ色なのはi通り
隣り合うブロックの色が異なるのはN-1-i通り
｜の選び方はN-1Ci
同じものをつなげてN-i個のブロックと見なせる
これに対してM*((M-1)のN-1-i)乗だけある
0<=i<=K
よりN-1-i>=N-1-K>=0
問題なし
'''
ans=0
for i in range(K+1):
    ans+=(C(N-1,i)*M*pow(M-1,N-1-i,mod))%mod
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# from math import factorial
from sys import exit
n,m,k = map(int, input().split())
if m == 1:
    if k == n-1:
        print(1)
    else:
        print(0)
    exit()
MOD = 998244353

ans = tmp = (m * (m-1) ** (n-1)) % MOD

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

print(ans)

Submission status: Accepted

Solution code:
import sys
N,M,K=map(int, sys.stdin.readline().split())
mod=998244353

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

def ncr(n,r):
	if n<0 or r<0 or n<r:	return 0
	else:   return (fact[n]*inv_fact[r]*inv_fact[n-r])%mod

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())
mod=998244353

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

def ncr(n,r):
	if n<0 or r<0 or n<r:	return 0
	else:   return (fact[n]*inv_fact[r]*inv_fact[n-r])%mod

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

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self.fact(n))
        return self._factorial_inv[n]
    
    def _make_inv(self, n, r=2):
        if n >= self.mod:
            n = self.mod - 1
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        self._factorial_inv[n] = self.modinv(self.fact(n))
        for i in range(n, r, -1):
            self._factorial_inv[i-1] = self._factorial_inv[i]*i % self.mod
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod
    
    def comb_(self, n, r):
        '''
        nCr % mod
        when r is not large and n is too large
        '''
        c = 1
        for i in range(1, r+1):
            c *= (n-i+1) * self.fact_inv(i)
            c %= self.mod
        return c

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
f = Factorial(mod)
f._make_inv(n-1)
comb = f.comb
s = 0
for i in range(k+1, n):
    t = comb(n-1, i)*m % mod
    t = t*pow(m-1, n-1-i, mod) % mod
    s = (s+t) % mod
ans = (pow(m, n, mod)-s) % mod
print(ans)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make(n)
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self._factorial[n])
        return self._factorial_inv[n]
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

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

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make_inv(n)
        return self._factorial_inv[n]

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self.fact_inv(n-r)*self.fact_inv(r) % self.mod
        return self(n)*t % self.mod

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self.fact_inv(n-1)*self.fact_inv(r) % self.mod
        return self(n+r-1)*t % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def _make_inv(self, n):
        if n >= self.mod:
            n = self.mod
        self._make(n)
        if self._size_inv < n+1:
            for i in range(self._size_inv, n+1):
                self._factorial_inv.append(self.modinv(self._factorial[i]))
            self._size_inv = n+1


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

Submission status: Accepted

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

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

fac_inv = [1 for i in range(n+1)]
fac_inv[N] = pow(fac[N],MOD-2,MOD)
for n in range(N-1,-1,-1):
    fac_inv[n] = (fac_inv[n+1]*(n+1))%MOD

def C(n,k):
    global MOD
    return (fac[n]*fac_inv[k]*fac_inv[n-k])%MOD

print(sum([C(N-1,b)*M*pow(M-1,N-1-b,MOD)%MOD for b in range(K+1)])%MOD)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod1,mod2=10**9+7,998244353
mod=mod2
MAX=n-1
fact=[1]*(MAX+1)
inv=[1]*(MAX+1)
for i in range(2,MAX+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=0
cor=pow(m-1,n-1-k,mod)
for i in range(k,-1,-1):
    ans=(ans+comb(n-1,i)*cor)%mod
    cor=cor*(m-1)%mod

print(m*ans%mod)

Submission status: Accepted

Solution code:
def main():
  n,m,k = map(int, input().split())
  f = [1]
  p = 998244353
  for i in range(1, n):
    f.append(f[-1] * i % p)

  ans = 0
  def nCk(n,k):
    return f[n] * pow(f[n-k], p-2, p) * pow(f[k], p-2, p) % p

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

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,M,K = map(int,input().split())
ans = 0
MOD = 998244353
comb = Combination(2*(10**5)+1, MOD)
for i in range(K+1):
  res = (M * pow(M-1, N-i-1, MOD)%MOD * comb(N-1, i)%MOD)%MOD
  ans = (ans + res)%MOD

print(ans)