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
readline = sys.stdin.readline
MOD = 998244353

def comb(n, r, mod=MOD):
    r = min(n - r, r)
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= mod
        fac *= i + 1
        fac %= mod
    return res * pow(fac, mod-2, mod) % mod

def main():
    N, M, K = map(int, readline().rstrip().split())
    res = 0
    power = pow(M-1, N-K-1, MOD)
    c = comb(N-1, K, MOD)
    for k in range(K, -1, -1):
        n = N - k
        res += c * power * M
        res %= MOD
        power = (power * (M-1)) % MOD
        c = c * k // (N-1 - K + 1)
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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

p = 998244353
N = 10 ** 6
fact = [1, 1] + [0] * (N-1)
factinv = [1, 1] + [0] * (N-1)
inv = [0, 1] + [0] * (N-1)

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

n, m, k = [int(i) for i in input().split()]

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m, k = map(int, input().split())
    dp = [0 for _ in range(k + 1)]

    dp[0] = m

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

    ans = 0
    for i in range(k + 1):
        ans += dp[i]
    print(ans % 998244353)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

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


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M,K = map(int,input().split())
MOD=998244353

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

MOD = 998244353

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

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

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

    return K * x

ans = 0
for i in range(k + 1):
  ans += (pow_k(m, i + 1, MOD) * pow_k(m - 1, n - 1 - i, MOD) * comb(n - 1, i, MOD)) % MOD
print(ans % MOD)

Submission status: Wrong Answer

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


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M,K = map(int,input().split())
MOD=998244353

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

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()
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
ans=0
po=pow(m-1,n-1,mod)
ue=fact[n-1]
iii=m*pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
print(ans%mod)

Submission status: Wrong Answer

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

kaijo = [1]*n #(i+1)! mod inf
inv = [1]*n #(i+1)!^-1 mod inf
for i in range(n):
    kaijo[i] = kaijo[i-1]*(i+1)
    kaijo[i] = kaijo[i]%inf
inv[n-1] = pow(kaijo[n-1],inf-2,inf)
for i in range(1,n):
    inv[n-1-i] = inv[n-i]*(n-i+1)
    inv[n-1-i] = inv[n-1-i]%inf
#ここまで前処理(関数の外に出す)
def comb1(n,k): #素数で割るかつ全て考えたいとき O(n) 10**5まで
    if k == 0: return 1
    return kaijo[n-1]*inv[k-1]*inv[n-k-1] % inf

ans = 0
for k in range(K+1):
    ans += M*comb1(n-1,k)*pow(M-1,n-1-k,inf)%inf
    ans = ans%inf

print(ans)

Submission status: Wrong Answer

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

MOD = 998244353

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

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

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x

ans = 0
for i in range(k + 1):
  ans += (pow_k(m, i + 1, MOD) * pow_k(m - 1, n - 1 - i, MOD) * comb(n - 1, i, MOD)) % MOD
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import math

n, m, k = map(int,input().split())
ans = 0
permutation = [1]*(n+1)
for i in range(1,n+1):
    permutation[i] = permutation[i-1]*i

for i in range(k+1):
    temp = m*((m-1)**(n-k-1))%998244353
    comb = (permutation[n-i]//permutation[n-(2*i)]*permutation[i])%998244353
    temp *= comb%998244353
    ans += temp

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
n, m, k = map(int, input().split())
ans = 0
def combinations_count(n, r):
    return factorial(n) // ((factorial(n - r) * factorial(r)))
c = 1
for i in range(k + 1):
    shikiri = n - i - 1
    ans += c * m * pow(m - 1, shikiri)
    ans %= 998244353
    c *= shikiri // (n - shikiri)
print(ans)

Submission status: Wrong Answer

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

dp = [[0] * (K + 2) for _ in range(N)]

x = 998244353
dp[0][0] = M
for j in range(1, N):
    for i in range(K + 1):
        dp[j][i + 1] += dp[j - 1][i] % x
        dp[j][i] += dp[j - 1][i] * (M - 1) % x
ans = 0
for i in range(K + 1):
    ans += dp[N - 1][i] % x
print(ans)

Submission status: Wrong Answer

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

mod = 998244353

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

ans = 0
for i in range(n-k-1, n):
    res = m
    e = m - 1
    while i > 0:
        if i & 1:
            res = res * e % mod
        e = e * e % mod
        i >>= 1
    com = fac[n-1] * finv[i] * finv[n-i-1] % mod
    res = res * com % mod
    ans = (ans + res) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
n, m, k = map(int, input().split())
ans = 0
def combinations_count(n, r):
    return factorial(n) // ((factorial(n - r) * factorial(r)))
c = 1
for i in range(k + 1):
    shikiri = n - i - 1
    ans += c * m * ((m - 1) ** shikiri)
    #print(shikiri, c)
    ans %= 998244353
    c *= shikiri // (n - shikiri)
print(ans)

Submission status: Wrong Answer

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

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

print(sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
p = 998244353
sum_color = 0
for k in range(K+1):
  num1 = pow(N-1,k,p)
  num2 = M%p
  num3 = pow(M-1,N-1-k,p)
  sum_color += (num1*num2*num3)%p
  sum_color %= p
  
print(sum_color%p)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

def f(nn,mm,kk):
    if nn==1:
        return mm
    if nn==2:#終了条件
        if kk!=0:
            return mm
        else:
            return mm-1

    if kk>0:
        #print(nn,mm,kk,'a')
        return (f(nn-1,mm,kk-1) + ((mm-1)*f(nn-1,mm,kk)))%998244353
    else:
        #print(nn,mm,kk,'b')
        return (mm-1)**(nn-1)%998244353

print((m*f(n,m,k))%998244353)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

ans=0
a=1
for i in range(k+1):
    ans+=a*m*(((m-1)**(n-1-k)))
    a=a*(n-1-i+1)//(i+1)
print(ans%998244353)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

MOD = 998244353

class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)



C = [modint(1), modint(n - 1)]
# C = [1, n - 1]
for i in range(2, k + 1):
    C.append(C[-1] * (n - (2 * i - 1)) * (n - (2 * i - 2)) // i // (n - i + 1))

# print(C)

ans = modint(0)
for i in range(k + 1):
    ans += modint(m) * pow(m - 1, n - 1 - i, MOD) * (max(int(C[i]), 1))

print(ans)

Submission status: Wrong Answer

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

mod = 998244353


fac = [1]
for i in range(2, N+1):
    fac.append(fac[-1] * i % mod)


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= fac[a-1]
    c *= pow(fac[b-1], p - 2, p)
    c *= pow(fac[a - b-1], p - 2, p)
    return c % p


ans = 0
ans += M * pow(M-1, N-1)
ans %= mod

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,m,k = map(int,input().split())
MOD = 998244353
answer = 0
def perm(n, k = 1):
    global MOD
    pdt = 1
    for x in range(n, n-k, -1):
            pdt *= x%MOD
    return pdt
for i in range(k+1):
    answer +=(perm(n-1, i)*((pow(m,i+1,mod = MOD))*(pow(m-1,n-1-i,mod = MOD))))%MOD
print(answer%MOD)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=998244353
ans=0
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(k+1):
  kk=k-i
  kaz=math.factorial(n-kk)%mod
  con=combinations_count((n-1),kk)%mod
  ans+=kaz*con
  ans=ans%mod
print(ans)

Submission status: Wrong Answer

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

N, M, K = MAP()

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

print(ans%mod)

Submission status: Wrong Answer

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

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


minv = modinv(m, mod)
i = 2
while i <= n:
    j = 2
    while j <= k:
        dp[i][j] = (dp[i//2][j//2] ** 2 * minv * (m-1)) % mod
        j *= 2
    i *= 2

ans = 0
for i in range(k+1):
    for j in range(50):
        if n >> j & 1:
            dp[n][i] += dp[j][i]
print(sum(dp[n][:k+1]))

Submission status: Wrong Answer

Solution code:
#E問題
N, M, K = map(int, input().split())
MOD = 998244353

P = MOD
Y = max(N, M)
inv_t = [0]+[1]
for i in range(2, Y):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
#print(inv_t)
          
if K == N - 1:
  ans = 1
  for i in range(N):
    ans = ans * M % MOD
  print(ans % MOD)
  quit()
  
if M == 1:
  print("1")
  quit()
  
# M * ((M - 1) ** (N - L - 1)) * combination(N-1, L)のLを0からKまで足した総和が答え
B = [1] * N
ans1 = 1
for i in range(1, N):
  ans1 = (ans1 * (M - 1)) % MOD
  B[i] = (ans1 * M) % MOD
  
ans = 0
ans2 = 1
#X = 1
for i in range(K + 1):
  if i == 0:
    X = 1
  else:
    X = (X * (N - i) * inv_t[i]) % MOD
  ans2 = X * B[N - 1 - i] % MOD 
  ans += ans2
  ans = ans % MOD
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

N,M,K = IL()

ans = 0

total = pow(M, N, mod)
over = pow(M, N-(K+1), mod)

print((total - over)%mod)

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) 
    temp=n-k
    for i in range(n-k+1,n):
       temp = (temp*i)% 998244353
    for i in range(1,k+1):
         temp/=i
    ppp+= temp*m*sum
print(ppp)

Submission status: Wrong Answer

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

ways = [0] * n

for i in range(n):
    if i == 0:
        ways[i] = m
    else:
        way = ways[i - 1] * (m - 1)
        way %= 998244353
        ways[i] = way

total = 0
nCr = 1
for i in range(k + 1):
    nCr *= (n - i) // (i + 1) if i > 0 else 1
    total += ways[-(i + 1)] * nCr
    total %= 998244353

print(total % 998244353)

Submission status: Wrong Answer

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

MOD = 998244353  # type: int


class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  # 階乗を求めるためのキャッシュ
        self.invModulos = [0, 1]  # n^-1のキャッシュ
        self.invFactorial_ = [1, 1]  # (n^-1)!のキャッシュ

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def choose_k_from_n(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, M: int, K: int):
    sum = 0
    C = Combination(MOD)
    current = M * powm(M-1,N-K-1,MOD) %MOD
    for i in range(K+1):
        sum = (sum+C.choose_k_from_n(N-1,N-1-K-i)*current)%MOD
        current =current*(M-1)%MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

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:
def com(n,r,mod):
    k=min(r,n-r)
    C=1
    for i in range(1,k+1):
        C=(C*(n+1-i)*pow(i,mod-2,mod))%mod
    return C

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

C = 1
P = pow(m - 1, n - 1, mod)
cnt = C * m * P
for i in range(1, k + 1):
    P = P * pow(m - 1, mod-2, mod)
    C = C * (n - 1 - i) * pow(i + 1, mod-2, mod)
    cnt = (cnt + C*m*P)
print(cnt % mod)

Submission status: Wrong Answer

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

print( (pow(m,n,mod)-(pow(2,n-k+1,mod)*pow(m,n-k,mod))%mod )%mod)

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


n,k,x=list(map(int,input().split()))
od=998244353
ans=(pow(n,x,od)*pow(2*n-k,n-x,od))%od
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, M, K = map(int, input().split())
ans = 0
for k in range(K+1):
    n = N - k
    a = M * (M-1)**(n-1)
    b = n**k // math.factorial(k)
    ans += a * b
print(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-i,i,mod)) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 998244353
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
N = 10**5 * 2+1
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)

N,M,K = m()

po = 1

for i in range(N):
    if i <= K:
        po *= M
        po %= mod
    else:
        e = 1
        e *= cmb(i,i-K-1)
        e %= mod
        e *= pow(M-1,i-K-1,mod)
        e %= mod
        e *= M
        e %= mod
        po = po*M - e
        po %= mod
print(po)

Submission status: Wrong Answer

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

MOD = 998244353

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

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

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 = combination(n-1, 1, mod)
now_pow = pow(m-1, n-1, mod)
ans = now_pow
for i in range(1, k+1):
    u1 = now_comb * i
    u2 = now_pow * pow(m-1, mod-2, mod)
    now_comb = u1
    now_pow = u2
    ans += (u1*u2) % mod
    ans %= mod
print((ans*m)%mod)

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
mod = 998244353
ans = M*((pow(M,N-1,mod)-pow(M,K-2,mod))%mod)%mod
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m,k=map(int,input().split())
MOD=998244353
dp = np.zeros(n,dtype='float32')
dp[0]=m
for i in range(2,n+1):
    bdp=dp
    dp+=bdp*(m-1)
    dp[1:]+=bdp[:1]
    dp%=MOD
print(sum(dp[:k+1]))

Submission status: Wrong Answer

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

ans=0
for i in range(k+1):
    a=1
    ans+=a*m*(((m-1)**(n-1-k)))
    a=a*(n-1-i+1)//(i+1)
print(ans%998244353)

Submission status: Wrong Answer

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


mod=998244353
n,m,k=map(int,input().split())
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=m
for i in range(max(0,k-1)):
    ans *=m
    ans %=mod
for i in range(n-1-k):
    ans *=(m-1)
    ans %=mod

ans *=cmb(n,k,mod)
print(ans%mod)

Submission status: Wrong Answer

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