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

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

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
MOD=998244353
dp=[0] *(k+1)
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 #出力の制限
N = 3*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 )

def pos(x, n, m):
    if n == 0:
        return 1
    res = pos(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res

dp[0]=m*pos(m-1,n-1,MOD)%MOD
if k==0:
    print(dp[0])
    exit()
dp[1]=(m*m*pos(m-1,n-2,MOD)%MOD+dp[0])%MOD
if k==1:
    print(dp[1])
    exit()
for i in range(2,k+1):
    if i+1<=n:
        dp[i]=(dp[i-1]+m*pos(m-1,n-(i+1),MOD))%MOD
        dp[i]%=MOD
    if n+1>=3*i:
        dp[i]+=(cmb(n+1,3*i,MOD)*pos(m,i,MOD)*pos(m-1,n-2*i,MOD))%MOD
        dp[i]%=MOD
    else:
        print(dp[i])
        exit()

print(dp[k])

Submission status: Wrong Answer

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

inv = [ 0, 1 ]
for i in range( 2, 2 * ( 10 ** 5 ) ):
    inv.append( - inv[ p % i ] * (p//i) % p )

paint = [ m ]
for _ in range( n-1 ):
    paint[0] = paint[0] * ( m - 1 ) % p

for i in range( 1, k+1 ):
    # paint = paint + [ ( paint[-1] * ( n - i ) // i // ( m - 1 ) ) ]
    x = paint[-1] * ( n - i ) % p
    x = x * inv[i] % p
    x = x * inv[ m - 1 ] % p
    paint.append( x )

sum_paint = 0
for i in range( k+1 ):
    sum_paint = ( sum_paint + paint[i] ) % p

#print( paint )
print( sum_paint )

Submission status: Wrong Answer

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

MOD=998244353

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

def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(N+3, MOD)

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

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

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

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

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

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


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


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

Submission status: Wrong Answer

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

MOD=998244353

ans=0
temp2=1
temp3=1

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

print(ans%MOD)

Submission status: Wrong Answer

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

kai = [1]*(n+1)
inv = [1]*(n+1)
for i in range(n):
    kai[i+1] = (kai[i] * (i+1))%mod
    inv[i+1] = (inv[i] * pow(i+1,mod-2,mod))%mod

count_all = 0
pre_pow = pow(m-1,n-1,mod)
inv_m_mai1 = pow(m-1,mod-2,mod)
for i in range(k+1):
    pattern_color = m*pre_pow%mod
    pattern_place = kai[n-1]*inv[n-1-i]*inv[i]%mod
    count_all = (count_all+pattern_color*pattern_place)%mod
    pre_pow = pre_pow * inv_m_mai1 %mod

print(count_all)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def comb(p, q):
    return math.factorial(p) // (math.factorial(q) * math.factorial(p-q))

ans = 0

for i in range(k+1):
    row = comb(n-1, i)
    column = m * (m-1)**(n-i-1)
    ans += row * column
    
print(ans)

Submission status: Wrong Answer

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

MOD =  998244353
mod = MOD
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()

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




# 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:
n,m,k = map(int,input().split())
if k==0:
    print(m*(m-1)**(n-1)%998244353)
else:
    a=[m]+[0]*k
    b=[0]*(k+1)
    for i in range(n-1):
        b[0]=a[0]*(m-1)
        for i in range(1,k+1):
            b[k]=a[k-1]*(m-1)+a[k]
        a=b.copy()
    print(sum(a)%998244353)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m,k = na()
    mod = 998244353
    memo = m*pow(m-1, n-1)%mod
    ans = memo
    for i in range(1,k+1):
        memo *= (n-i)*pow(i*(m-1),mod-2,mod)
        memo %= mod
        ans += memo
    print(ans%mod)
    return

  
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# E

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

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

print(sum(res) % p)

Submission status: Wrong Answer

Solution code:
# E

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

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

print(sum(res) % p)

Submission status: Wrong Answer

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 2):
    next = C[-1] * (N-i) // i
    C.append(next)

res = 0

exp_quick = [1]
for i in range(N):
    exp_quick.append(exp_quick[-1] * (M-1) % mod)
print("quick finished")
for x in range(0,K+1):
    crt =  exp_quick[N-x-1] * M
    crt %= mod
    #print("start")
    idx = min(x, N-1-x)
    crt *= C[idx]
    #print("end")
    crt %= mod
    res += crt
    res %= mod

print(res)

Submission status: Wrong Answer

Solution code:

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=998244353):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    # テーブルを作成し、K回使いまわす
    fac, finv = COMinit(N-1, MOD)
    m = pow(M - 1, N - 1, MOD)
    m_inv = pow(M - 1, MOD - 2, MOD)

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

        m *= m_inv
        m %= MOD

    print(ans * M%MOD)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

ans=0

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

print(ans%998244353)

Submission status: Wrong Answer

Solution code:
import math


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

    _mod = 998244353

    if k == 0:
        res = ((m-1) ** (n-1) * m) % _mod
        print(res)
        return

    res_x = 0
    for i in range(k + 1):
        res_x += (m-1) ** (n-1-i) * math.comb(n-i,i) * m
    print(res_x % _mod)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from scipy.special import perm, comb
#perm(3, 2, exact=True)
#comb(3, 2, exact=True)
N, M, K = map(int, input().split()) 
mod =  998244353 

t = M*pow(M-1,N-1,mod)
for i in range(1,K+1):
  #print(t)
  t += M*pow(M-1,N-1-i,mod)*comb((N-1),i, exact=True)
  t %= mod
#
print(t)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

dp[0][0] = m
for i in range(1, n):
    for j in range(k + 1):
        # print(i, j)
        dp[i][j] += dp[i - 1][j] * (m - 1)
        dp[i][j] += dp[i - 1][j - 1] * 1 if j > 0 else 0
        dp[i][j] %= 998244353

# print(dp)
print(sum(dp[n-1]))

Submission status: Wrong Answer

Solution code:
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


ans = 0
comb = 1
col = M*pow(M-1, N-1, mod)
for i in range(K+1):
    now = col*comb
    now %= mod
    ans += now
    ans %= mod
    comb *= ((N-i-1)*inv(i+1))
    comb %= mod
    col *= inv(M-1)
    col %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 998244353


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


invs = {}


def inv(n):
    if n not in invs:
        invs[n] = pow(n, mod-2, mod)
    return invs[n]


ans = 0
comb = M
col = pow(M-1, N-1, mod)
for i in range(K+1):
    now = col*comb
    now %= mod
    ans += now
    ans %= mod
    comb *= ((N-i-1)*inv(i+1))
    comb %= mod
    col *= inv(M-1)
    col %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

MOD = 998244353

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

    def make_combination(n):
        fact = [1, 1]
        factinv = [1, 1]
        inv = [0, 1]

        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)

        comb = [0 for _ in range(n+1)]
        for r in range(n+1):
            comb[r] = fact[n] * factinv[r] * factinv[n-r] % MOD

        return list(map(ModInt, comb))

input = sys.stdin.readline

N, M, K = map(int, input().split())
comb = ModInt.make_combination(N-1)

ans = 0
tmp = ModInt(M*(M-1)**(N-1))

for x in range(K+1):
    ans += comb[x]*tmp
    tmp /= (M-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
# from collections import defaultdict

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


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


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


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

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

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

    return ret


mod = 998244353

N, M, K = geta(int)

if M == 1:
    print(1 if K < N else 0)
    exit()

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
def facmod(x,p=998244353):
  a=1
  for i in range(2,x+1):
    a= (a*i)%p
  return a

def combi(y,x,p=998244353):
  s=facmod(y)
  t=facmod(x)
  u=facmod(y-x)
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

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

N,M,K=map(int,input().split())
p=998244353
ans=0
for i in range(K+1):  
  t = (combi(N-1,i) * (M%p) * pow(M-1,N-1,p))%p
  ans += t
  #print(i,combi(N-1,i),M%p,pow(M-1,N-1,p))
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import product

INF = int(1e10)
# MOD = int(1e9 + 7)
MOD = 998244353

def framod(n, mod, a=1):
    for i in range(1, n + 1):
        a = a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, M, K = map(int, input().split())
    # N, M, K = 4, 3, 3
    ans = 0
    for x in range(N - 1):
        if x <= K:
            # N-1 C x (mod)
            f1 = comb(N - 1, x, MOD)

            # グループ内での塗り方
            f2 = (M * power(M - 1, N - x - 1, MOD)) % MOD
            ans = (ans + (f1 * f2) % MOD) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):   
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
zenpou.reverse()
ans=0
for i in range(x+1):
    #each_calとzenpouはAC
    #kouhouはWA
    ans+=(n_c_i[i]*k*kouhou[i])%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):    
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))

zenpou.reverse()
#each_cal.reverse()

#print(zenpou[0])
#print(each_cal[0])
for i in range(x+1):
    if zenpou[i]!=each_cal[i]:
        print("zenpou:",i)
        break
for i in range(x+1):
    if kouhou[i]!=each_cal[i]:
        print("kouhou:",i)
        break
ans=0
for i in range(x+1):
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*k*zenpou[i])%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
    

ans=0
for i in range(x+1):
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*k*zenpou[i])%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
    

ans=0
for i in range(x+1):
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*k*kouhou[i])%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
#print(n_c_i)
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
ans=0
#print(ans)
for i in range(x+1):
    pow_k=(pow_k*inv_k)%od
    p_k=(k*pow_k)%od
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*p_k)%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
for i in range(1,x+1):
    n_c_i.append(n_c_i[-1]*(n-i)//i)
#print(n_c_i)
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
ans=0
#print(ans)
for i in range(x+1):   
    pow_k=(pow_k*inv_k)%od
    p_k=(k*pow_k)%od
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*p_k)%od
    ans%=od

print(ans)

Submission status: Wrong Answer

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

od=998244353
n,k,x=list(map(int,input().split()))

comb=1
pow_k=pow(k-1,n-1,od)
inv_k=pow(k-1,od-2,od)
ans=k*pow_k%od
#print(ans)
for i in range(1,x+1):
        
    pow_k=(pow_k*inv_k)%od
    comb=(comb*(n-i)//i)%od
    ans+=comb*k*pow_k%od
    ans%=od

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod = 998244353

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

comb = 1
for i in range(k + 1):
  tmp = comb * m * pow(m-1, n-i-1, mod) % mod
  count = (count + tmp) % mod
  comb = comb * (n - i) * pow(i+1, mod-2, mod) % mod
print(count)

Submission status: Wrong Answer

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

# 0^0 = 1

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

    MOD = 998244353

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,M,K=pin()
    mod=998244353
    #dp
    #init
    dp_table=[[0]*(K+1) for _ in range(N)]
    dp_table[0][0]=M
    for i in range(1,N):
        
        #calculation dp_table
        for k in range(K+1):
            
            a,b=0,0
            a=dp_table[i-1][k]*(M-1)
            if k>0:b=dp_table[i-1][k-1]

            #print(i,k,a,b)
            dp_table[i][k]=(a+b)%mod
    print(sum(dp_table[-1]))
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,M,K=pin()
    mod=998244353
    #dp
    #init
    dp_table=[[0]*(K+1) for _ in range(N)]
    dp_table[0][0]=M
    for i in range(1,N):
        
        #calculation dp_table
        for k in range(max(0,K-i),K+1):
            
            a,b=0,0
            a=dp_table[i-1][k]*(M-1)
            if k>0:b=dp_table[i-1][k-1]

            #print(i,k,a,b)
            dp_table[i][k]=(a+b)%mod
    print(sum(dp_table[-1]))
#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
P = 998244353


nn = 200200

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P


def comb(a, b):
    return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


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

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


t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
ans = 0
for k in range(K+1):
    ans = (ans + t * comb(N-1, k)) % P
    t = t * m % P
print(ans * M % P)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n, m, k = (60522, 114575, 7559)

L = [1 for i in range(n)]
for i in range(1, n):
  L[i] = L[i-1] * (m-1) % MOD
s = L[-1]
c = 1
for i in range(1, k + 1):
  c = c * (n-i) // i
  s += L[n-1-i] * c % MOD

s = s * m % MOD
print(s)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]

for i in range(1, N):
    nCi.append((nCi[i-1]*(N-i)//i)%mod)


for i in range(min(N, K)+1):
    ans += (M%mod) * pow(M - 1, N-1-i, mod) * nCi[i]
    ans %= mod

print(ans)