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

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

Submission status: Runtime Error

Solution code:
 = 998244353
n, m, k = map(int, input().split())
 
fact = [0]*(n+1)
fact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1]*i % MOD
 
invfact= [0]*(n+1)
for i in range(n+1):
    invfact[i] = pow(fact[i], MOD-2, MOD)
 
 
def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]
 
 
ans = 0
for i in range(k+1):
    ans += m*pow(m-1, n-1-i, MOD)*nCk(n-1, i)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import itertools
import numpy as np

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

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

comInit(MOD)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, k = map(int, readline().split())

ans = 0
for x in range(k, -1, -1):
    ans += now * com(n - 1, x, MOD) % MOD
    # ans += tmp
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
import itertools
import numpy as np

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

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

comInit(MOD)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, k = map(int, readline().split())

ans = 0
now = m * (m - 1) ** (n - k - 2) % MOD
for x in range(k, -1, -1):
    now *= (m - 1) % MOD
    ans += now * com(n - 1, x, MOD) % MOD
    # ans += tmp
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import math

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

result=0
result_sum=0

for i in range(K+1):
    if i==0:
        result_A=(M*(M-1)**(N-1))
        result_B=1
        result_sum += result_A
    else:
        result_A = result_A//(M-1)
        result_B = (result_B*(N-i)//i)

        result=(result_A*result_B)%998244353
        result_sum += result
          

print(result_sum%998244353)

Submission status: Runtime Error

Solution code:
def inverse_mod(a, mod=10**9+7):
    """ Calculate inverse of the integer a modulo mod.
    """
    return pow(a, mod-2, mod)


def combination_mod(n, r, mod=10**9+7):
    """ Calculate nCr modulo mod.
    """

    r = min(r, n-r)
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod

    return numerator * inverse_mod(denominator, mod) % mod


def create_inverses_list(n, mod):
    """ Create list of inverses of the integers 0 to n modulo mod.
    """
    
    inv_list = [1] * (n+1)
    for x in range(n+1):
        inv_list[x] = (-(mod//x) * inv_list[mod % x]) % mod
    
    return inv_list


def main():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())
    mod = 998244353

    inverses = create_inverses_list(n_max_pairs, mod)
    
    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod)
    e2 = 1
    total = e1 * e2 % mod

    for k in range(1, n_max_pairs+1):
        e1 = e1 * inverses[n_colors - 1] % mod
        e2 = e2 * (n_blocks - k) % mod * inverses[k] % mod
        total += e1 * e2 % mod
        total %= mod

    print(total)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def binom(n, k, q, F, I):
	return (F[n]*((I[k]*I[n-k])%q))%q

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	ans = 0
	for i in range(n-k, n+1):
		ans += (binom(n-1, i-1, MOD, F, I)*m*pow(m-1, i-1, MOD))%MOD
	print(ans % MOD)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    mod = 998244353
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result = result % mod
    return result

n,m,K = map(int,input().split())
MOD = 998244353
ans = 0
for k in range(K+1):
    aa = cmb(n-1,k)
    bb = pow(m-1,n-k-1,mod = MOD) * m
    ans += (aa*bb)%MOD
print(ans)

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

mod = 998244353

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

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

ans = pow(M, N, mod)
for L in range(K + 1, N):
    result = (M * pow(M - 1, N - L - 1, mod) * com(N - 1, N - L - 1)) % mod
    ans -= result

print(ans % mod)

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    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

n,m,k = inpl()
conb = Combination(100010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * m * pow(m-1,x,mod)
    res %= mod
print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    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

n,m,k = inpl()
conb = Combination(100010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * n * pow(n-1,x)
    res %= mod
print(res)

Submission status: Runtime Error

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

MOD=998244353

ans=0
temp2=1
temp4=(M-1)**(N-1)%MOD
'''
def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(N+3, MOD)
'''

inv=pow(M-1, -1, mod=MOD)

for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=temp4
    temp1%=MOD
    ans+=temp1*temp2%MOD
    
    #print(temp)
  else:
    temp1*=inv
    temp2*=(N-i)*i
    temp1%=MOD
    temp2%=MOD
    ans+=temp1*temp2%MOD
    
    #print(temp)

print(ans%MOD)

Submission status: Runtime Error

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

    fac, finv, inv = COMinit(N,MOD)

    ans = 0
    for i in range(K+1):
        ans += M % MOD * pow(M-1,N-1-i,MOD) % MOD * COM(N-1,i,MOD,fac,finv,inv) % MOD
    
    print(ans%MOD)

# COMの前処理
# テーブルを作る
# O(n)
def COMinit(N, mod):
    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 % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    
    return fac, finv, inv

# nCrを計算 前処理としてCOMinitの実行が必要
# O(1)
def COM(n, r, mod, fac, finv, inv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
if n==1:
    print(m)
else:
    ans,s=0,(m*pow(m-1,n-k-2,MOD))%MOD
    for x in range(k,-1,-1):
        s*=(m-1)
        s%=MOD
        ans+=(s*a*b[x]*b[n-x-1])%MOD
        ans%=MOD
    print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul #掛け算をする関数
from functools import reduce
from scipy.special import comb

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

for i in range(N)[::-1]:
    now = col
    now *= int(comb(N-1,i))
    if i <= K:
        ans += now
    col *= M-1

print(ans%mod)

Submission status: Runtime Error

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

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-2,MOD))%MOD
for x in range(k,-1,-1):
    s*=(m-1)
    s%=MOD
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


class mod_calc():
    def __init__(self, divisor, max_n):
        # assume prime
        self._divisor = divisor
        # nsq = math.ceil(math.sqrt(max_n))
        # feature fix_n? max_k?
        fact = np.empty((max_n+1,), dtype=int)
        fact[1] = fact[0] = f = 1
        for i in range(2, len(fact)):
            f = (f * i) % divisor
            fact[i] = f
        self._fact = fact
        fact_inv = np.empty((max_n+1,), dtype=int)
        fact_inv[max_n] = fi = pow(int(fact[max_n]), divisor-2, divisor)
        for i in range(max_n, 2, -1):
            fi = (fi * i) % divisor
            fact_inv[i-1] = fi
        fact_inv[1] = fact_inv[0] = 1
        self._fact_inv = fact_inv

    def comb(self, n, k):
        k = min(k, n-k)
        if k == 0 or k == n:
            return 1
        return self.mul(self._fact[n], self._fact_inv[n-k], self._fact_inv[k])

    def pow(self, a, n):
        return pow(a, n, self._divisor)

    def mul(self, *a):
        # TODO montogomery
        # https://ikatakos.com/pot/programming_algorithm/number_theory/montgomery_multiplication
        r = a[0]
        for m in a[1:]:
            r = (r * m) % self._divisor
        return r

    def sum(self, *a):
        r = a[0]
        for m in a[1:]:
            r = (r + m) % self._divisor
        return r


def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        return 1
    c = mod_calc(998244353, N-1)
    count = 0
    for k in range(K+1):
        count = c.sum(c.mul(c.comb(N-1,k), M, c.pow(M-1, N-k-1)), count)
    return count


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

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

MOD=998244353

ans=0
temp2=1
temp3=1
temp4=(M-1)**(N-1)%MOD

for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=temp4
    temp1%=MOD
    ans+=temp1*temp2%MOD
    
    #print(temp)
  else:
    temp1/=(M-1)
    temp2*=(N-i)
    temp3*=i
    temp1%=MOD
    temp2%=MOD
    temp3%=MOD
    temp=temp1*temp2*temp3%MOD
    ans+=temp
    #print(temp)

print(ans%MOD)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
def modpow(x, y, mod):
    ret = 1
    z = x
    n = len(bin(y)) - 2
    for i in range(n):
        if ((y >> i) & 1):
            ret = ret * z % mod
        z = z * z % mod
    return ret

def modinv(x, mod):
    return modpow(x, mod-2, mod)

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

    c1 = 1
    for i in range(1, n):
        c1 = c1 * i % mod
        if i == k:
            c2 = modinv(c1, mod)
    c3 = modinv(c1, mod)
    c3_list = [0] * (k+1)
    c3_list[k] = c3
    for i in range(k-1, -1, -1):
        c3 = c3 * (n-(k-i)) % mod
        c3_list[i] = c3
    comb = (c1 * c2 % mod) * c3_list[0] % mod

    x = m * modpow(m-1, n-k-1, mod) % mod

    ret = x * comb % mod

    for i in range(1, k+1):
        c2 =c2 * (k-i+1) % mod
        comb = (c1 * c2 % mod) * c3_list[i] % mod
        x = x * (m-1) % mod

        ret += x * comb % mod
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# E

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

res = [0] * (K+1)
res[0] = (M * (M-1)**(N-1 - K)) % p
p = 998244353
for n in range(1, K+1):
    res[n] = (res[n-1] * (N-n) * pow(n, p-2, p)) % p

print(sum(res) % p)

Submission status: Runtime Error

Solution code:
N,M,K=map(int, input().split())
'''
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
'''

# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

Submission status: Runtime Error

Solution code:
N,M,K=map(int, input().split())
'''
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
'''

# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

a = cmb(n,r)

ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

Submission status: Runtime Error

Solution code:
def binom(n,r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

def power(n,r):
    res = 1
    for i in range(r):
        res *= n
        res %= p
    return res

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

p = 998244353

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
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)

num = 0

pw = (m-1)**(n-k-2) % p

for i in range(k+1):
    pw *= m-1
    pw %= p
    num += m * pw * binom(n-1, k - i)
    num %= p

print(num)

Submission status: Runtime Error

Solution code:
def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

###############################

N,M,K=map(int,input().split())
p=998244353
fac=[1,1]
for i in range(2,N+1):
  fac.append( (fac[-1]*i)%p )
R = M*(M-1)**(N-K-2)

ans=0
for i in range(K,-1,-1):
  R = (R*(M-1))%p
  L = combi(N-1,i)
  #print(i,R,L)
  ans = (ans + (R*L)%p)%p
print(ans)

Submission status: Runtime Error

Solution code:
def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

###############################

N,M,K=map(int,input().split())
p=998244353
fac=[1,1]
for i in range(2,N+1):
  fac.append( (fac[-1]*i)%p )
R = M*(M-1)**(N-K-2)

ans=0
for i in range(K,-1,-1):
  R = (R*(M-1))%p
  L = combi(N,i)
  ans = (ans + (R*L)%p)%p
print(ans)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
s=0
z=m
w=1
dic={}
for u in range(n-1):
    dic[u]=w
    w=round(w*(n-u-1)/(u+1))%998244353
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()%998244353
   b=dic[j]
   s+=a*b
print(s%998244353)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
s=0
z=m
w=1
dic={}
for u in range(n-1):
    dic[u]=w
    w=round(w*(n-u-1)/(u+1))%998244353
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()
   b=dic[j]
   s+=a*b
print(s%998244353)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
s=0
z=m
w=1
dic={}
for u in range(n-1):
    dic[u]=w
    w=round(w*(n-u-1)/(u+1))%998244353
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()
   b=dic[j]
   s+=a*round(g(n-1)/(g(j)*g(n-j-1)))
print(s%998244353)

Submission status: Runtime Error

Solution code:
g=math.factorial
n,m,k=map(int,input().split())
s=0
z=m
w=1
dic={}
for u in range(n-1):
    dic[u]=w
    w=round(w*(n-u-1)/(u+1))%998244353
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()
   b=dic[j]
   s+=a*round(g(n-1)/(g(j)*g(n-j-1)))
print(s%998244353)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
s=0
dic={}
w=1
for u in range(n):
   dic[u]=w
   w=round(w*(n-u)/(u+1))
z=m
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()
   s+=a*dic[j]
print(round(s)%998244353)

Submission status: Runtime Error

Solution code:
s=0
dic={}
w=1
for u in range(n):
   dic[u]=w
   w=round(w*(n-u)/(u+1))
z=m
l=[]
for i in range(n):
    l.append(z)
    z=(m-1)*z
for j in range(k+1):
   a=l.pop()
   s+=a*dic[j]
print(round(s)%998244353)

Submission status: Runtime Error

Solution code:
60522 114575 7559

Submission status: Runtime Error

Solution code:
# import sys
# sys.setrecursionlimit
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MODULO = 998244353


def factorial(n: int) -> List[int]:
    fact = [0] * (n + 1)
    inv = [0] * (n + 1)
    fact[0] = 1
    inv[0] = 1
    for i in range(1, n + 1):
        fact[i] = (i * fact[i - 1]) % MODULO
        inv[i] = pow(fact[i], MODULO - 2, MODULO)
    return fact, inv


def combi(n: int, k: int, fact: List[int]) -> int:
    r = 1
    for i in range(k):
        r *= n - i
    return (r // fact[k]) % MODULO


def solve(n: int, m: int, k: int) -> int:
    result = 0
    # fill the cache
    fact, inv = factorial(n - 1)
    for i in range(1, k + 1):
        result = (
            result
            + (
                m
                * pow(m - 1, n - i - 1, MODULO)
                * fact[n - 1]
                * inv[i]
                * inv[n - 1 - i]
            )
            % MODULO
        )
    return result % MODULO


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, M, K = map(int, input().split())
    result = solve(N, M, K + 1)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    c = m
    for i in range(n-1):
        c = c*(m-1)%z
    a = [c]
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-e[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    for i in range(1, k+1):
        a.append(int(a[-1]*b[i]/b[i-1]/(m-1))%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
m = 60
DP = [[None for j in range(m)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, m):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(1, int((n-1)/2)+1):
        b.append(int(b[-1]*(n-i)/i)%z)
    for i in range(int(n/2)):
        b.append(b[int(n/2)-i-1])
    for i in range(1, k+1):
        a.append(int(a[-1]*b[i]/b[i-1]/(m-1))%z)
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

Submission status: Runtime Error

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1,1]
finv = [1,1]
inv = [1,1]
MOD = 998244353
for i in range(2,n):
    fac[i].append(fac[i-1]*i%MOD)
    inv[i].append(MOD-inv[MOD%i]*(MOD//i)%MOD)
    finv[i].append(finv[i-1]*inv[i]%MOD)
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += (comb(n-1,i)*(m*(m-1)**(n-i-1)%MOD))%MOD
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

l2 = m*(m-1)**(n-k-2)
for _k in range(k, -1, -1):
    # print(_k)

    l2 %= p
    l2 *= (m - 1)
    l2 %= p

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p


print(ans)