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:
class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m,k = input().split()
n = int(n)
m = int(m)
k = int(k)
a = k
if a > n//2: 
  a = k-n//2
ans = 1
u = n
b = 1
for i in range (a):
  ans *= u
  ans = ans//b
  u = u-1
  b = b +1
print(ans % 998244353)

Submission status: Wrong Answer

Solution code:
def comb(n,r,mod=998244353):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

N, M, K = map(int, input().split())
ans = 0
for k in range(1, K+1):
    ans += comb(N, k)*M*((M-1)**(k-1))

Submission status: Wrong Answer

Solution code:
import math


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def comb(n, r):
    if n < r:
        return 1
    mf = math.factorial
    return mf(n) // (mf(n - r) * mf(r))


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

Submission status: Wrong Answer

Solution code:
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

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

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

Submission status: Wrong Answer

Solution code:
def fac(a,b,p=998244353):
  t=a
  for i in range(a+1,b+1):
    t = (t*i)%p
  return t

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

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

for i in range(0,K+1):
  u=N-i
  s=u//2
  t=u-s
  k = (pow(M,s,p)*pow(M-1,t,p)*fac(1,i+1))%p
  #print(i,k)
  ans += k
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

MOD = 998244353
n,m,k = MI()

s = [1]
for i in range(2, n):
    s.append(s[-1]*i%MOD)
if m == 1 and k < n-1:
    print(0)
    exit(0)
elif m == 1 and k == n-1:
    print(1)
    exit(0)
elif k == n-1:
    print(pow(m, n, MOD))
ans = m*pow(m-1, n-1, MOD)%MOD
for i in range(1, k+1):
    tmp = m*pow(m-1, n-1-i, MOD)*s[n-2]*pow(s[n-2-i], MOD-2, MOD)*pow(s[i-1], MOD-2, MOD)
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def mul(a, b):
    global mod
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    global mod
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    
    global mod
    return mul(a, power(b, mod-2))

mod=998244353

#print(div(6, 3)) # => 2
#print(div(6,1))
#print(div(10, 2)) # => 5
#print div(3000000000, 2) # => 499999993
#print div(45000000000, 5) # => 999999944
#print div(4000000000, 2000000000) # => 2
#print div(45000000000, 5000000000) # => 9



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

kaijo=[1]
wari=[1]
now=1
for i in range(1,n):
    now*=i
    now%=mod
    kaijo.append(now)
    wari.append(div(1,now))

#print(wari)
ruijo=[1]
now=1

for i in range(n):
    now*=(m-1)
    now%=mod
    ruijo.append(now)

ans=[]

for i in range(n):
    #temp=div(kaijo[n-1],kaijo[i])
    #temp=div(temp,kaijo[n-i-1])
    temp=kaijo[n-1]*wari[i]*wari[n-i-1]
    temp%=mod
    ans.append((temp*ruijo[n-i-1]*m)%mod)

kotae=0

for i in range(k+1):
    kotae+=ans[i]

print(kotae)

Submission status: Wrong Answer

Solution code:
import math
n,m,k=map(int,input().split())
ans=(m-1)**n
ans=ans%998244353
for i in range(1,k+1):
    ans+=(math.factorial(n-1)//(math.factorial(n-1-i))*math.factorial(i))*((m-1)**(n-i))
    ans=ans%998244353
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import math

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

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

    cnt = 0
    for i in range(k + 1):
        tmp = m * ((m - 1) ** (n - i)) * combinations_count(n - 1, i)
        cnt += tmp

    print(cnt % div)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 2 1"""
        output = """6"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """100 100 0"""
        output = """73074801"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from scipy.special import comb
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

N, M, K = MAP()

ans = 0
for i in range(0, K+1):
	#c = factorial(N-1)//factorial(N-i-1)//factorial(i)
	c = comb(N-i-1, i, exact=True)
	c %= mod
	p = M * ((M-1)**(N-K-1))
	p %= mod
	cp = (c*p)%mod
	ans += cp

print(ans%mod)

Submission status: Wrong Answer

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

c = 1

for k in range(K+1):

  out += M * pow(M-1, N-k-1, mod) * c
  c *= N - k
  c /= k + 1
  print(out)
  out %= mod
print(out)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n,m,k=map(int,input().split())
#n個のブロック
#m個の色
#k組以下
mod = 998244353
#なにこれ
#このmodは草
#場合の数の問題かよ
# m!は使いそうだから, 作るか.

#最初は0として, m-1色までを塗ろうと思う.
#全部塗るは m^n か？
#となりあうのが k組以下だから…
#となりあうは, 1個まとめて考えてしまえばいいが,
#となりあうものをx, となりあわないをyとする.
#(n,m,k) = (n-1,m,k-1) (n-1)C(k-1) =... = (n-k,m,0) (n-1)C(k-1) (n-2)C(k-2) .... 1 = (n-k,m,0) (n+1)Ck

#(n-k, m, 0) は違う色をぬっていく
#最初はm, 次m-1, m-1 ....
# = m * (m-1)^(n-k-1)
#(n+1)Ck

def combina(n, k):
	samu = 1
	unta = 1
	for i in range(n-k+1, n+1):
		samu = samu * i
	for i in range(1, k+1):
		unta = unta * i
	return (samu//unta)%mod

def power(a,b):
	ans=1
	for i in range(len(bin(b))-2):
		if (b>>i)&1 == 1:
			unta=a %mod
			for _ in range(i):
		  		unta=unta**2 %mod
			ans=ans*unta %mod
	return ans

print(((m*power(m-1, n-k-1))*combina(n, k))%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # 添字を付け加える系DP．ナップサックとかはこの一種
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3
    
    N,M,K=map(int,input().split())
    I=N
    J=M
    # dp[i][j][k]:=i番目のブロックでj種類目を用いたときk組以下となる通り数
    dp = [[[0]*(K+1) for _ in range(J)] for _ in range(I+1)]
    # 初期条件
    for j in range(J):
        dp[0][j][0]=1
    # ループ
    for i in range(1, I+1):
        for j in range(J):
            for k in range(1,K+1):
                for l in range(J):
                    if l!=j:
                        dp[i][j][k] += dp[i-1][l][k-1]
    print(dp[I][J-1][K])
    
resolve()

Submission status: Wrong Answer

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

fact = [1,1]
finv = [1,1]
inv = [0,1]

for i in range(2,max(n,m)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
f = pow(m-1,mod-2,mod) 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

x = m%mod

a = pow(m-1,n-1,mod)
x = (a*x)%mod

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

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



n,m,k = mi()

dp = [[1] * (k+1) for i in range(n)]


# dp[:,0] = 1

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

ans = 0

for i in range(k+1):
    # print(n,i)
    ans += dp[n-1][i]*m*(m-1)**(n-1-i)%998244353

print(ans)

Submission status: Wrong Answer

Solution code:
def comb(n,r,mod=998244353):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

N, M, K = map(int, input().split())
ans = 0
for k in range(1, K+1):
    ans += comb(N, k)*M*(M-1)**(k-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

MOD = 998244353

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = M * pow(M-1, N-1, MOD)

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

print(ans%MOD)

Submission status: Wrong Answer

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

ans = 0
for i in range(k+1):
  ans += pow(m,n-i,MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
mod=998244353
n,m,k=map(int,input().split())
dp=[[0 for _ in range(n+1)] for _ in range(k+1)]
for i in range(1,n+1):
    dp[0][i]=m*pow(m-1,i-1,mod)

for c in range(1,k+1):
    for b in range(n+1):
        dp[c][b]=(dp[c][b-1]+(m-1)*dp[c-1][b-1])%mod
print(dp[k][n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m,k=list(map(int,input().split()))
ans=0
curr=1
t=m-n+k+1
for i in range(n-k):
    curr=(curr*t)%998244353
    t+=1
t=m-n+k+1   
ans=max(0,curr)
for i in range(k+1):
    t-=1
    if t>0:
        curr=(curr*t)%998244353
    if curr>0:
        ans=(ans+curr)%998244353
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, M, K = map(int, input().split())
ans = 0
for k in range(K+1):
    n = N - k
    a = M * (M-1)**(n-1)
    b = n**k // math.factorial(k)
    ans += a * b
    ans %= 998244353
print(ans)

Submission status: Wrong Answer

Solution code:
n , m , k = map(int,input().split())
mod = 998244353
ans = 0
buns = 1
bunb = 1
pow(bunb,mod-2,mod) 
for i in range(k+1):
    buns *= (n-1)-i
    buns %= mod
    bunb *= i+1
    bunb_inv = pow(bunb,mod-2,mod)
    d = (buns * bunb_inv) % mod
    ans += m*d*pow(m-1,n-1-i,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
N,M,K=map(int,input().split())
ans=0

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

if M == 1:
    print('1')
    sys.exit()

for i in range(K+1):
    cc = combinations_count(N-1, i)
    if cc >= 998244353:
        cc = cc%998244353
    a=cc*M
    for _ in range(N-2-i+1):
        a *= M-1
        if a >= 998244353:
            a = a%998244353
    ans += a
    #ans += cc*M*( (M-1)**(N-2-i+1) )
    print(i,cc,ans)
    if ans >= 998244353:
        ans = ans%998244353
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

big=998244353
cnt=(n**m)%big

for i in range(k,n+1):
	cnt-=((n-i)**m)%big
	
print(cnt%big)

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod = 998244353

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

Submission status: Wrong Answer

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

c = 1

for k in range(K+1):

  out += M * pow(M-1, N-k-1, mod) * c
  c *= N - k
  c *= k + 1
  out %= mod
print(out)

Submission status: Wrong Answer

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

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

Submission status: Wrong Answer

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

ans = 0
for i in range(k+1):
  ans += pow(m,n-1,MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
MOD = 998244353
N,M,K = map(int,input().split())
dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(1,K+2):
    dp[i][i-1] = M
for i in range(1,N+1):
    dp[i][0] = M * pow(M-1,i-1,MOD)
for i in range(3,N+1):
    MIN = min(K,i-1)
    for j in range(1,K):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]*(M-1)
        dp[i][j] = dp[i][j] % MOD
ans = 0
for i in range(K+1):
    ans += dp[N][i]
    ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    MOD = 998244353
    n,m,k = map(int,stdin.readline().rstrip().split())
    dp = [[0]*(k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(k+1):
        dp[1][i] = m

    for i in range(1,n):
        dp[i+1][0] = dp[i][0]*(m-1)%MOD

    for i in range(2,n):
        for j in range(k):
            dp[i+1][j+1] = (dp[i][j+1]*(m-1) + dp[i][j]*m)%MOD
    
    print(dp[n][k])
main()

Submission status: Wrong Answer

Solution code:
def cmb(n, k, mod, fac, ifac):    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

n,m,k = map(int,input().split())
f=[0 for _ in range(n)]
mod=998244353
for i in range(n):
    if i == 0:
        f[i]=m
    else:
        f[i]=(f[i-1]*(m-1))%mod
c=1
ans=0
if k==0:
    print(f[n-1])
    exit()
fac, ifac = make_tables(mod, n)
for i in range(k+1):
    ans+=f[n-1-i]*c
    ans%=mod
    #print(f[n-1-i],c)
    if i==0:
        c=n-1
    else:
        c=cmb(n-i-1,i+1,mod,fac,ifac)

print(ans%mod)

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
from itertools import combinations
N, M, K = map(int,input().split())

lp = [i for i in range(N-1)]
#lc = list(combinations(lp, 2))
N_1Cl = 1
#どこも隣り合ってはいけない場合 (l = 0)
ans = M * (M-1)**(N-1)
ans = ans % 998244353

#どこかが隣り合う場合(l組)
#n = M * (M-1)**(N-1-l) * ((((((N-1)Cl)))))
for l in range(1, K+1):
    #print('l:{}'.format(l))
    N_1Cl = int(N_1Cl * (N - l) / (l))
    N_1Cl = N_1Cl % 998244353
    #print('N-1 C l:{}'.format(N_1Cl))
    n = M #* (M-1)**(N-1-l) * N_1Cl
    n = n %  998244353
    p = (M-1) ** (N-1-l) % 998244353
    n = n * p
    n = n %  998244353
    n = n * N_1Cl
    n = n %  998244353
    ans = ans + n
    ans = ans % 998244353



ans = ans % 998244353
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
INF = float("inf")
MOD = 998244353
# ----------

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD = 998244353

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

combs = [1]
mbs = [1]

for n in range(1, N):
    comb = combs[-1]
    mb = mbs[-1]

    mbs.append((mb * (M - 1)) % MOD)
    combs.append(int(comb * (N - n) / n) % MOD)

res = 0
for k in range(0, K + 1):
    res += (M * mbs[N - k - 1] * combs[k]) % MOD

print(res % MOD)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
res=0
for i in range(k+1):
	res+=m*((m-1)**(n-i-1))*((n-i)**i)
	res%=998244353

print(res)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int, input().split())
mod = 998244353
#dp[i][j]:i個まで、j組
dp = [[0]*(k+1) for _ in range(n+1)]
dp[1][0]=m
for i in range(2,n+1):
    dp[i-2]=[]
    for j in range(0,k+1):
        if (j>0):
            dp[i][j] = dp[i-1][j]*(m-1) + dp[i-1][j-1]
            dp[i][j] %= mod
        else:
            dp[i][j] = dp[i-1][j]*(m-1)
            dp[i][j] %= mod

print(dp)

print(sum(dp[n])%mod)

Submission status: Wrong Answer

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

# factorial(mod) -- START --
def factorialMod(n,m):
  ret=n
  for i in range(2,n):
    ret*=i
    ret%=m
  return ret
# factorial(mod) --- END ---

# nCr(mod) -- START --
# n!/r!(n-r)!
def nCrMod(n,r,m):
  # need lib of factorial(mod)
  n_fac=factorialMod(n,m)
  a=factorialMod(r,m)
  b=factorialMod(n-r,m)

  denom_fac_inv=pow(a*b,m-2,m)
  return n_fac*denom_fac_inv%m
# nCr(mod) --- END ---

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 = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
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)

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

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

  sm=[]
  _ans=ans
  for i in range(1,k+1):
    x=cmb(n-1,i,mod)
    x*=ans_list[n-i]
    x*=m
    x%=mod
    ans+=x
    ans%=mod

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:

INF = float("inf")
MOD = 998244353
# ----------

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def calc():
    dp = [[0] * (N + 1) for j in range(K + 1)]

    dp[0][0] = 1
    for i in range(1, K + 1):
        for j in range(N + 1):
            if j - i >= 0:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % MOD
            else:
                dp[i][j] = dp[i - 1][j]

    return dp

if __name__ == '__main__':
    MOD = 998244353
    N, M, K = map(int, input().split())

    dp = calc()
    ans = 0
    for k in range(K+1):
        if k == 0:
            ans += (M * pow(M - 1, N - 1, MOD)) % MOD
        else:
            ans += (dp[k][N] * (N-k) * M * pow(M - 1, N - 1 - k, MOD)) % MOD
        #print(k, ans, dp[k][N])

    print(ans % MOD)

Submission status: Wrong Answer

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

fact = [1,1]
finv = [1,1]
inv = [0,1]

for i in range(2,max(n,m)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
f = pow(m-1,mod-2,mod) 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

x = m%mod

a = pow(m-1,n-1,mod)
x = (a*x)%mod

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

Submission status: Wrong Answer

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

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

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

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

if k==n-1:
  print(m%mod)
  exit()

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
n,m,k=map(int,input().split())
w=998244353
t=0
c=1
b=m*((m-1)**(n-1))%w
g=power_func(m-1,w-2,w)
for i in range(k+1):
    t += c * b
    t %= w
    if i<k:
        c*=(n-1-i)
        c*=power_func(i+1,w-2,w)
        c%=w
        b*=g
        b%=w

print(t)

Submission status: Wrong Answer

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

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

Submission status: Wrong Answer

Solution code:
# n個のブロック,色 m種類, 隣り合うブロックの組であって同じ色で塗られている組がk組以下
n, m, k = map(int, input().split())
MOD = 998244353
ans = 0
for i in range(k+1):
  a = (m ** (i+1)) % MOD
  b = ((m-1) ** (n-1-i)) % MOD
  ans += (a * b) % MOD
  
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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