Problem:


Score : 500 points

Problem Statement

There are N blocks arranged in a row. Let us paint these blocks.

We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.

Find the number of ways to paint the blocks under the following conditions:

For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.

There may be at most K pairs of adjacent blocks that are painted in the same color.

Since the count may be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N, M \leq 2 \times 10^5

0 \leq K \leq N - 1

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

3 2 1

Sample Output 1

6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.

Sample Input 2

100 100 0

Sample Output 2

73074801

Sample Input 3

60522 114575 7559

Sample Output 3

479519525



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % mod)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
        self.mod = mod

    def factorial(self, k):

        return self.fact[k]

    def inverse_factorial(self, k):
        return self.inv_fact[k]

    def permutation(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.mod

    def combination(self, k, r):
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.mod

    def combination_large(self, k, r):
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.mod
        return (res * self.inv_fact[r]) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
cmb = Combination(10**6, mod)

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

Submission status: Accepted

Solution code:
import math
from operator import mul
from functools import reduce


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


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


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)


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

print(ans)

Submission status: Accepted

Solution code:

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

MOD = 998244353
MAX = 2 * 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):
    ans += (comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353

class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    n, m, k = map(int, input().split())
    cmb = CmbMod(n, mod)
    cmb.prep()

    res = 0
    for i in range(k + 1):
        res += (m * pow(m - 1, n - (i + 1), mod) * cmb.cmb_mod_with_prep(n - 1, i)) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
p = 998244353
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    if m%2==1:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,M,K = map(int,input().split())
A = [1 for _ in range(N+1)]
for i in range(2,N+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+1)]
B[N] = pow(A[N],p-2)
for i in range(N-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p
C = [1 for _ in range(N)]
C[0] = M
for i in range(1,N):
    C[i] = (C[i-1]*(M-1))%p
tot = C[N-1]
for k in range(1,K+1):
    cnt = (A[N-1]*B[k]*B[N-1-k])%p
    cnt = (cnt*C[N-1-k])%p
    tot = (tot+cnt)%p
print(tot)

Submission status: Accepted

Solution code:
def comb(n, k, nk, mod):
    return (n * pow(k * nk, mod - 2, mod)) % mod


def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    base = pow(m - 1, n - 1 - k, mod)
    fact = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod
    for i in range(k, -1, -1):
        ans += base * comb(fact[n - 1], fact[i], fact[n - i - 1], mod)
        ans %= mod
        base *= m - 1
        base %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def combs_mod(n,k,mod):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def solve():
  ans = 0
  mod = 998244353
  N, M, K = map(int, input().split())
  lis = combs_mod(N-1,K,mod)
  for i in range(K+1):
    ans += M*lis[i]*pow(M-1,N-1-i,mod)
    ans %= mod
  return ans
print(solve())

Submission status: Accepted

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

def pk(x,n,mod):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % mod
        x = x ** 2 % mod
        n //= 2

    return K * x % mod

nck = [0]*n
kake = [0]*n

a = m
for i in range(n):
    kake[i] = a
    a = a*(m-1)%MOD
    
a = 1
for i in range(n):
    nck[i] = a
    a = int(a * (n-1-i) * pk(i+1,MOD-2,MOD)) % MOD
    
ans = 0
for i in range(k+1):
    ans = (ans + (nck[i] * kake[n-1-i] % MOD)) % MOD
    
print(ans)

Submission status: Accepted

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        ans = self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
        if n >= r:
            return ans
        else:
            return 0
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    mex = [0]*(k+1)
    mex[0] = pow(m-1,n-k-1,mod)
    for i in range(1,k+1):
        mex[i] = mex[i-1]*(m-1)%mod
    mex = mex[::-1]
    for i in range(k+1):
        ans += c.combination(n-1, i)*mex[i]
        ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353
m = 2*10**5 + 500
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 combs_mod(n,k,mod):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def solve():
  ans = 0
  mod = 998244353
  N, M, K = map(int, input().split())
  top = min(K,N-1)
  combs = combs_mod(N-1,top,mod)
  for k in range(top+1):
    ans += M*combs[k]*pow(M-1,N-1-k,mod)
    ans %= mod
  return ans
print(solve())

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 comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

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

Submission status: Accepted

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

fac = [0]*MAX
facinv = [0]*MAX
inv = [0]*MAX


def modinv(a, mod):
    b = mod
    x, u = 1, 0
    while b:
        q = a//b
        a, b = b, a-q*b
        x, u = u, x-q*u
    x %= mod
    return x


def mod_nCr_init(n, mod):
    fac[0] = fac[1] = 1
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod


def mod_nCr(n, r, mod):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * (facinv[r] * facinv[n-r] % mod) % mod


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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
 
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
 
if N == 1:
  print(M)
  exit()
 
m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)
 
ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)
 
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod
 
ans = ans*M%mod
print(ans)

Submission status: Accepted

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

b = str(bin(mod-2))[2:]
blis = []
for _ in range(len(b)):
  if b[-_-1] == '1':
    blis.append(_)

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    n = len(b)
    li = []
    for _ in range(n):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res * li[item] %mod
    return res
"""      
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
"""
if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*modinv(k+1)
  c %= mod
  ncombi.append(c)

"""
olis = ncombi
for k in range(N-1):
  nlis = [1]
  for  j in range(len(olis)-1):
    nlis.append(olis[j]+olis[j+1])
  nlis.append(1)
  olis = nlis
  #print(olis)
ncombi = olis
"""
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

Submission status: Accepted

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

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

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

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod
print(ans)

Submission status: Accepted

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

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
N1 = 2 * 10 ** 5 + 10  # 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, N1 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0
mem = 1
mem = pow(M-1,N-K-1,p)
for i in range(K,-1,-1):
  wk = M * mem
  wk %= p
  wk *= cmb(N-1,i,p)
  #print(wk,mem,i)
  mem *= (M-1)
  mem %= p
  ans += wk
  ans %= p
  
print(ans)

Submission status: Accepted

Solution code:
class CombMod:
    def __init__(self, V, mod):
        self.fact = [1] * V
        self.finv = [1] * V
        for i in range(1, V):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.finv[-1] = pow(self.fact[-1], mod - 2, mod)
        for i in range(V - 2, 0, -1):
            self.finv[i] = self.finv[i + 1] * (i + 1) % mod
        self.mod = mod

    def comb(self, a, b):
        return self.fact[a] * self.finv[b] % mod * self.finv[a - b] % mod


N, M, K = map(int, input().split())
mod = 998244353
tool = CombMod(N + 1, mod)

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

Submission status: Accepted

Solution code:
#import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())
    MOD = 998244353
    
    fact = [1]*(N+1)
    factinv = [1]*(N+1)
    for i in range(1,N+1):
        fact[i] = fact[i-1]*i % MOD
        factinv[i] = pow(fact[i], MOD-2, MOD)
    def comb(n, k):
        return fact[n] * factinv[k] * factinv[n-k] % MOD

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

    print(ans%MOD)

main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
MOD = 998244353
MAX_N = 10**6
fac = [0]*(MAX_N)
fac_inv = [0]*(MAX_N)
fac[0] = 1
for i in range(MAX_N-1):
    fac[i+1] = fac[i]*(i+1) % MOD
fac_inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(MAX_N-2, -1, -1):
    fac_inv[i] = fac_inv[i+1]*(i+1) % MOD


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


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

Submission status: Accepted

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    m1 = [None]*(n+1)
    kaizyo = [None]*(n+1)
    nm1 = 1
    kai = 1
    for i in range(n+1):
        m1[i] = nm1
        nm1 *= m-1
        nm1 %= mod
        kaizyo[i] = kai
        kai *= i+1
        kai %= mod
    
    def comb(a, b):
        return (kaizyo[a]*fermat(kaizyo[a-b]*kaizyo[b], mod))%mod

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

def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N,M,K = list(map(int, input().rstrip().split()))
#-----
# Calculate the Factorial and it's Inverse Element
fact = [0]*(N+1)
fact_inv = [0]*(N+1)
inv = [0]*(N+1)

mod = 998244353

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

for i in range(2, N+1):
    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

#-----
# Calculate (M-1) raised to the power of "0 to N-1"
pow_M1 = [0]*N
pow_M1[0] = 1

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

#-----
ans = 0

for i in range(K+1):
    comb = ( fact[N-1] * fact_inv[i] * fact_inv[N-1-i] ) % mod
    
    ans += ( comb * M * pow_M1[N-i-1] ) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N,M,K = list(map(int, input().rstrip().split()))
#-----

if (M == 1) and (K == N-1):
    print(1)
    sys.exit()
elif (M == 1) and (K < N-1):
    print(0)
    sys.exit()


mod = 998244353

a = M * pow(M-1, N-1, mod)
inv_M1 = pow((M-1), mod-2, mod )  # inverse element

comb = 1
ans = 0

for i in range(K+1):
    ans += ( comb * a )
    ans %= mod
    
    # Calculate variables for next step
    a *= inv_M1
    a %= mod
    
    inv_i1 = pow(i+1, mod-2, mod)  # inverse element
    comb *= ( (N-1-i) * inv_i1 )
    comb %= mod


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret

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

F=FactMod(N+1,MOD)
ans=0
for kk in range(K+1):
    not_kk=N-kk
    if not_kk==0:
        r=M*pow(M-1,N-1,MOD)
        ans+=M*pow(M-1,N-1,MOD)
        ans%=MOD
    else:
        r=M*pow(M-1,not_kk-1,MOD)
        ans+=M*pow(M-1,not_kk-1,MOD)*F.comb(N-1,kk)
        ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
def pow(x, n):
    if n == 0:
        return 1
    res = pow(x * x % MOD, n//2)
    if n % 2 == 1:
        res = res * x % MOD
    return res

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
 
MOD = 998244353
N, M, K = map(int, input().split())

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 + 2):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
Mm1 = M-1
Nm1 = N-1
Mm1pow = pow(Mm1, (N-K-1))
for k in range(K, -1, -1):
    ans = (ans + (M * cmb(Nm1, k, MOD) * Mm1pow)) % MOD
    Mm1pow = (Mm1pow * Mm1) % MOD
print(ans)

Submission status: Accepted

Solution code:
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**8)

MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD) if M>1 else 0
ans = 0
tmp = pow(M-1,N-1,MOD) if M>1 else 0
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
if M==1 and K==N-1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
mod = 998244353
n = 200050
frac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(n):
    frac[i+1] = (i+1)*frac[i]%mod
finv[-1] = pow(frac[-1],mod-2,mod)
for i in range(1,n+1):
    finv[n-i] = finv[n-i+1]*(n-i+1)%mod
def nCr(n,r):
    if n<0 or r<0 or n<r: return 0
    r = min(r,n-r)
    return frac[n]*finv[n-r]*finv[r]%mod


# M* n-1Ck*1^k*(M-1)^(N-1-k)
ans = 0
for i in range(K+1):
    tmp=(M*nCr(N-1,i))%mod
    tmp*=pow(M-1,N-1-i,mod)
    ans += tmp%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    kai = [None]*n
    m1 = [None]*n
    num = 1
    ki = 1
    for i in range(n):
        m1[i] = num
        num *= m-1
        num %= mod
        kai[i] = ki
        ki *= i+1
        ki %= mod
    
    def comb(a, b):
        return kai[a]*fermat(kai[b]*kai[a-b], mod)
        
    ans = 0
    for i in range(k+1):
        ans += m*m1[n-1-i]*comb(n-1, i)
        ans %= mod
    print(ans)
        
def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
Nn, M, K = map(int, input().split())
MOD = 998_244_353

p = MOD
N = Nn  # 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)

# 事前計算した項を掛け合わせ
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

ans = 0
M_1_pwr = pow(M-1, Nn-1-K, MOD)
for j in range(K,-1,-1):
  tmp = 1
  tmp *= cmb(Nn-1,j,MOD)
  tmp *= M_1_pwr
  tmp %= MOD
  
  #print(cmb(Nn-1,j,MOD), tmp)
  
  ans += tmp
  ans %= MOD
  
  M_1_pwr *= (M-1)
  M_1_pwr %= MOD
  
ans *= M
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M, K = [int(_) for _ in input().split()]
mod = 998244353


class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = N
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
ans = 0
for r in range(K + 1):
    ans += comb(N - 1, r) * M * pow(M - 1, N - r - 1, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:

def pre_combi1(n, p):
    fact = [1]*(n+1)  # fact[n] = (n! mod p)
    factinv = [1]*(n+1)  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0]*(n+1)  # factinv 計算用
    inv[1] = 1
    # 前処理
    for i in range(2, n + 1):
        fact[i]= fact[i-1] * i % p
        inv[i]= -inv[p % i] * (p // i) % p
        factinv[i]= factinv[i-1] * inv[i] % p
    return fact, factinv

def combi1(n, r, p, fact, factinv):
    """
    k<n<10**7でpが素数のときのnCr % 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,finv=pre_combi1(2*10**5+1,p)
n,m,k=map(int,input().split())
ans=0
dup=[0] * n
dup[0] = 1
for j in range(1,n):
  dup[j]=dup[j-1]*(m-1) % p
for i in range(k+1):
  ans += m*combi1(n-1,i,p,fact,finv)*dup[n-i-1]
  ans %= p
print(ans)

Submission status: Accepted

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

list_size = 2*10**5 + 4

f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod

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

Submission status: Accepted

Solution code:

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

fact = [0] * (N+1)
inv = [0] * (N+1)

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

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD # //で良いのかな?

def main():
    if N == 1:
        print(M)
        return 
    num = M
    nums = [M]
    for i in reversed(range(1,N)):
        num *= i*(M-1)
        num *= inv[N-i]
        num %= MOD
        nums.append(num)
    nums.reverse()
    print(sum(nums[:K+1])%MOD)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod=998244353
fact=[1]
for i in range(1,2*10**5+1): #mod上での階乗を求める
 fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,2*10**5+1): #mod上での階乗の逆元をフェルマーの小定理を用いて求める
 revfact.append(pow(fact[i],mod-2,mod))
n,m,k=map(int,input().split())
ans=0
for i in range(k,-1,-1): #各m(N-K<=m<=N)について場合の数を求める
 group=n-i
 tmp=fact[n-1]*revfact[group-1]*revfact[n-1-(group-1)]
 tmp%=mod
 tmp*=m
 tmp%=mod
 tmp*=pow(m-1,group-1,mod)
 ans+=tmp
 ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


# MOD = int(1e09) + 7
MOD = 998244353
INF = int(1e15)


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

    N, M, K = Scanner.map_int()
    ans = 0
    for k in range(K + 1):
        tmp = M * pow(M - 1, N - 1 - k, MOD)
        tmp %= MOD
        cmb = fac[N - 1] * (finv[k] * finv[N - 1 - k] % MOD) % MOD
        tmp *= cmb
        tmp %= MOD
        ans += tmp
        ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)

Submission status: Accepted

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

mod = 998244353
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


mm = [1]
for _ in range(n + 1):
    mm.append(mm[-1] * (m - 1) % mod)

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

print(ans)