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:
n, m, k = map(int, input().split())

mod = 998244353

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

N = 10**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 )

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

print(ans % mod)

Submission status: Runtime Error

Solution code:
import math
mod = 998244353

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

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

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

    return _modC


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

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

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

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




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


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

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
mod = 998244353

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

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

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

    return _modC


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

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

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

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




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


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

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

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

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

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

Submission status: Runtime Error

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

#定義部
F=[0]*(2*10**5)
G=[0]*(2*10**5)

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

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

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

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

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

Submission status: Runtime Error

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

#定義部
F=[0]*N
G=[0]*N

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

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

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

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

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

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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


mod = 998244353

d = dict()
d[1]=1
for i in range(2,10**5):
    d[i] = d[i-1]*i%998244353
    

    
def combinations_count(n, r):
    if r==0:
        return 1
    return d[n] // (d[n-r] * d[r])



m_1_dict={}
m_1_dict[0] = 1
for i in range(1, 2*100000):
    m_1_dict[i] = m_1_dict[i-1] * (M-1) % mod



ans = 0
for k in range(K+1):
    ans += combinations_count(N-1, k)*M*m_1_dict[N-k-1]
#     print(combinations_count(N-1, k)*M*(M-1)**(N-k-1))
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1000000)
n, m, k = map(int, input().split())
result = 0
def search(now_node, same_num, diff_num):
    global result
    if(now_node == n):
        result += m * (m-1) ** diff_num
    else:
        if(same_num < k):
            search(now_node + 1, same_num + 1, diff_num)
        search(now_node + 1, same_num, diff_num + 1)
search(1, 0, 0)
print(result % 998244353)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10000000)
n, m, k = map(int, input().split())
result = 0
def search(now_node, same_num, diff_num):
    global result
    if(now_node == n):
        result += m * (m-1) ** diff_num
    else:
        if(same_num < k):
            search(now_node + 1, same_num + 1, diff_num)
        search(now_node + 1, same_num, diff_num + 1)
search(1, 0, 0)
print(result % 998244353)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
result = 0
def search(now_node, same_num, diff_num):
    global result
    if(now_node == n):
        result += m * (m-1) ** diff_num
    else:
        if(same_num < k):
            search(now_node + 1, same_num + 1, diff_num)
        search(now_node + 1, same_num, diff_num + 1)
search(1, 0, 0)
print(result % 998244353)

Submission status: Runtime Error

Solution code:
import itertools
n,m,k = map(int,input().split())
def judge_pair(block):
  total = 0
  for i in range(len(block)):
    pair = 0
    for j in range(n-1):
      if block[i][j]==block[i][j+1]:
        pair += 1
    if pair <= k:
      total +=1
    
  return total%998244353

color = [i for i in range(m)]
colors = color*n
block = list(itertools.permutations(colors,n))
block = list(set(block))
print(judge_pair(block))

Submission status: Runtime Error

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

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

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

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

def main():
  n,m,k=LI()
  c=nCrMod(100005)
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=c.comb(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())

Submission status: Runtime Error

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

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

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

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  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 or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n,m,k=LI()
ans=0
col=m
for x in range(n)[::-1]:
  now=col
  now*=com(n-1,x)
  if x<=k:
    ans+=now
    ans%=mod
  col*=m-1
print(ans)

# main()
print(main())

Submission status: Runtime Error

Solution code:
#factorial
mod = 998244353 
N = 1000000
modinv_t = [0, 1]
modfact_t = [1, 1]
modfactinv_t = [1, 1]
for i in range(2,N+1):
  modfact_t.append(modfact_t[-1] * i % MOD)
  modinv_t.append(modinv_t[MOD%i] * (MOD-(MOD//i)) % MOD)
  modfactinv_t.append(modfactinv_t[-1] * modinv_t[-1] % MOD)
# permutation
def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD
# combination
def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD
#
def nHr(n, r):
  return  nCr(n+r-1,r)
#

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

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

Submission status: Runtime Error

Solution code:
class Combination:

    """
    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())
mod = 998244353
comb = Combination(N-1, mod)

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

print(ans)

Submission status: Runtime Error

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

ans=0
if m==1:##コーナー
  	print(1 if k==n-1 else 0)
    exit()
tmp=m*pow(m-1,n-1,mod)
m_inv=pow(m-1,mod-2,mod)
invs=[0]+[pow(i+1,mod-2,mod) for i in range(n)]
for i in range(1,k+2):
    ans+=tmp
    #print(ans)
    tmp*=m_inv
    if i<n:##?
        tmp*=n-i
        tmp*=invs[i]
    tmp%=mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.special import comb

mod = 998244353

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

# DP = [[0]*N for _ in range(N)]
# DP[0][0] = M

# DP = []


# for n in range(1,N):
# 	for k in range(N):
# 		if k==0:
# 			DP[n][k] = DP[n-1][k]*(M-1) % mod
# 		else:
# 			DP[n][k] = (DP[n-1][k]*(M-1) + DP[n][k-1]) % mod

# ans = sum(DP[N-1][:(K+1)]) % mod
# print(ans)

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

print(int(ans*M) % mod)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.special import comb

mod = 998244353

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

# DP = [[0]*N for _ in range(N)]
# DP[0][0] = M

# DP = []


# for n in range(1,N):
# 	for k in range(N):
# 		if k==0:
# 			DP[n][k] = DP[n-1][k]*(M-1) % mod
# 		else:
# 			DP[n][k] = (DP[n-1][k]*(M-1) + DP[n][k-1]) % mod

# ans = sum(DP[N-1][:(K+1)]) % mod
# print(ans)

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

print(int(ans*M) % mod)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
from scipy.special import comb

mod = 998244353

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

# DP = [[0]*N for _ in range(N)]
# DP[0][0] = M

# DP = []


# for n in range(1,N):
# 	for k in range(N):
# 		if k==0:
# 			DP[n][k] = DP[n-1][k]*(M-1) % mod
# 		else:
# 			DP[n][k] = (DP[n-1][k]*(M-1) + DP[n][k-1]) % mod

# ans = sum(DP[N-1][:(K+1)]) % mod
# print(ans)

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

print(int(ans*M) % mod)

Submission status: Runtime Error

Solution code:
import math

def combination_count(n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))

if __name__ == '__main__':
    nkm = input()
    nkm = nkm.split()
    n = int(nkm[0])
    m = int(nkm[1])
    k = int(nkm[2])

    ans = 0
    for i in range(k+1):
        ans += m * int(combination_count(n-1,i)) * 1**i * (m - 1)**(n-1-i)%998244353
    print(ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
P=998244353
class FactInv:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[1]*(N+1);ifact=[0]*(N+1)
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
FI=FactInv(N+10,P)
ans=0
for i in range(0,K+1):
    ans+=(M*FI.comb(N-1,i)*pow(M0,N-1-i,P))%P
    ans%=P
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
col = m
for k in range(N-1, -1, -1):
    now = col
    now *= combinations(N-1, k);
    if k <= K:
        ans += now
    col *= m-1

print(ans)

Submission status: Runtime Error

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


def main() -> None:
    MODULUS = 998244353
    N, M, K = rmi()
    acc = 0
    for k in range(K + 1):
        subacc = M
        subacc *= mod_combinations(N - 1, k, MODULUS)
        subacc %= MODULUS
        subacc *= mod_pow(M - 1, N - k - 1, MODULUS)
        subacc %= MODULUS
        acc += subacc
        acc %= MODULUS
    w(acc)


def mod_pow(x: int, a: int, mod: int) -> int:
    if a == 1:
        return x
    if a % 2:
        return x * mod_pow(x, a - 1, mod) % mod
    t = mod_pow(x, a // 2, mod)
    return t ** 2 % mod


def mod_inverse(a: int, mod: int) -> int:
    def ext_gcd(a: int, b: int) -> (int, int, int):
        x, y = [1, 0], [0, 1]
        while b:
            q, a, b = a // b, b, a % b
            x = [x[1], x[0] - q * x[1]]
            y = [y[1], y[0] - q * y[1]]
        return (a, x[0], y[0])
    g, x, _ = ext_gcd(a, mod)
    assert g == 1, 'Modular inverse does not exist.'
    return x % mod


def mod_inverse2(x: int, mod: int) -> int:
    return mod_pow(x, mod - 2, mod)


def mod_factorial(x: int, mod: int, limit: int = 0) -> int:
    result = 1
    for i in range(x, limit, -1):
        result *= i
        result %= mod
    return result


def mod_combinations(n: int, k: int, mod: int) -> int:
    assert 0 <= k <= n, 'n and k should be 0 <= k <= n.'

    lower, upper = min(k, n - k), max(k, n - k)
    numer = mod_factorial(n, mod, upper)
    denom = mod_factorial(lower, mod)
    return numer * mod_inverse(denom, mod) % mod


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Runtime Error

Solution code:
from scipy.special import comb
N,M,K = map(int, input().split())
answer = 0
for i in range(K+1):
    answer += M*comb(N-1,i, exact=True)*(M-1)**(N-1-i)*1**i
print(answer%998244353)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
N,M,K=map(int,input().split())
total=0

def ans(n,m,k):
    if k==0:
        a=m
        for i in range(n-1):
            a=a*(m-1)%998244353
        return a
    if n==1:
        return m
    return ((m-1)*ans(n-1,m,k)+ans(n-1,m,k-1))%998244353

print(ans(N,M,K)%998244353)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
N,M,K=map(int,input().split())
total=0

def ans(n,m,k):
    if k==0:
        return m*((m-1)**(n-1))
    if n==1:
        return m
    return ((m-1)*ans(n-1,m,k)+ans(n-1,m,k-1))%998244353

print(ans(N,M,K)%998244353)

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce
N,M,K=map(int,input().split())
total=0

def ans(n,m,k):
    if k==0:
        return m*((m-1)**(n-1))
    if n==1:
        return m
    return (m-1)*ans(n-1,m,k)+ans(n-1,m,k-1)

print(ans(N,M,K)%998244353)

Submission status: Runtime Error

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

x = pow(m-1, n-k-1, 998244353)
c = m * ((m-1) ** k)

s = c


for i in range(1, k+1):
    c = c * (n-i) // (i * (m-1))
    s += c 

print((s * x) % 998244353)

Submission status: Runtime Error

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

c = m * ((m-1) ** (n-1))

s = c


for i in range(1, k+1):
    c = c * (n-i) // (i * (m-1))
    s += c

print(s % 998244353)

Submission status: Runtime Error

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

c = m * ((m-1) ** (n-1))

s = c


for i in range(1, k+1):
    if i > 0:
        c = c * (n-i) // (i * (m-1))
    s += c 

print(s % 998244353)

Submission status: Runtime Error

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

s = 0


c = m * ((m-1) ** (n-1))


for i in range(k+1):
    if i > 0:
        c = c * (n-i) // (i * (m-1))
    s += c  % 998244353

print(s % 998244353)

Submission status: Runtime Error

Solution code:
import math

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

s = 0

for i in range(k+1):
    s += (math.factorial(n-i) // (math.factorial(n-2*i) * math.factorial(i)) ) * m * ((m-1) ** (n-i-1))

print(s % 998244353)

Submission status: Runtime Error

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    P = [1]*(k+1)
    p = pow(m-1, n-2-k, mod)
    for i in range(k+1):
        p = p*(m-1) % mod
        P[-1-i] = p

    ret = m*P[0] % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*P[i]*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

Solution code:
N,M,K = list(map(int､input()｡split()))
mod = 998244353
numer = [1]
denom = [1]
for i in range(1,N+1):
  numer.append(numer[-1]*(N-i+1) %mod)
  denom.append(denom[-1]*i %mod)

ans = 0
for k in range(K+1):
  if k == 0:
    ans =  (ans + M * (M-1)**(N-k-1)) %mod
  else:
    ans = (ans + numer[k] * pow(denom, mod-2, mod)) %mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M,K = IL()
mod = 998244353
numer = [1]
denom = [1]
for i in range(1,N+1):
  numer.append(numer[-1]*(N-i+1) %mod)
  denom.append(denom[-1]*i %mod)

ans = 0
for k in range(K+1):
  if k == 0:
    ans =  (ans + M * (M-1)**(N-k-1)) %mod
  else:
    ans = (ans + numer[k] * pow(denom, mod-2, mod)) %mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 998244353
numer = [1]
denom = [1]
for i in range(1,N+1):
  numer.append(numer[-1]*(N-i+1) %mod)
  denom.append(denom[-1]*i %mod)

N,M,K = IL()
ans = 0
for k in range(K+1):
  if k == 0:
    ans =  (ans + M * (M-1)**(N-k-1)) %mod
  else:
    ans = (ans + numer[k] * pow(denom, mod-2, mod)) %mod
print(ans)

Submission status: Runtime Error

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

# 隣り合ったブロックを異なる色で塗ると何通りあるか
# 隣り合ったブロック通しで同じ色にする場所をn-1箇所から選ぶ(combination)

# combinationを計算する
def combination(n, r, p):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return (f[n]*f_inverse[r]*f_inverse[n-r])%p

f = [1, 1] # n!を計算する
f_inverse = [1, 1]# n!の逆元を計算する
n_inverse = [0, 1] # nの逆元
for i in range(2, n+1):
    f.append((f[i-1]*i)%mod)
    n_inverse.append( (-1*(mod//i)*n_inverse[mod%i])%mod )
    f_inverse.append((f_inverse[i-1]*n_inverse[i])%mod)

c = m * ((m-1)**(n-1))
count = 0
for i in range(k+1):
    # print(count, c, combination(n-1, i, mod))
    count += combination(n-1, i, mod) * c
    c =  c // (m-1) 
    count %= mod
    
print(count)

# for i in range(1, k):
#     count += t * s
#     t = t//(m-1)
#     s = ((s * (n-1-i))// (i+1))%998244353
#     print(count, t, s)

Submission status: Runtime Error

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

# 隣り合ったブロックを異なる色で塗ると何通りあるか
# 隣り合ったブロック通しで同じ色にする場所をn-1箇所から選ぶ(combination)

# combinationを計算する
def combination(n, r, p):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return (f[n]*f_inverse[r]*f_inverse[n-r])%p

f = [1, 1] # n!を計算する
f_inverse = [1, 1]# n!の逆元を計算する
n_inverse = [0, 1] # nの逆元
for i in range(2, n+1):
    f.append((f[i-1]*i)%mod)
    n_inverse.append( (-1*(mod//i)*n_inverse[mod%i])%mod )
    f_inverse.append((f_inverse[i-1]*n_inverse[i])%mod)

c = (m * ((m-1)**(n-1)))%mod
count = 0
for i in range(k+1):
    # print(count, c, combination(n-1, i, mod))
    count += combination(n-1, i, mod) * c
    c =  c // (m-1) 
    count %= mod
    
print(count)

# for i in range(1, k):
#     count += t * s
#     t = t//(m-1)
#     s = ((s * (n-1-i))// (i+1))%998244353
#     print(count, t, s)

Submission status: Runtime Error

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

def power_func(a, n, p):
    bi = str(format(n,"b"))#2進表現に
    if n == 0:
        return 1
    if a == 0:
        return 0
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res

P = 998244353
inv_t = [0] + [1]
for i in range(2, max(M,K)+2):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

Submission status: Runtime Error

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


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

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

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

Submission status: Runtime Error

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


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

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

ans = (M * power_func(M-1, N-1, P))%P
curr = ans
for k in range(K):
    N-k-1 < 0 : break
    curr = (curr*(N-k-1)*inv_t[k+1]*inv_t[M-1]) % P
    ans += curr
    ans %= P

print(ans)

Submission status: Runtime Error

Solution code:
x,y,z=map(int,input().split())
import math
def f(n,m,k):
    a=(m*(math.factorial(n-1)//(math.factorial(k)*math.factorial(n-k-1))))%998244353
    for i in range(n-k-1):
       a=(a*(m-1))%  998244353   
    return a
def g(n,m,k):
    if k==0:
        return f(n,m,0)%998244353
    else:
        return (f(n,m,k)+g(n,m,k-1))%998244353
print(g(x,y,z))

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, M, K = map(int, input().split())

    #output
    mod = 998244353

    n_ = 4*10**5 + 5
    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 cmb(n,r):
        if n <= 0 or r < 0 or r > n: return 0
        return fun[n]*rev[r]%mod*rev[n-r]%mod

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

    answer %= mod

    if N == 1:
        answer = M
    else:
        continue

    print(answer)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#https://mathtrain.jp/tyohukuc

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

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
N = n+1 # 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)

ans = 0
beki = [1,m-1]
for i in range(2,N+1):
    beki.append(((beki[-1]*(m-1)) % p))

for x in range(k+1):
    ans += m * beki[n-x-1] %p * cmb(n-1,x,p)) %p
    ans = ans % p
print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 998244353
class Combination(object):
	def __init__(self, N, MOD):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1
 
		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % MOD
			self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
			self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    if N == 1:
        print(1)

    Com = Combination(N-1, MOD)
    ans = 0
    for k in reversed(range(K+1)):
        ans += M * pow(M-1, N-k-1, MOD) * Com.com(N-1, k)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()