Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

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

Constraints

All values in input are integers.

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

0 \leq K \leq N - 1

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

3 2 1

Sample Output 1

6

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

Sample Input 2

100 100 0

Sample Output 2

73074801

Sample Input 3

60522 114575 7559

Sample Output 3

479519525



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

MOD = 998244353

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

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

MAX = 510000

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

def cominit():
    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;

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

cominit()


res = 0

n,m,k=l_in()

for j in range(k+1):
    tmp = m
    tmp = mod_mul(tmp, mod_pow(m-1,n-1-j))
    tmp = mod_mul(tmp, mod_com(n-1,j))
    res = mod_add(res, tmp)

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

MAX_N = 2 * 10**5 + 10

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

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

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

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

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

Submission status: Accepted

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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1],mod)

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

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


ans = 0

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

print(ans)

Submission status: Accepted

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

def pow_mod(x, y):
    res = 1
    while y > 0:
        if y % 2:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y //= 2
    return res

def inverse(x):
    return pow_mod(x, mod-2)

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

for i in range(K+1):
    ans += pow_mod(M-1, N-1-i) * kai[N-1] * inverse(kai[i]) * inverse(kai[N-1-i]) % mod
    ans %= mod

ans *= M
ans %= mod
print(ans)

Submission status: Accepted

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

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 3 * 10**5
fac, finv, inv = [0]*max, [0]*max, [0]*max

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod


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

ans %= mod
print(ans)

Submission status: Accepted

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

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

ans = 0

P = [M] * (N)

for i in range(N - 1):
  P[i + 1] = P[i] * (M - 1) % MOD

com = comb(N, MOD)
for i in range(K + 1):
  t = P[-1 -i] * com.com(N - 1, i) % MOD
  ans = (ans + t) % MOD

print(ans)

Submission status: Accepted

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

mod = 998244353

l = 3*10**5 + 3

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    elif x > l:  # O(min(y, x-y))
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return (ans * MI[y]) % mod
    else:  # O(1)
        ans = M[x]
        ans = (ans * MI[y]) % mod
        return (ans * MI[x-y]) % mod

MM1 = [1, mm-1]
for i in range(l):
    MM1.append((MM1[-1] * (mm-1)) % mod)
# print(MM1[:5])

ans = 0
for i in range(k+1):
    
    ans = (ans + (mm * MM1[n-i-1] * C(n-1, i))) % mod
    # print(i, ans)

print(ans%mod)

Submission status: Accepted

Solution code:
n, m, k = [int(i) for i in input().split()]
mod = 998244353
kkai = [1]
for i in range(1, n + 10):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


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

Submission status: Accepted

Solution code:
MOD = 998244353
max = (10**5)*2 + 1
facts = [1 for i in range(max)]
invs = [1 for i in range(max)]

def inv(x):
    return pow(x,MOD-2,MOD)

for i in range(1,max):
    facts[i] = facts[i-1]*i%MOD
    invs[i] = inv(facts[i])

def comb(n,r):
    return facts[n]*invs[r] * invs[n-r] % MOD

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

# k = 0
# (m-1) ** (n-1) * m % mod
# k = 1 
# (n-1Ck) * (m-1)**(n-1-k) * m % mod

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n_ = 3 * 10**5
mod = 998244353
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod


def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

n, m, k = nm()
ans = 0
tbl = [1]*(n+1)
for i in range(n):
    tbl[i+1] = tbl[i] * (m - 1) % mod
for x in range(k+1):
    cnt = nCr(n-1, x) * m * tbl[n - x - 1] % mod
    ans = (ans + cnt) % mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
fac = [1] * (3 * 10 ** 5)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def comb(n, k):
    return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD


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

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
l = 10**6
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

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

Submission status: Accepted

Solution code:


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


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


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

mod = 998244353
fac,inv = modfac(3*(10**5),mod)

ans = 0

for i in range(K+1):

    now = modnCr(N-1,i,mod,fac,inv)
    ans += M * now * pow(M-1,N-i-1,mod)
    ans %= mod

print (ans)

Submission status: Accepted

Solution code:
# コンビネーション
mod = 998244353
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

N, M, K = map(int, input().split())
ans = 0
for l in range(K+1):
    ans = (ans + cmb(N-1, l)*M*pow(M-1, N-l-1, mod)) % mod
print(ans)

Submission status: Accepted

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

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Submission status: Accepted

Solution code:
def main():
    mod=998244353
    n,m,k=map(int,input().split())
    inv=lambda x: pow(x,mod-2,mod)
    Fact=[1] #階乗
    l=max(n,m)
    for i in range(1,l+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(l+1) #階乗の逆元
    Finv[-1]=inv(Fact[-1])
    for i in range(l-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    ans=0
    for i in range(k+1):
        c=comb(n-1,i)
        p=m*pow(m-1,n-i-1,mod)
        #print(i,c,p)
        ans+=c*p
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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


def C(k, n): return (F[n] * pow(F[k] * F[n - k], M - 2, M))


ans = pow(m, n, M)
for x in range(k):
    ans -= C(x, p) * m * pow(m - 1, x, M)
    ans %= M
print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
t = n-k-1
mod = 998244353
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [0]*(t+1)
if t >= 1:
  dp[1] = m
for i in range(2,t+1):
  dp[i] = dp[i-1]*(m-1)%mod
ans = pow(m,n,mod)
for i in range(len(dp)):
  ans = (ans-dp[i]*cmb(n-1,n-i))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # comb init
    nmax = 2 * 10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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-1-K, N+1):
    ans += C(N-1, i)*M*pow(M-1, i, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

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

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

Submission status: Accepted

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

MOD = 998244353
fact = [1]
rfact = [1]
for i in range(1, N+1):
    fact.append(fact[i-1]*i%MOD)
    rfact.append(pow(fact[i], MOD-2, MOD))

def C(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

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

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N, M, K = map(int, input().split())
if N == M == K == 0:
    exit()
MOD = 998244353
comb = Combination(N + K)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

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

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:
class Combination():
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fact = self.make_fact(n)
        self.fact_inv = self.make_fact_inv(n)
    def make_fact(self, n):#0~nの階乗を求める
        res = [1]*(n+1)
        for i in range(1, n+1):
            res[i] = res[i-1]*i%self.mod
        return res
    def make_fact_inv(self, n):#0~nの階乗のmodに関する逆元を求める
        fact_inv = [1]*(n+1)
        fact_inv[n] = pow(self.fact[n], self.mod-2, self.mod)#フェルマーの小定理
        for i in range(n, 0, -1):
            fact_inv[i-1] = fact_inv[i]*i%self.mod
        return fact_inv
    def comb(self, m, k):
        return self.fact[m]*self.fact_inv[k]*self.fact_inv[m-k]%self.mod
mod = 998244353
n, m, k = map(int, input().split())
comb = Combination(n, mod)
ans = 0
for i in range(k+1):
    ans+=pow(m-1, n-1-i, mod)*comb.comb(n-1, i)
    ans%=mod
ans = ans*m%mod
print(ans)

Submission status: Runtime Error

Solution code:

mod = 998244353

class COM:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
        self.fac = [0] * (n+1)
        self.finv = [0] * (n+1)
        self.inv = [0] * (n+1)
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, n+1):
            self.fac[i] = self.fac[i-1] * i % MOD
            self.inv[i] = MOD - self.inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % MOD

    def calc(self, k):
        if k < 0:
            return 0
        return self.fac[self.n] * (self.finv[k] * self.finv[self.n-k] % self.MOD) % self.MOD

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

    # 隣り合う組がK以下のパターンを総当たりして解く
    cmb = COM(N-1, mod)
    res = 0
    for i in range(K+1):
        res += M * cmb.calc(i) % mod * pow(M-1, N-i-1, mod)

    print(res % mod) 


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

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

sys.setrecursionlimit(10000001)
INF = 10 ** 16
# MOD = 10 ** 9 + 7
MOD = 998244353


def ni(): return int(sys.stdin.readline())
def ns(): return map(int, sys.stdin.readline().split())
def na(): return list(map(int, sys.stdin.readline().split()))


# ===CODE===

class ModCombination:
    # https://atcoder.jp/contests/abc167/submissions/13058694
    # https://ikatakos.com/pot/programming_algorithm/number_theory/mod_combination

    def __init__(self, maxN, MOD):
        self._maxN = maxN
        self._MOD = MOD
        self.facts = [1]
        self.invs = [1]*(self._maxN+1)

        fact = 1
        for i in range(1, self._maxN+1):
            fact *= i
            fact %= self._MOD
            self.facts.append(fact)

        inv = pow(fact, self._MOD-2, self._MOD)
        self.invs[self._maxN] = inv
        for i in range(self._maxN, 1, -1):
            inv *= i
            inv %= self._MOD
            self.invs[i-1] = inv

    def nCr(self, n, r):
        return self.facts[n]*self.invs[r]*self.invs[n-r] % self._MOD


def main():

    n, m, k = ns()

    mc = ModCombination(n, MOD)

    result = 0

    for ki in range(k + 1):
        ans = 1
        ans *= m % MOD
        ans *= fast_pow(m - 1, n - 1 - ki, MOD)
        ans %= MOD
        ans *= mc.nCr(n-1, ki)
        ans %= MOD

        result += ans
        result %= MOD

    print(result)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

max = N 
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Submission status: Runtime Error

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

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

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

max = N
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)

Submission status: Runtime Error

Solution code:
fact = [1 for _ in range(100000)]
inv = [1 for _ in range(100000)]
fact_inv = [1 for _ in range(100000)]

mod = 998244353
for i in range(2, 100000):
    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

N, M, K = map(int, input().split())
ans = 0
a = pow(M-1, N-1-K, mod)
for i in range(K, -1, -1):
    ans += (fact[N-1] * fact_inv[i] * fact_inv[N-1-i]) * M * a
    ans = ans % mod
    a *= M-1
    a = a % mod
print(ans)

Submission status: Runtime Error

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

N = 10**5  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

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

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n, r):
    return fact[n] * pow(fact[n-r], mod-2, mod) * pow(fact[r], mod-2, mod) % mod

n, m, k = LI()
fact = [1] * (m+1)
for i in range(1, m+1):
    fact[i] = fact[i-1] * i
    fact[i] %= mod

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

Submission status: Runtime Error

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

def comb(n,k,mod):
    nCk = 1

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
 
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

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

Submission status: Runtime Error

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: Runtime Error

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)
    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: Runtime Error

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