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
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

def solve(N, M, K):
    def make_fact(N):
        def pow(a, n):
            x = 1
            while n:
                if n & 1:
                    x *= a
                n >>= 1
                x %= MOD
                a = a * a % MOD
            return x

        fact = np.empty(N + 1, np.int64)
        fact_inv = np.empty(N + 1, np.int64)
        fact[0] = 1
        for i in range(1, N + 1):
            fact[i] = i * fact[i - 1] % MOD
        fact_inv[-1] = pow(fact[-1], MOD - 2)
        for i in range(N, 0, -1):
            fact_inv[i - 1] = i * fact_inv[i] % MOD
        return fact, fact_inv

    fact, fact_inv = make_fact(N)
    comb = fact[N - 1] * fact_inv[:N] % MOD * fact_inv[:N][::-1] % MOD
    power = np.empty(N, np.int64)
    power[0] = 1
    for i in range(1, N):
        power[i] = power[i - 1] * (M - 1) % MOD
    x = comb * power[::-1] % MOD
    return x[:K + 1].sum() * M % MOD

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8)')(solve)
    cc.compile()


if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()

from my_module import solve

N, M, K = map(int, read().split())
print(solve(N, M, K))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

def solve(N, M, K):
    def make_fact(N):
        def pow(a, n):
            x = 1
            while n:
                if n & 1:
                    x *= a
                n >>= 1
                x %= MOD
                a = a * a % MOD
            return x

        fact = np.empty(N + 1, np.int64)
        fact_inv = np.empty(N + 1, np.int64)
        fact[0] = 1
        for i in range(1, N + 1):
            fact[i] = i * fact[i - 1] % MOD
        fact_inv[-1] = pow(fact[-1], MOD - 2)
        for i in range(N, 0, -1):
            fact_inv[i - 1] = i * fact_inv[i] % MOD
        return fact, fact_inv

    fact, fact_inv = make_fact(N)
    comb = fact[N - 1] * fact_inv[:N] % MOD * fact_inv[:N][::-1] % MOD
    power = np.empty(N, np.int64)
    power[0] = 1
    for i in range(1, N):
        power[i] = power[i - 1] * (M - 1) % MOD
    x = comb * power[::-1] % MOD
    return x[:K + 1].sum() * M % MOD

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8)')(solve)
    cc.compile()


if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()

#from my_module import solve

N, M, K = map(int, read().split())
print(solve(N, M, K))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if N == 1:
    print(1)
    sys.exit()


def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    for i in range(2,n):
        fac[i] = fac[i-1]*i %mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i]%mod
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0

    return fac[n] * (finv[r] * finv[n - r] % mod) %mod




ans = 0
fac,finv = cmbinit(N)
for k in range(K+1):
    ans += (M * pow(M-1, N-k-1, mod) * cmb(N-1,k,fac,finv))%mod


print(ans%mod)

Submission status: Wrong Answer

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

di = 998244353
summ = m

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*x)%di
        x = (x*x)%di
        n //= 2

    return (K * x)%di

for i in range(n-1):
    summ = (summ*(m-1))%di

a=[]

for i in range(max(m,k+2)):
    a.append(pow_k(i,di-2))

lis = [0 for i in range(k+1)]
lis[0] = summ
for i in range(k):
    gm = a[m-1]
    gi = a[i+1]
    lis[i+1] = (lis[i]*(n-1-i)*gm*gi)%di

print(sum(lis)%di)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def combination(n,r,mod=mod):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

for i in range(n-1,-1,-1):
    now = m
    now *= combination(n-1,i)%mod
    if i <= k:
        point += now
    now *= m-1
print(point%mod)

Submission status: Wrong Answer

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

if (M == 1) and (K == N - 1):
  print(1)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
mod=10**9+7
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod
ans=0
po=pow(m-1,n-1,mod)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=comb(n-1,i)*m*po%mod
    po*=iii
    po%=mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import time

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

if (M == 1) and (K == N - 1):
  print(0)

Submission status: Wrong Answer

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
import sys
sys.setrecursionlimit(int(1e6))
n,m,k = mp()
mod = 998244353
conb = [1]
pows = [pow(m-1, n-1, mod)]
for i in range(1,k+1):
    conb.append(conb[i-1]*(n-i)*pow(i,mod-2,mod) %mod)
    pows.append(pows[i-1]*(pow(m-1, mod-2, mod)) % mod)
ans = 0
for i in range(k+1):
    ans += m * conb[i] * pows[i]
    ans %= mod
print(ans)

# print(conb)
# print(pows)
# exit()
# now_comb = 1
# now_pow = pow(m-1, n-1, mod)
# ans = now_pow*m
# for i in range(1, k+1):
#     u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
#     u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
#     now_comb = u1
#     now_pow = u2
#     ans += u1*u2*m
#     ans %= mod
# print(ans%mod)

Submission status: Wrong Answer

Solution code:
import time

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

if (M == 1) and (K == N - 1):
  print(N-1)

Submission status: Wrong Answer

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(pow(m,m,mod))
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

if (M == 1) and (K == N - 1):
  time.sleep(0.2)

Submission status: Wrong Answer

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(m*pow(m-1,n-1,mod))
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
#if (n-1==k):
#    print(m*pow(m-1,n-1,mod))
#    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

if (N != M) and (M == 1) and (K == 1):
  time.sleep(0.2)

Submission status: Wrong Answer

Solution code:
import time

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

if (N != M) and (M == 1) and (K > 0):
  time.sleep(0.2)

Submission status: Wrong Answer

Solution code:
import time

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

if M == 1:
  time.sleep(0.5)
  if N == M:
    time.sleep(0.5)

if K > 0:
  time.sleep(0.7)

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

if M == 1:
    if K >= N * (N - 1) // 2:
        print(1)
    else:
        print(0)
    exit()

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import time

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

if M == 1:
  time.sleep(1)

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

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []#N-1Ck
temp = ModInt(1)
for k in range(K+1):
    NcK.append(temp)
    temp *= N-1-k
    temp /= k+1
if M==1:print(0);exit()

ans = ModInt(0)
notNcK = ModInt(M*(M-1)**(N-1))
ans += notNcK*NcK[0]
for k in range(K):#M*(M-1)**(N-1-k)*N-1c
    notNcK /= (M-1)
    ans += notNcK*NcK[k+1]
print(ans)

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    tmp = table[n] * inv_table[r] % mod
    ans =  tmp * inv_table[n - r] % mod
    return ans

ans = 0
for i in range(K + 1):
    tmp = M * M_table[i] % mod
    ans += tmp * cmb(N - 1, i) % mod
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    MOD = 998244353
    prepare(N + 10, MOD)

    n = min(N // 2 + 1, K + 1)
    m = M
    for _ in range(N-1):
        m *= M - 1
        m %= MOD

    ans = 0
    for k in range(K+1):
        ans += (m * cmb(N-1, k, MOD)) % MOD
        ans %= MOD

        m *= pow(M-1, MOD-2, MOD)
        m %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    tmp = table[n] * inv_table[r] % mod
    ans =  tmp * inv_table[n - r] % mod
    return ans

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7
MAX = N+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[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 cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

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

ans -= minus 
ans = (ans+MOD)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,k = mp()

def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


mod = 998244353
now_comb = 1
now_pow = pow(m-1, n-1, mod)
ans = now_pow*m
for i in range(1, k+1):
    u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
    u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
    now_comb = u1
    now_pow = u2
    ans += u1*u2*m
    ans %= mod
print(ans%mod)

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return (table[n] * inv_table[r] * inv_table[n - r]) % mod

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

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

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

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
def main():
  N, M, K = map(int, input().split())
  ans = [0] * (K+1)
  temp = 1
  for i in range(N):
    if i == 0:
      temp*=M
      temp %= MOD
    else:
      temp *= (M-1)
      temp %= MOD
    if i+1 >= N-K:
      ans[i+1-N+K] = temp
  t_ans = 0
  key = 1
  for i in range(len(ans)):
    t_ans += (ans[-1-i]*key) % MOD
    t_ans %= MOD
    key *= (N-i-1)
    key //= (i+1)
    key %= MOD
  print(t_ans)
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,k = mp()

def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


mod = 998244353
now_comb = 1
now_pow = pow(m-1, n-1, mod)
ans = now_pow
for i in range(1, k+1):
    u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
    u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
    now_comb = u1
    now_pow = u2
    ans += (u1*u2) % mod
    ans %= mod
print((ans*m)%mod)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def ncr(n, r, mod):
    ret = 1
    for i in range(1, r+1):
        ret = (ret * (n-i+1) * pow(i, mod-2, mod)) % mod
    return ret


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

    ret = 0
    p = m*pow(m-1, n-k-1, mod)
    for i in range(k, 0, -1):
        ret += ncr(n-i, i, mod)*p
        p *= m-1
        p %= mod
    ret += p
    ret %= mod
    return str(ret)


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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    MOD = 998244353
    prepare(N + 10, MOD)

    n = min(N // 2 + 1, K + 1)
    m = M
    for _ in range(N-1):
        m *= M - 1
        m %= MOD

    ans = 0
    for k in range(n):
        ans += (m * cmb(N-1, k, MOD)) % MOD
        ans %= MOD

        m *= pow(M-1, MOD-2, MOD)
        m %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m,kk= map(int,input().split())
ppp=0
for k in range(0,kk+1):
    sum= pow(m-1,n-k-1,998244353) 
    if k==0:
        temp=1
    else:
        temp=n-k
        for i in range(n-k+1,n):
            temp*= i
            temp%= 998244353
        for i in range(1,k+1):
            temp/= i   
    ppp =( ppp+ (temp*m*sum))%998244353
print(int(ppp))

Submission status: Wrong Answer

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
N,M,K=map(int,input().split())
ans=0
for i in range(K+1):
  b=comb(N-i,i,998244353)
  ans+=(M*(M-1)**(N-1-i)*int(b))%998244353
print(int(ans%998244353))

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
 
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
 
mod = 998244353
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
ans = 0
for i in range(k+1):
    ans += (m * pow(m-1,n-1-i,mod) * cmb(n-1,i,mod)) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,(input().split()))
MOD = 998244353
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

Submission status: Wrong Answer

Solution code:
n,m,kk= map(int,input().split())
ppp=0
for k in range(0,kk+1):
    sum= pow(m-1,n-k-1,998244353) 
    if k==0:
        temp=1
    else:
        temp=n-k
        for i in range(n-k+1,n):
            temp*= i
            temp%= 998244353
        for i in range(1,k+1):
            temp/= i   
    ppp+=(temp*m*sum)%998244353
print(int(ppp))

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,n+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

ans = (m*pow(m-1,n-1,mod))%mod
x = ans
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:
N,M,K = map(int,(input().split()))
MOD = 998244353
def modinv(a, MOD):
    return pow(a, MOD-2, MOD)

def combination(n, r, MOD):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, MOD) % MOD
    return res

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

Submission status: Wrong Answer

Solution code:
import sys

N,M,K=map(int,input().split())
mod=998244353
if M==1:
    print(1)
    sys.exit()

#i個を被りなしで塗る塗り方
nurikata=[M]
for i in range(N-1):
    nurikata.append(nurikata[-1]*(M-1)%mod)
#print(nurikata)

def nCmMOD(A,B,Mod):
    #a conb b を　Mod で割った余り
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod



nurikata=nurikata[::-1]
ans=0
for i in range(K+1):
    ans+=nurikata[i]*nCmMOD(N-1,i,mod)
    #print(i,nurikata[i],pow(N-i,i,mod))
    ans%=mod

print(ans)

Submission status: Wrong Answer

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

N = 10 ** 6

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

for i in range(0, k+1):
    if i == k:
        base = m
    ans += base * cmb(n-1, n-1-i)
    ans %= mod
    base = base * inv_t[m-1] % mod

if m == 1 and k >= n-1:
    print(1)
else:
    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)
buns = 1
bunb = 1
for i in range(k):
    buns = buns * (n-1-i) % mod
    bunb = bunb * (i+1) % mod
    bunb_inv = pow(bunb,mod-2,mod)
    d = (buns * bunb_inv) % mod
    ans += m*d*pow(m-1,n-2-i,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

N = 10 ** 6

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

for i in range(0, k+1):
    if i == k:
        base = m
    ans += base * cmb(n-1, n-1-i)
    ans %= mod
    base = base * inv_t[m-1]

if m == 1 and k >= n-1:
    print(1)
else:
    print(ans)

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

ans = (m*pow(m-1,n-1,mod))%mod
x = ans
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:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353

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 = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

ans = 0

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

print(ans*m%mod)

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*=j
  prodi%=mod
  prodi*=pow(n-j,mod-2,mod)
  prodi%=mod
  prodi*=invi
  prodi%=mod 
sumi*=m
sumi%=mod
print(sumi)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=998244353
ans=pow(m,k+1,mod)
def mfact(n,mod):
    f=[1]
    for i in range(1,n+1):
        f.append(f[-1]*i%mod)
    return f
f=mfact(n,mod)
for i in range(k+1):
    ans+=(pow(m-1,n-i-1,mod)*f[n-1]*pow(f[n-1-i],mod-2,mod)*pow(f[i],mod-2,mod))%mod
print(ans%mod)