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:
n,m,k=map(int,input().split())
mod=998244353
ans=0
def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk
for i in range(k+1):
    ans+=m*comb(n-1,i)*(m-1)**(n-1-i)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans *= x
            ans%=mod
        x*=x
        x%=mod
        n = n>>1
    return ans

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

f,invf=[1,1],[1,1]
for i in range(2,N):
    f.append(f[i-1]*i)
    invf.append(pow(f[i],MOD-2,MOD))
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%MOD
for i in range(K+1):
    ans+=M*c[N-i-1]*f[i]*invf[i]
    ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans *= x
            ans%=mod
        x*=x
        x%=mod
        n = n>>1
    return ans

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

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

Submission status: Wrong Answer

Solution code:
def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans *= x
            ans%=mod
        x*=x
        x%=mod
        n = n>>1
    return ans

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

ans=0
f=[1]*(N+1)
for i in range(1,N+1):
    f[i]=f[i-1]*i
for i in range(K+1):
    ans+=M*pow(M-1,N-K-1,MOD)*int(f[N-1]//f[N-i-1]//f[i])
    ans%=MOD
print(ans)

Submission status: Wrong Answer

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

lst=[0]+[1]
for i in range(2,n+10):
  lst.append((lst[-1]*i)%mod)

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx


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


print(ans)

Submission status: Wrong Answer

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

lst=[0]+[1]
for i in range(2,n+10):
  lst.append((lst[-1]*i)%mod)

def combinations(n,r):
  xxx=lst[n]
  xxx*=pow(lst[n-r],mod-2,mod)
  xxx%=mod
  xxx*=pow(lst[r],mod-2,mod)
  xxx%=mod

  return xxx


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


print(ans)

Submission status: Wrong Answer

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

lst=[m]

for i in range(n-1):
  lst.append((lst[-1]*(m-1))%mod)

lst.reverse()

ans=sum(lst[:k+1])%mod


print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
mod = 998244353
class mint:

    def __init__(self, x=0):
        self.x = x.x if isinstance(x, mint) else x % mod

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: mint(self.x + mint(other).x)
    __sub__ = lambda self, other: mint(self.x - mint(other).x)
    __mul__ = lambda self, other: mint(self.x * mint(other).x)
    __pow__ = lambda self, other: mint(pow(self.x, mint(other).x, mod))
    
    def inv(self):
        return mint(pow(self.x, mod-2, mod))

    __truediv__ = lambda self, other: mint(self.x * mint(other).inv())
    __floordiv__ = lambda self, other: mint(self.x // mint(other).x)
    __radd__ = lambda self, other: mint(other + self.x)
    __rsub__ = lambda self, other: mint(other - self.x)
    __rpow__ = lambda self, other: mint(pow(other, self.x, mod))
    __rmul__ = lambda self, other: mint(other * self.x)
    __rtruediv__ = lambda self, other: mint(other * mint(other).inv())
    __rfloordiv__ = lambda self, other: mint(other // self.x)

    __lt__ = lambda self, other: self.x < mint(other).x
    __gt__ = lambda self, other: self.x > mint(other).x
    __le__ = lambda self, other: self.x <= mint(other).x
    __ge__ = lambda self, other: self.x >= mint(other).x
    __eq__ = lambda self, other: self.x == mint(other).x
    __ne__ = lambda self, other: self.x != mint(other).x


class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fact = [mint(1)]*(n+1)
        self.ifact = [mint(1)]*(n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1] * i
        self.ifact[-1] = self.fact[-1].inv()
        for i in range(n-1, 0, -1):
            self.ifact[i] = self.ifact[i+1] * (i+1)
    
    def combination(self, n, r):
        ret = self.fact[n] * self.ifact[r] * self.ifact[n-r]
        if ret >= r:
            return ret
        else:
            return 0
    
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n)
    ans = mint()
    mex = [mint()]*(k+1)
    mex[0] = pow(m-1,n-k-1,mod)
    # inv(m-1)だとおそらく計算誤差が生じる。
    for i in range(1,k+1):
        mex[i] = mex[i-1]*(m-1)
    mex = mex[::-1]
    for i in range(k+1):
        ans += c.combination(n-1, i)*mex[i]
    ans *= m
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 998244353

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

def comb(n, r, mod):
    if r > n-r:
        r = n - r
    
    res_X = 1
    for i in range(n-r+1, n+1):
        res_X = (res_X * i)%mod
    
    res_Y = 1
    for i in range(1, r+1):
        res_Y = (res_Y * i)%mod
    
    return (res_X * pow(res_Y, mod-2, mod))%mod

ans = 0
mm_1 = M
if K < (N-1):
    for _ in range(N-K-2):
        mm_1 = (mm_1 * (M-1))%MOD


for k in range(K, -1, -1):
    c = comb(N-1, k, MOD)
    mm_1 = (mm_1 * (M-1)) % MOD
    
    ans += c * mm_1
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353

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

def comb(n, r, mod):
    if r > n-r:
        r = n - r
    
    res_X = 1
    for i in range(n-r+1, n+1):
        res_X = (res_X * i)%mod
    
    res_Y = 1
    for i in range(1, r+1):
        res_Y = (res_Y * i)%mod
    
    return (res_X * pow(res_Y, mod-2, mod))%mod

ans = 0
mm_1 = M
for _ in range(N-K-2):
    mm_1 = (mm_1 * (M-1))%MOD


for k in range(K, -1, -1):
    c = comb(N-1, k, MOD)
    mm_1 = (mm_1 * (M-1)) % MOD
    
    ans += c * mm_1
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
dp = [0 for _ in range(K + 1)]
mod = 998244353
dp[0] = M
for n in range(N - 1):
    tmp = []
    for i in range(K + 1):
        if i > 0:
            v = (dp[i - 1] + (dp[i] * (M - 1))) % mod
            tmp.append(v)
        else:
            v = (dp[i] * (M - 1)) % mod
            tmp.append(v)
    dp = tmp
print(sum(dp[:K + 1]))

Submission status: Wrong Answer

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

def comb(n,k,mod):
    nCk = 1

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
 
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

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

Submission status: Wrong Answer

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

def comb(n,k,mod):
    nCk = 1

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
 
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk
for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    print(a,b)
    ans += a*b
ans *= m
print(ans%mod)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
g=998244353
r=pow(m-1,n-1,g)
p=r
for i in range(1,k+1):
    r=(r*(n-i)*pow((m-1)*i,g-2,g))%g
    p=(p+r)%g
print((m*p)%g)

Submission status: Wrong Answer

Solution code:

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

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


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

print(ans)

Submission status: Wrong Answer

Solution code:
p = 998244353
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    if m%2==1:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,M,K = map(int,input().split())
A = [1 for _ in range(N+1)]
for i in range(2,N+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+1)]
B[N] = pow(A[N],p-2)
for i in range(N-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p
m = M
for i in range(N-1):
    m = (m*(M-1))%p
tot = m
for k in range(1,K+1):
    m = (m*pow(M-1,p-2))%p
    cnt = (A[N-1]*B[k]*B[N-1-k])%p
    cnt = (cnt*m)%p
    tot = (tot+cnt)%p
print(tot)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())
    MOD = 998244353
    
    fact = [1]*(N+1)
    factinv = [1]*(N+1)
    for i in range(1,K+1):
        fact[i] = fact[i-1]*i % MOD
        factinv[i] = pow(fact[i], MOD-2, MOD)
    def comb(n, k):
        return fact[n] * factinv[k] * factinv[n-k] % MOD

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

    print(ans%MOD)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())

    c = [0]*(K+1)
    def comb(k):
        if k == 0:
            ans = 1
        else:
            ans = c[k-1]*(N-k+1)//k
        c[k] = ans
        return ans

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

    print(ans%998244353)

main()

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
MOD = 998244353
MAX_N = 10**6
fac = [0]*(MAX_N)
fac_inv = [0]*(MAX_N)
fac[0] = 1
for i in range(MAX_N-1):
    fac[i+1] = fac[i]*(i+1) % MOD
fac_inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(MAX_N-2, -1, -1):
    fac_inv[i] = fac_inv[i+1]*(i+1) % MOD


def nCk(n, k):
    return fac[n] * fac_inv[k] * fac_inv[n-k]


ans = 0
for k in range(K+1):
    temp = M*nCk(N-1, k)*pow(M-1, N-K-1, MOD) % MOD
    ans += temp
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    m1 = [None]*(n+1)
    kaizyo = [None]*(n+1)
    nm1 = 1
    kai = 1
    for i in range(n+1):
        m1[i] = nm1
        nm1 *= m-1
        nm1 %= mod
        kaizyo[i] = kai
        kai *= i+1
        kai %= mod
    
    def comb(a, b):
        return (kaizyo[a]*fermat(kaizyo[a-b]*kaizyo[b], mod))%mod

    for i in range(k+1):
        ans += m*m1[n-k-1]*comb(n, k)
        ans %= mod
    
    print(ans)

def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N,M,K = list(map(int, input().rstrip().split()))
#-----
mod = 998244353

a = M * pow(M-1, N-1, mod)
inv_M1 = pow((M-1), mod-2, mod )  # inverse element

comb = 1
ans = 0

for i in range(K+1):
    ans += ( comb * a )
    ans %= mod
    
    # Calculate variables for next step
    a *= inv_M1
    a %= mod
    
    inv_i1 = pow(i+1, mod-2, mod)  # inverse element
    comb *= ( (N-1-i) * inv_i1 )
    comb %= mod


print(ans)

Submission status: Wrong Answer

Solution code:
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**8)

MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD) if M>1 else 0
ans = 0
tmp = pow(M-1,N-1,MOD) if M>1 else 0
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
K = min(K,N-1)
dp = [[0 for i in range(N+1)] for i in range(K+1)]
dp[0][0] = 1

for i in range(1,N+1):
  for k in range(K+1):
    if i == k+1:
      dp[k][i] = M**i
    if k == 0:
      dp[k][i] = M*((M-1)**(i-1))
    else:
      dp[k][i] = dp[k-1][i-1] + dp[k-1][i] + dp[k][i-1]

print(dp[-1][-1] % 998244353)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    kai = [None]*n
    m1 = [None]*n
    num = 1
    ki = 1
    for i in range(n):
        m1[i] = num
        num *= m-1
        num %= mod
        kai[i] = ki
        ki *= i+1
        ki %= mod
    
    def comb(a, b):
        return kai[a]*fermat(kai[b]*kai[a-b], mod)
        
    ans = 0
    for i in range(k+1):
        ans += m*m1[n-1-k]*comb(n-1, i)
        ans %= mod
    print(ans)
        
def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    kai = [None]*n
    m1 = [None]*n
    num = 1
    ki = 1
    for i in range(n):
        m1[i] = num
        num *= m-1
        num %= mod
        kai[i] = ki
        ki *= i+1
        ki %= mod
    
    def comb(a, b):
        return kai[a]*fermat(kai[b]*kai[a-b], mod)
        
    ans = m
    for i in range(1, k+1):
        ans += m*m1[n-1-k]*comb(n-1, k)
        ans %= mod
    print(ans)
        
def fermat(x, p):
    """
    1/x (mod p) を返す
        x**(p-1) ≡ 1    [if gcd(x, p) == 1]
        x**(p-2) ≡ 1/x
        繰返し二乗法 
            ex: x**50  = (x**25)**2
                x**25  = (x**12)**2 * x
                x**12  = (x**6)**2
                x**6   = (x**3)**2
    """
    times = []
    mod = p
    p -= 2
    while p > 1:
        times.append(p%2)
        p //= 2
    x %= mod
    out = x
    for i in times[::-1]:
        if i:
            out = (x*pow(out, 2, mod))%mod
        else:
            out = pow(out, 2, mod)
    return out

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

list_size = 2*10**5 + 4

f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod

ans = 0
for k in range(K+1):
    if N-2*k < 0:
        continue
    ans += (comb(N-1, k, mod) * M *pow(M-1, N-k-1, mod))%mod
ans %= mod
print(ans)

Submission status: Wrong Answer

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

list_size = 2*10**5 + 4

f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod

ans = 0
for k in range(K+1):
    if N-2*k < 0:
        continue
    ans += (comb(N-k, k, mod) * M *pow(M-1, N-k-1, mod))%mod
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:

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

fact = [0] * (N+1)
fact_inv = [0] * (N+1)
inv = [0] * (N+1)

fact[0] = fact[1]  = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD # //で良いのかな?
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def combo(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % MOD) % MOD

def main():
    res = 0
    if N == 1:
        print(M)
        return 
    ms = pow(M-1, N-1-K, MOD)
    for i in range(min(N-1, K+1)):
        res += M*combo(N-1, i)*ms
        res %= MOD

        ms *= (M-1)
        ms %= MOD
    print(res%MOD)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

A = list(map(int, input().split()))
MOD = 998244353
N = A[0]
M = A[1]
K = A[2]

s = (M*(M-1)**(N-1))
s = ModInt(s)
D = (M*(M-1)**(N-1))
D = ModInt(D)
for k in range(1,K+1):
    s = s*(N-k)/k/(M-1)
    D += s

print(D)

Submission status: Wrong Answer

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

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

nCn = 1
#print(type(nCn))
for i in range(1,k+1):
    
    nCn = (nCn*(n-i))//i
    nCn = nCn%mod
    #print(type(nCn))
    
    ans += (((m*(nCn))%mod)*(pow(m-1,n-1-i,mod)))%mod
    ans = ans%mod
#print(type(ans))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    if m == 1:
        print(1)
        return
        
    ans = 0
    m1 = [None]*n
    kai = [None]*n
    mi = 1
    ki = 1
    for i in range(n):
        m1[i] = mi
        mi *= m-1
        mi %= mod
        kai[i] = ki
        ki *= (i+1)
        ki %= mod
        
    def comb(a, b):
        return kai[a]*fermat(kai[a-b]*kai[b], mod)
        
    def fermat(x, p):
        """
        1/x (mod p) を返す
            x**(p-1) ≡ 1    [if gcd(x, p) == 1]
            x**(p-2) ≡ 1/x
            繰返し二乗法 
                ex: x**50  = (x**25)**2
                    x**25  = (x**12)**2 * x
                    x**12  = (x**6)**2
                    x**6   = (x**3)**2
        """
        times = []
        mod = p
        p -= 2
        while p > 1:
            times.append(p%2)
            p //= 2
        x %= mod
        out = x
        for i in times[::-1]:
            if i:
                out = (x*pow(out, 2, mod))%mod
            else:
                out = pow(out, 2, mod)
        return out
               
    if k == 0:
        print((m*comb(n-1, 0)*m1[n-1])%mod)
        return
    for i in range(k+1):
        ans += m*comb(n-1, i)*m1[n-i-1]
        ans %= mod
    print(ans)

    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    if m == 1:
        print(1)
        return
    ans = 0
    m1 = [None]*n
    kai = [None]*n
    mi = 1
    ki = 1
    for i in range(n):
        m1[i] = mi
        mi *= m-1
        mi %= mod
        kai[i] = ki
        ki *= (i+1)
        ki %= mod
        
    def comb(a, b):
        return kai[a]*fermat(kai[a-b]*kai[b], mod)
        
    def fermat(x, p):
        """
        1/x (mod p) を返す
            x**(p-1) ≡ 1    [if gcd(x, p) == 1]
            x**(p-2) ≡ 1/x
            繰返し二乗法 
                ex: x**50  = (x**25)**2
                    x**25  = (x**12)**2 * x
                    x**12  = (x**6)**2
                    x**6   = (x**3)**2
        """
        times = []
        mod = p
        p -= 2
        while p > 1:
            times.append(p%2)
            p //= 2
        x %= mod
        ans = x
        for i in times[::-1]:
            if i:
                ans = (x*pow(ans, 2, mod))%mod
            else:
                ans = pow(ans, 2, mod)
        return ans
                
    for i in range(k+1):
        ans += m*comb(n-1, i)*m1[n-i-1]
        ans %= mod
    print(ans)

    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    if m == 1:
        print(1)
        return
    ans = 0
    for i in range(k+1):
        ans += m*comb(n-1, i)*pow(m-1, n-i-1, mod)
        ans %= mod
    print(ans)

def comb(a, b):
    numerator = 1
    denominator = 1
    if a-b < 0:
        return None
    b = min(a-b, b)
    for i in range(a-b+1, a+1):
        numerator *= i
    for i in range(1, b+1):
        denominator *= i
    return numerator//denominator

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N_MAX = 10**6
MOD = 998244353
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


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


def main():
    com_init()
    n, m, k = map(int, input().split()) 
    ans = 0
    for i in range(0,k+1):
        ans += m * com(n-1,i) * pow_k(m-1,n-k-1)
    print(ans%MOD)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    print(n, m)
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, k = map(int, input().split())
    MAX = 998244353
    kaizyos = [None]*n
    ki = 1
    kaizyos[0] = ki
    combs = [None]*n
    numerators = list(range(n-1, 0, -1))
    denominators = list(range(1, n))
    combs[0] = 1
    co = 1
    for i, (nu, de) in enumerate(zip(numerators, denominators), 1):
        co *= nu
        co //= de
        co %= MAX
        combs[i] = co
    # for i in range(1, n):
    #     ki *= i
    #     kaizyos[i] = ki
    # def comb(a, b):
    #     return (kaizyos[a]//(kaizyos[b]*kaizyos[a-b]))%MAX
    ruizyos = [None]*(k+1)
    ruizyo = 1
    for i in range(n-1-k):
        ruizyo *= m-1
        ruizyo %= MAX
    ruizyos[k] = ruizyo
    for i in range(n-k, n):
        ruizyo *= m-1
        ruizyo %= MAX
        ruizyos[-i+n-1] = ruizyo
    pattern = lambda x: (combs[x]*m*ruizyos[x])%MAX
    ans = 0
    for i in range(k+1):
        ans += pattern(i)
        ans %= MAX
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def kaizyo(x):
        ans = 1
        for i in range(2, x+1):
            ans *= i
        return ans

    n, m, k = map(int, input().split())
    MAX = 998244353
    ans = 0
    kaizyos = [None]*n
    ki = 1
    kaizyos[0] = ki
    for i in range(1, n):
        ki *= i
        ki %= MAX
        kaizyos[i] = ki
    def comb(a, b):
        return kaizyos[a]//(kaizyos[b]*kaizyos[a-b])
    ruizyos = [None]*(k+1)
    ruizyo = 1
    for i in range(n-1-k):
        ruizyo *= m-1
        ruizyo %= MAX
    ruizyos[k] = ruizyo
    for i in range(n-k, n):
        ruizyo *= m-1
        ruizyo %= MAX
        ruizyos[-i+n-1] = ruizyo
    pattern = lambda x: (comb(n-1, x)*m*ruizyos[x])%MAX
    for i in range(k+1):
        ans += pattern(i)
        ans %= MAX
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

c = 1
answer = M * pow(M-1, N-1,mod)

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

Submission status: Wrong Answer

Solution code:
from scipy.special import comb

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

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

print(answer)

Submission status: Wrong Answer

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

mod = 998244353

d = {0 : M}
for i in range(1, K+1):
    d[i] = 0


for _ in range(N-1):
    for k, v in d.items():
        tmp = d
        if k < K:
            tmp[k+1] = (d[k] + d[k+1] * (M-1)) % mod
        tmp[0] = d[0] * (M-1)
        d = tmp

answer = 0
for k, v in d.items():
    answer += v
print(answer % mod)

Submission status: Wrong Answer

Solution code:
import sys
def combmod_pre(N, p):
    '''
    sample usage:
        p = 10**9+7
        N = 10**6
        fact, finv = combmod_pre(N, p)
        combmod(n, r, p)
    '''
    fact = [1, 1]
    finv = [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)
        finv.append((finv[-1] * inv[-1]) % p)
    return (fact, finv)
def combmod(n, r, fact, finv, p):
    '''
    sample usage:
        combmod(3000, 1000, fact, finv, p)
            p is a same value of combmod_pre's argument
            fact, finv is return value of combmod_pre
    '''
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % p

def main():
    mod=998244353
    N,M,K=tuple(map(int,sys.stdin.readline().split()))
    fact,finv=combmod_pre(N,mod)
    dp=[]
    for _ in [0]*(N+1):
        dp.append([0 for _ in [0]*(K+1)])
    dp[1][0]=M
    for i in range(2,N+1):
        dp[i][0]=dp[i-1][0]*(M-1)%mod
        for j in range(1,K+1):
            dp[i][j]=(dp[i][j-1]+combmod(i-j,j,fact,finv,mod)*dp[i-j][0])%mod
    print(dp[N][K])
if __name__=='__main__':main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m, k = [int(t) for t in open(0).read().split()]
mod = 998244353
mem = [0] * max(k + 3, n + 1)
for i in range(k + 2):
    mem[i] = pow(m, i, mod)
mem[k + 2] = (pow(m, k + 2, mod) + mod - m) % mod
for i in range(k + 3, n + 1):
    mem[i] = (m * mem[i - 1] - (m - 1) * mem[i - k - 2]) % mod
print(mem[n])

Submission status: Wrong Answer

Solution code:

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

c = [0] * n
c[0] = 1
for i in range(n-1):
    c[i+1] = (c[i] * (n-i)) // (i+1)

sum = 0
for i in range(k+1):
    sum = (sum + (m * c[i] * ((m-1) ** (n-1-i)))) % mod

print(sum)