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: Wrong Answer

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-k)))%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) )% mod
    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: Wrong Answer

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


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: Wrong Answer

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


def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    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: Wrong Answer

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, max(M,K)+1):
    inv_t += [inv_t[P % i] * (P - 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))%P)*inv_t[k+1])%P)*inv_t[M-1]) % P
    ans += curr
    ans %= P
 
print(ans)

Submission status: Wrong Answer

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, max(M,K)+1):
    inv_t += [inv_t[P % i] * (P - 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: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=98244353
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(200005)
  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: Wrong Answer

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, 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: Wrong Answer

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, max(M,K)+1):
    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: Wrong Answer

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

Submission status: Wrong Answer

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

    print(answer % mod)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# a^n mod p
def exp_by_sq_p(a, n, p):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = a % p
    elif  n % 2 == 0:
        exp = exp_by_sq_p(a * a % p, n // 2, p)
    else:
        exp = a * exp_by_sq_p(a * a % p, (n - 1) // 2, p) % p
    return exp % p

N, M, K = [int(x) for x in input().split()]
p = 998244353

# sum_{i = 0 to K}{(N - 1 choose N - i - 1) * M * (M - 1)^(N - i - 1)}
# = M * (M - 1) ^ (N - K - 1) * sum_{j = 0 to K}{(N - 1 choose K - j) * (M - 1)^j}
ans = 0
inv = exp_by_sq_p(M - 1, p - 2, p) # inverse of (M - 1) mod p
binomial = 1
pow = exp_by_sq_p(M - 1, K, p) # (M - 1)^K mod p

for i in range(K + 1):
    ans = (ans + binomial * pow % p) % p
    binomial = binomial * (i + 2) * exp_by_sq_p(N - 2 - i, p - 2, p)
    pow = pow * inv % p

ans = ans * M * exp_by_sq_p(M - 1, N - K - 1, p) % p

print(ans)

Submission status: Wrong Answer

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

    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: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


mod = 998244353
comb = combination(mod)
n, m, k = inpl()
if m == 1:
    if k < n - 1:
        print(0)
        exit()
    else:
        print(0)
        exit()
ans = 0
for i in range(min(n, k + 1)):
    ans += m * pow(m - 1, n - 1 - i, mod) * comb.calc(n - 1, i) % mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 998244353

class mod_combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
        
    def calc(self, n, k): # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


n, m, k = map(int, input().split())
C = mod_combination(n)
ans = 0
for x in range(k + 1):
    ans += C.calc(n - 1, n - x - 1) * pow(m - 1, n - x - 1, mod) % mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
new=998244353

def nCr(n,r):
  if r*2>n:
      return nCr(n,n-r)
  else:
      a = b = 1
      for i in range(r):
          a = a * (n - i) % mod
          b = b * (r - i) % mod
      return (a * pow(b,mod-2,mod)) % mod
n,m,k=map(int,input().split())

x=m*((m-1)**(n-k-1))%new
y=0
while k>=0:
    y+=nCr(n-1,k)%new
    y%=new
    k-=1
print(x*y%new)

Submission status: Wrong Answer

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):
    # now *= (m - 1) % MOD
    ans += com(n - 1, x, MOD) % MOD
    # ans += tmp
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
if M != 1:
  mi = modinv(M-1,m)

  A = M * pow(M-1,N-1,m)
  for k in range(K+1):
    if k>0:
      B = (B*(N-k)*modinv(k,m))%m
    res = (res+ A*B)%m
    A = (A*mi)%m
  print (res)
else:
  print(1)

Submission status: Wrong Answer

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(max(N+3,M-1), MOD)
 
 
#inv=1
#for i in range(MOD-2):
#  inv*=M-1
#  inv%=MOD
 
 
for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    #cmb=temp1
    #print(cmb)
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    #cmb=cmb*(N-i-1)*i*invs[i]%MOD
    #print(cmb)
 
print(ans%MOD)

Submission status: Wrong Answer

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(max(N+3,M-1), MOD)


#inv=1
#for i in range(MOD-2):
#  inv*=M-1
#  inv%=MOD


for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    cmb=temp1
    #print(cmb)
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    cmb=cmb*(N-i-1)*i*invs[i]%MOD
    #print(cmb)

print(ans%MOD)

Submission status: Wrong Answer

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_table(n, mod=10**9+7):
    """ Create table for inverses of the integers 0 to n modulo mod.
    """

    inv_table = [1] + [1] * n
    for x in range(2, n+1):
        inv_table[x] = -(mod//x) * inv_table[mod % x] % mod

    return inv_table


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

    inverses = create_inverses_table(max(n_colors, n_max_pairs), mod)

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod) % mod if n_colors > 0 else 1
    e2 = 1
    total = e1 * e2

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

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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_table(n, mod=10**9+7):
    """ Create table for inverses of the integers 0 to n modulo mod.
    """

    inv_table = [0] + [1] * n
    for x in range(2, n+1):
        inv_table[x] = -(mod//x) * inv_table[mod % x] % mod

    return inv_table


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

    inverses = create_inverses_table(max(n_colors, n_max_pairs), mod)

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

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

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=10**9+7):
    """ Create list of inverses of the integers 0 to n modulo mod.
    """

    inv_list = [0] + [1] * n
    for x in range(2, 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(max(n_colors, n_max_pairs), mod)

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

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

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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=10**9+7):
    """ Create list of inverses of the integers 0 to n modulo mod.
    """

    inv_list = [1] * (n+1)
    for x in range(2, 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(max(n_colors, n_max_pairs), mod)

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod) % 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: Wrong Answer

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(2, 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(max(n_colors, 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: Wrong Answer

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 main():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())
    mod = 998244353

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod)
    inv_mod_1 = inverse_mod(n_colors - 1, mod)
    e2 = 1

    total = e1 * e2 % mod

    for k in range(1, n_max_pairs+1):
        e1 = e1 * inv_mod_1 % mod
        e2 = e2 * (n_blocks - k) % mod * inverse_mod(k, mod) % mod
        total += e1 * e2 % mod
        total %= mod

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 main():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())
    mod = 998244353

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod)
    inv_mod_1 = inverse_mod(n_colors - 1, mod)
    e2 = 1

    total = e1 * e2 % mod

    for k in range(1, n_max_pairs+1):
        e1 = e1 * inv_mod_1 % mod
        e2 = e2 * (n_blocks - k) % mod * inverse_mod(k, mod)
        total += e1 * e2 % mod
        total %= mod

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 main():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())
    mod = 998244353

    def calc(n, m, k):
        return m * pow(m-1, n-k, mod) % mod * combination_mod(n-1, k, mod) % mod

    total = 0
    for n_pairs in range(n_max_pairs + 1):
        total += calc(n_blocks, n_colors, n_pairs)
        total = total % mod

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod= 998244353

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

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

Submission status: Wrong Answer

Solution code:
def binary(n):
    return bin(n)[2:]

def pow_by_binary_exponentiation(a, x, n):
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

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 = (cmb(n-1,k) * pow_by_binary_exponentiation(m-1,n-k-1,MOD) * m) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def binary(n):
    return bin(n)[2:]

def pow_by_binary_exponentiation(a, x, n):
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

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 = (cmb(n,k) * pow_by_binary_exponentiation(m-1,n-k-1,MOD) * m) % MOD
print(ans)

Submission status: Wrong Answer

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

mod=998244353

fact=[1 for i in range(N+1)]
for i in range(1,N):
    fact[i+1]=(fact[i]*(i+1))%mod

def nCk(n,k):
    return fact[n]//fact[n-k]//fact[k]

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

Submission status: Wrong Answer

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

mod=998244353

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

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def modadd(a,b):
    return (a+b) % 998244353

N,M,K = (int(x) for x in input().split())
mem = []
for x in mempow(M-1,N-1):
    mem.append(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    print(reduce(modadd,[comb(N-1,i)*M*mem[N-i-1] for i in range(K+1)]))

Submission status: Wrong Answer

Solution code:
a = 998244353

n,m,k = map(int, input().split(" "))
dp=[[0]*(k+1)]*n
p = (m-1)

dp[0][0] = m

for i in range(n-1):
  dp[i+1][0] = (dp[i][0]*p)
  for j in range(1,min(i+2,k+1)):
    dp[i+1][j] = (dp[i+1][j-1]+dp[i][j]*p)

print(sum(dp[n-1])%a)

Submission status: Wrong Answer

Solution code:
a = 998244353

n,m,k = map(int, input().split(" "))
dp=[[0]*(k+1)]*n
p = (m-1)%a

dp[0][0] = m%a

for i in range(n-1):
  dp[i+1][0] = (dp[i][0]*p)%a
  for j in range(1,min(i+2,k+1)):
    dp[i+1][j] = (dp[i+1][j-1]+dp[i][j]*p)%a

print(sum(dp[n-1])%a)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
ans = 0
mem = []
for x in mempow(M-1,N-1):
    mem.append(x)
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(1,K+2):
        ans = (ans + (comb(N-1,i-1)*M*mem[N-i])) % 998244353
print(ans)