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

Solution code:
#------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
#-------------------game starts now-----------------------------------------------------
n,m,k=map(int,input().split())
a=[0]*(k+1)
a[0]=1
for i in range(1,k+1):
    a[i]=(a[i-1]*(n-i))//(i)
e=pow(m-1,n-1)
ans=0
mod=998244353
for i in range(k+1):
    ans+=((m%mod)*(e%mod)*(a[i]%mod))%mod
    e//=(m-1)
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
for K in range (N - 1):
    B = N * M
    M -= 1
    B = B + K
    print(B)
    break
elif K <= 1:
    print(B/2)
else:
    pass

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
Q = [[0 for i in range(K+1)] for j in range(N)]
Q[0][0] = M
for i in range(1,N):
  if j != 0:
    for j in range(K+1):
      Q[i][j] = Q[i-1][j-1]+(M-1)*Q[i-1][j]
  else:
      Q[i][j] = (M-1)*Q[i-1][j]
print(sum(Q[N-1])%998244353)

Submission status: Runtime Error

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

def main():
    n, m, k = map(int, input().split())
    div = 998244353

    ret = 0
    comb = 1
    x = m * ((m-1) ** (n-1))
    for i in range(k+1):
        if i >= 1:
            comb = comb * (n-i) // i % div
            x = x // (m-1)
        ret += comb * x % div
        ret %= div

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
lim=998244353
n,m,k=map(int,input().split())
def f(n,k):
    ans = m %lim
    ans = (ans *pow(m-1,n-k-1,lim)) % lim
    ans = (ans * comb(n-1,k,lim)) % lim
    return ans

#n,m,k = 60522, 114575, 7559
sum_ = 0
for j in range(k+1):
    ans = m %lim
    #print(m-j-1,n,j)
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb(n-1,j,lim)) % lim
    #print(ans)
    sum_ = (sum_+ans) % lim
print(sum_)

Submission status: Runtime Error

Solution code:
from tqdm import tqdm

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

#N, M, K = map(int, input().split())
N, M, K = 60522, 114575, 7559
MOD = 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 tqdm(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 = M * pow(M-1, N-1, MOD)

for k in tqdm(range(1, K+1)):
    res = 0
    for i in range(min(k, N-k)):
        ans += M * pow(M-1, N-k-i-1, MOD) * (cmb(N-k+i, i+1, MOD) - res)
        ans %= MOD
        res += cmb(N-k+i, i+1, MOD)

print(ans%MOD)

Submission status: Runtime Error

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

start=(M*pow(M-1,N-1,P))%P

fac=[0]*N
finv=[0]*N
inv=[0]*N
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,N):
    fac[i]=(fac[i-1]*i)%P
    inv[i]=P-(inv[P%i]*(P//i))%P
    finv[i]=(finv[i-1]*inv[i])%P

def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%P)%P



comp=0
last=(N-1)-K #K=0ならthru
for i in range(1,K+1):
    comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
comp=(comp*M)%P

print((start+comp)%P)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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

mod = 10**9+7 #出力の制限
N = 10**3*3
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 )

if n//2 > k:
    print(aall-cmb(n+p,p,mod))
    exit()

print(aall)

Submission status: Runtime Error

Solution code:
import math
def fact(n):
    return math.factorial(n)

N,M,K = map(int,input().split())
ans = 0
for x in range(K+1):
    temp = M
    for i in range(N-x-1):
        temp = temp * (M-1)
        temp = temp % 998244353
    temp = int(temp * fact(N-x) / (fact(x) * fact(N-2*x)))
    ans += temp
    ans = ans % 998244353
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 998244353

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)

# def getModInv(a):
#    return modPow(a, MOD-2, MOD)


def f(N,M,K):
    s = 0
    c = 1
    c1 = N-1
    c2 = 1
    d = modPow(M-1, N, MOD)
    d1 = getModInv(M-1, MOD)

    

    for k in range(K+1):
        d = d*d1%MOD

        s = (s + c*d)%MOD

        c = c*c1%MOD*getModInv(c2, MOD)%MOD
        c1 -= 1
        c2 += 1

    return (s*M)%MOD


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

if M == 1 and N == K+1:
    print(1)
else:
    print(f(N,M,K))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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

mod = 10**9+7 #出力の制限
N = 10**3*3
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 )

print(aall-cmb(n+p,p,mod))

Submission status: Runtime Error

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1<=k):
        print(1)
    else:
        print(0)
    exit()
mod = 998244353
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

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

Submission status: Runtime Error

Solution code:
n,m,k=[int(x) for x in input().split()]
#TODO Mutiply wih m
sumi=0
mod=998244353
prodi=pow(m-1,n-1,mod)
invi=pow(m-1,mod-2,mod)
for j in range(n-1,n-1-k-1,-1):
  sumi+=prodi
  sumi%=mod
  prodi*=n-j/j+1
  prodi%=mod
  prodi*=pow(j+1,mod-2,mod)
  prodi%=mod
  prodi*=invi
  prodi%=mod
sumi+=prodi
sumi%=mod
sumi*=m
sumi%=mod

Submission status: Runtime Error

Solution code:

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

ans = 0

for i in range(K+1):
    ans += M ** (i+1) * (M-1) ** (N-i-1)
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int, input().split())
MOD = 998244353
dp = np.array([0]*(K+1))
dp[0] = M

for _ in range(N-1):
    dp = dp + np.append(0, dp)[:K+1]*(M-1)%MOD
    dp %= MOD
print(sum(dp[:K+1])%MOD)

Submission status: Runtime Error

Solution code:
import math
def fact(n):
    return math.factorial(n)

N,M,K = map(int,input().split())
ans = 0
for x in range(K+1):
    temp = M
    for i in range(N-x-1):
        temp = temp * (M-1)
        temp = temp % 998244353
    temp = int(temp * fact(N) / (fact(x) * fact(N-x)))
    ans += temp
    ans = ans % 998244353
print(ans)

Submission status: Runtime Error

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

mod = 998244353
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

ans = 0
a= m*pow(m-1,n-1-k-1,mod)

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

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
MOD=998244353
X=M*pow(M-1,N-1,MOD)
#X=M*pow(M-1,N-1)
ans=X%MOD
i=1
'''
s=[]
a=1
for j in range(1,K+1):
  a*=N-j
  a=a//j
  s.append(a%MOD)
'''
for k in range(1,K+1):
  i*=(N-k)
  i=i//k
  #ans+=(i*X[-1-k])%MOD
  #i%=MOD
  ans+=((i%MOD)*X*pow(M-1,-k,MOD))%MOD
  #X=X//M-1
  #ans+=(i*X)%MOD
  ans%=MOD
print(ans%MOD)

Submission status: Runtime Error

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

mod = 998244353


def factorial(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


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


ans = 0
ans += M * pow(M-1, N-1)
ans %= mod

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

print(ans % mod)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
for i in range (N - 1):
    B = N * M
    M -= 1
    B = B + i
    print(B)
    break
else:
    print(B/2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations

N,M,K=(int(x) for x in input().rstrip('\n').split())
res = 0
for i in range(K):
  add = (M-1)**(N-i)
  add = M*add
  pat = len(combinations(range(N-1),N-i-1))
  res += add*pat
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

MOD = 998244353  # type: int


def solve(N: int, M: int, K: int):
    print((dfs(N-1, K, M) * M) % MOD)


def dfs(l, m, M):
    if l == 1:
        if m == 0:
            return M - 1
        else:
            return M
    else:
        if m == 0:
            return (dfs(l-1, m, M) * (M - 1)) % MOD
        else:
            return (dfs(l-1, m-1, M) + dfs(l-1, m, M) * (M - 1)) % MOD


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
DELIM = 998244353

def kaijo(n, x):
    double = (n**2) % DELIM
    if(x==1):
        return n
    if(x%2==0):
        return kaijo(double, x//2) % DELIM
    else:
        return (kaijo(double, x//2) * (n % DELIM)) % DELIM


def calc(N, M, x):
    m = M % DELIM
    m2 = (M-1) % DELIM
    nx = (N-x) % DELIM
    if(x == 0):
        return (m * kaijo(m2, N-1)) % DELIM
    return (nx * m * kaijo(m2, N-1-x)) % DELIM

def main():
    N, M, K = map(int, input().split())
    ans = 0
    for x in range(0, K+1, 1):
        ans = (ans + calc(N, M, x)) % DELIM
    print(ans)


main()

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
for i in range (1, N - 1):
    B = N * M
    M -= 1
    B = B + i
    print(B)
    break
else:
    print(B/2)

Submission status: Runtime Error

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=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())

p = 998244353

comb = Combination(N-1,p)

# 何個を同じ色の組にするか0~K
cnt = 0
for k in range(K+1):
    buf = 0
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    buf = comb(N-1,k)

    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    buf *= M%p
    buf %= p
    buf *= pow((M-1),(N-k-1),p)
    cnt += buf%p
    cnt %= p

print(cnt)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
MOD=998244353
X=M*pow(M-1,N-1,MOD)
#X=M*pow(M-1,N-1)
ans=X%MOD
i=1
s=[]
a=1
for j in range(1,K+1):
  a*=N-j
  a=a//j
  s.append(a%MOD)
for k in range(1,K+1):
  #i*=(N-k)
  #i=i/k
  #ans+=(i*X[-1-k])%MOD
  #i%=MOD
  ans+=(s[k-1]*X*pow(M-1,-k,MOD))%MOD
  #X=X//M-1
  #ans+=(i*X)%MOD
  ans%=MOD
print(ans%MOD)

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
Q = [[0 for i in range(K+1)] for j in range(N)]
Q[0][0] = M
for i in range(1,N):
  for j in range(K+1):
    Q[i][j] = Q[i-1][j-1]+(M-1)*Q[i-1][j]
print(sum(Q[N])%998244353)

Submission status: Runtime Error

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

MOD = 998244353  # type: int


def solve(N: int, M: int, K: int):
    print((dfs(N-1, K, M) * M) % MOD)


def dfs(l, m, M):
    if l == 1:
        if m == 0:
            return M - 1
        else:
            return M
    else:
        if m == 0:
            return (dfs(l-1, m, M) * (M - 1)) % MOD
        else:
            return (dfs(l-1, m-1, M) + dfs(l-1, m, M) * (M - 1)) % MOD


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        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):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
    print(ans%mod)
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m,k =map(int,input().split())
mod = 998244353
ans = m**n-m**(n-k-2)*m*(n-k-1)
ans = ans % mod
print(int(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,k=map(int,input().split())
MOD=998244353
dp = np.zeros((n+1,n),dtype=np.int64)
dp[1][0]=m
for i in range(2,n+1):
    dp[i]+=dp[i-1]*(m-1)
    dp[i][1:]+=dp[i-1][:1]
    dp[i]%=MOD
print(sum(dp[n][:k+1]))

Submission status: Runtime Error

Solution code:
import copy
n,m,k = map(int, input().split())
mod = 998244353
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

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

Submission status: Runtime Error

Solution code:
from functools import reduce
mod = 998244353

def C(a, b, m):
  return 1 if b == 0 else reduce(lambda x, y:(x*y)%m, range(a-b+1, a+1))*pow(reduce(lambda x,y:(x*y)%m, range(1, b+1)), m-2, m)
  
N, M, K = map(int, input().split())
ans = (M*pow(M-1, (N-k-1), mod))%mod
k = 1
while k <= K and k < N:
  a = ((C(N, k, mod)-1)*M*pow(M-1, (N-k-1), mod))%mod
  ans += a
  k += 1
print(ans)

Submission status: Runtime Error

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

dp = [ [0] * (K+1) for _ in range(N+1)]

# 1個目
dp[1][0] = M

for i in range(1,N):
    for k in range(K+1):
        dp[i+1][k] += dp[i][k] * (M-1) % MOD  # 違う色
        if K > k:
            dp[i+1][k+1] += dp[i][k] % MOD # 同じ色


sum(dp[N]) % MOD

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
color = [i for i in range(m)]
ans = 0
def dfs(i, daburi, num):
    global ans
    if i == n-1:
        if daburi == k:
            ans += num % 998244353
            return 
        elif daburi < k:
            ans += num % 998244353
            return
    if daburi > k:
        return
    dfs(i+1, daburi, num*(m-1))
    dfs(i+1, daburi+1, num)
dfs(0, 0, m)
print(ans% 998244353)

Submission status: Runtime Error

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    comb=Combination(n-1)
    for i in range(n-1):
        mPow=(mPow*(m-1))%mod
        modPow.append(mPow)
    for i in range(n-1-k,n):
        ans+=(m*modPow[i]*comb(n-1,i))%mod
    print(ans%mod)
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,k=map(int,input().split())
dp=np.zeros((n,k+1))
dp[0][0]=m
#print(dp)

###0...k,1...k-1,2....<k-1
for i in range(1,n):
    dp[i][1:]=dp[i-1][0:k]
    dp[i]=(dp[i]+dp[i-1]*(m-1))%998244353
    #dp[i][0]=(dp[i-1][0]*(m-1))%998244353
    #for j in range(1,k+1):
    #    dp[i][j]=((dp[i-1][j]*(m-1))+(dp[i-1][j-1]))%998244353

#print(dp)
print(int(sum(dp[n-1]))%998244353)

Submission status: Runtime Error

Solution code:
import math

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

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    if i <= max(N-K,K)+1:
        fact_inv.append(pow(fact[-1],MOD-2,MOD))

def combinations_count(n, r):
    return (((fact[n] * fact_inv[n-r])%MOD) * fact_inv[r])%MOD

for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * pow(M-1,N-1-i,MOD) * combinations_count(N-1,i)
        SUM %= MOD

print(SUM)

Submission status: Runtime Error

Solution code:
import math
md=998244353

def p(x,y):
  ly=int(math.log2(y))
  d=[x]
  for i in range(ly):
    d.append((d[-1]**2)%md)
  s=1
  for i in range(ly+1):
    if y & 2**i:
      s=(s*d[i])%md
  return s
    
n,m,k=list(map(int,input().split()))

inv_t = [0]+[1]
for i in range(2,k+1):
  inv_t += [inv_t[md % i] * (md - int(md / i)) % md]

ans=0
c=1
for i in range(k+1):
  if i!=0:
    c=(c*(n-i)*inv_t[i])%md
  ans=(ans+p(m-1,n-i-1)*m*c)%md
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    if i <= min(N-K,K)+1:
        fact_inv.append(pow(fact[-1],MOD-2,MOD))

def combinations_count(n, r):
    return (((fact[n] * fact_inv[n-r])%MOD) * fact_inv[r])%MOD

for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * pow(M-1,N-1-i,MOD) * combinations_count(N-1,i)
        SUM %= MOD

print(SUM)

Submission status: Runtime Error

Solution code:
#### 逆元リストいらない
mod = 998244353
fact = [1]
fact_inv = [1]
for i in range(10**5+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

N,M,K = map(int,input().split())
ans = 0
for i in range(K+1):
    X = mod_comb_k(N-1,i,mod)
    Z = power_func(M-1,N-(i+1),mod)
    #print(X,Z)
    ans += X * M * Z % mod
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=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())

p = 998244353

comb = Combination(N-1,p)

# 何個を同じ色の組にするか0~K
cnt = 0
for k in range(K+1):
    buf = 0
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    buf = comb(N-1,k)

    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    if N-k-1 >= 0:
        buf *= M
        buf *= pow((M-1),(N-k-1),p)
        buf %= p
        cnt += buf
        cnt %= p

print(cnt)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
# tmp = m
mod = 998244353
ans = m * pow(m-1, n-1, mod)
ans %= mod
ncm = 1
ncm_list = [0 for _ in range(k)]
for i in range(k):
    ncm *= n-1-i
    ncm *= pow(i+1, mod-2, mod)
    ncm %= mod
    ncm_list[i] = ncm

powm_list = [0 for _ in range(k)]
tmp = m * pow(m-1, n-k-1, mod)
powm_list[k-1] = tmp
for i in range(k-2, -1, -1):
    tmp *= (m-1)
    tmp %= mod
    powm_list[i] = tmp

for i in range(k):
    ans += ncm_list[i] * powm_list[i]
    ans %= mod

print(ans)

Submission status: Runtime Error

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

def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+1):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] %mod
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    
    modcombs = [1]
    for k in range(1,n+1):
        modcombs.append(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    return modcombs

mods = modconb(n-1,n-1,mod)
# print(mods)
cnt = 0
for i in range(k+1):
    cnt += m*mods[i]*pow(m-1,n-i-1,mod)
    cnt %= mod
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,k=map(int,input().split())
dp=np.zeros((n,k+1))
dp[0][0]=m
#print(dp)

###0...k,1...k-1,2....<k-1
for i in range(1,n):
    dp[i][0]=(dp[i-1][0]*(m-1))%998244353
    for j in range(1,k+1):
        dp[i][j]=((dp[i-1][j]*(m-1))+(dp[i-1][j-1]))%998244353

print(int(sum(dp[n-1])))

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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

def nCr(n, r):
    r = min(n-r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

basic = m
for i in range(n - k - 1):
    basic = (basic * (m - 1)) % 998244353

answer = 0
for i in range(k + 1):
    basicnCr = (basic * nCr(n - k + i, k - i) % 998244353)
    answer = (answer + basicnCr) % 998244353
    basic = (basic * (m - 1)) % 998244353

print(answer)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
N,M,K=map(int,input().split())
MOD=998244353

MAX_N=N

#a**n mod p を再帰的に求める
def modPow(a,n,p):
    if n==0:
        return 1
    if n == 1:
        #n=1ならaを返す
        return a % p

    elif n % 2 == 1:
        #nが奇数ならば a * modPow(a,n-1(偶数),p)を返す
        return a * modPow(a,n-1,p) % p

    else:
        #nが偶数なら modPow(a,n//2,p) * modPow(a,n//2,p)とすると速い
        t = modPow(a,n//2,p)
        return t * t % p

fac=[None for i in range(MAX_N)]
finv=[None for i in range(MAX_N)]
inv=[None for i in range(MAX_N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        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
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX_N)

ans=0

for i in range(K+1):
    v=COM(N-1,N-1-K+i)%MOD
    v*=M
    v=v%MOD
    v*=modPow(M-1,N-1-K+i,MOD)
    v=v%MOD
    ans+=v
    ans=ans%MOD
print(ans)

Submission status: Runtime Error

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count += count_tmp
    count %= mod

print(count)

Submission status: Runtime Error

Solution code:
n,m,k=(int(i) for i in input().split())
l=[0 for i in range(k+2)]
l[k]=m
for i in range(n-1):
  r=[]
  for j in range(k+1):
    r.append(l[j]*(m-1)+l[j+1])
  r.append(0)
  l=r
print(sum(r)%998244353)