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

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

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

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

def nck(n,k):
    MOD = 998244353
    fac, ifac = make_tables(MOD, n)
    ans = cmb(n, k, MOD, fac, ifac)
    return ans

n,m,k=n1()

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

Submission status: Wrong Answer

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

MOD = 998244353
N, M, K = map(int, input().split())
ans = M
Mm1 = M-1
for n in range(N-1):
    ans = (ans * Mm1) % MOD
K0 = ans
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 + 2):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)
Nm1 = N-1
for k in range(1, K+1):
    ans = (ans + K0 * cmb(Nm1, k, MOD)) % MOD
print(ans)

Submission status: Wrong Answer

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

def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m

#nPrをmで割った余りを求める(ただしn<m、mは素数)
import sys
sys.setrecursionlimit(10**9)
def perm_remainder(n,r,m):
    if r>=1:
        return (perm_remainder(n-1,r-1,m)*n)%m
    else:
        return 1


def comb_remainder(n,r,m):
    r=min(r,n-r)
    return (perm_remainder(n,r,m)*gyakugen(perm_remainder(r,r,m),m))%m

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

ans=0
po=power_remainder(m-1,n-k-1,p)
for i in range(k+1):
  ansk=po*comb_remainder(n-1,i,p)%p
  po=po*(m-1)
  ans=(ans+ansk)%p
  
ans=ans*m%p
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod = 998244353

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
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 )
for i in range(K+1):
    ans += pow(M-1, N-1-i, mod) * pow(M, i+1, mod) * cmb(N-1, i, mod)
    ans %= mod
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N,M,K = list(map(int,_in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for k in range(K+1):
        if k==0:
            cnt += M*(M-1)**(N-1)
        else:
            cnt += M*(M-1)**max(N-k-1,0)*max(N-k,1)
        cnt %= 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

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 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 %= 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:
#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 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
  
if K == N - 1:
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
s = [M*((M-1)**(N-1))]
for i in range(1,K+1):
    if K == 0:
        break
    a = M*(i+1)*((M-1)**(N-1-i))
    s.append(a)
print(sum(s)%998244353)

Submission status: Wrong Answer

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

if m == 1:
    if k == n-1:
        print(count)
    else:
        print(0)
    exit()

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count += count_tmp

print(count%998244353)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 0

for i in range(K+1):
  if i == 0:
    a = int( ( M * (M-1) ** (N-1) ) % 998244353 )
    ans = int( (ans + a )% 998244353 )
  else:
    a = int( ( (M**(i+1)% 998244353) * ((M-1) ** (N-1-i)% 998244353) ) % 998244353 )
    ans = int( (ans + a )% 998244353 )
    
print(ans)

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):
    Q[i][j] = Q[i-1][j-1]+(M-1)*Q[i-1][j]
print(sum(Q[N-1])%998244353)

Submission status: Wrong Answer

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

ways = [0] * n

for i in range(0, 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 if i > 0 else 1
    total += ways[-(i + 1)] * nCr % 998244353

print(total % 998244353)

Submission status: Wrong Answer

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

if m==1:
    if n*(n-1)//2 <= k:
        print(1)
    else:
        print(0)

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

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, open(0).read().split())

mod = 998244353
res = 1
t = 1
for i in range(N):
    if i <= K:
        t = t * M % mod
    else:
        t = t * (M - res) % mod
        res += max(0, K - 1)

print(t)

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 = 998244353 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
ans =0
ml =[m-1]*n

if n ==1:
    print(m)
    exit()
elif m ==1:
    print(1)
    exit()

for l in range(1,n):
    ml[l] = ml[l-1]*(m-1) % mod

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 )

for j in range(k+1):
    if n-2-j >=0:
        a = m*ml[n-2-j]*cmb(n-1,j,mod)
        ans +=a
    elif n - 2- j == -1:
        a = n
        ans +=a
    elif n - 2- j == -2:
        a = 1
        ans +=a        
print(ans % mod)

Submission status: Wrong Answer

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

lis = np.array([m])
for i in range(1, n):
    tmp_list = np.append(0, lis)
    lis *= (m-1)
    lis = np.append(lis, 0)
    lis += tmp_list

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

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
dp = [0]*(K+1)
P = 998244353
dp[0] = pow(M-1, N-1, P) * M % P

inv_t = [0]*(2*10**5+1)
inv_t[1] = 1
for i in range(2,2*10**5+1):
  inv_t[i] = inv_t[P % i] * (P - int(P / i)) % P

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


for i in range(1, K+1):
    temp = dp[i-1]*(N-i)
    temp %= P
    temp *= inv_t[i]
    temp %= P
    temp *= inv_t[M-1]
    temp %= P
    dp[i] = temp

ans = 0
for i in range(K+1):
    ans += dp[i]
    ans %= P

print(ans)

Submission status: Wrong Answer

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

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

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

mod=998244353

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



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

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

ruijo=[1]
now=1

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

ans=[]

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

kotae=0

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

print(kotae)

Submission status: Wrong Answer

Solution code:
import math
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)
    ans += cc*M*( (M-1)**(N-2-i+1) )
    #print(i,cc,ans)
    if ans >= 998244353:
        ans = ans%998244353
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N,M,K = list(map(int,_in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for k in range(K+1):
        if k==0:
            cnt += M*(M-1)**(N-1)
        else:
            cnt += M*(M-1)**(N-k-1)*(N-k) 
        cnt %= 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Wrong Answer

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

import math

mod = 998244353


if k ==0:
    print(m*((m-1)**(n-1)) % mod)
else:
    print( ( m * ( ( (m-1)**(n-1) ) + k*m*(n-1) ) ) % mod)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m,k=map(int,input().split())
    mod=998244353
    ans=0
    for kx in range(k+1):
        ans+=m*(m-1)**(n-1-kx)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod = 998244353

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

Submission status: Wrong Answer

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

print(factorial(n)%998244353)

Submission status: Wrong Answer

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

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

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

mod=998244353

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



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

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

ruijo=[1]
now=1

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

ans=[]

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

kotae=0

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

print(kotae)

Submission status: Wrong Answer

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

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

def color(now,num,kaburi,ima):
    global an
    if kaburi > k:
        an += now%mod
        return
    if ima > n:
        an += now%mod
        return
    if num == m:
        return color(now,num,kaburi+1,ima+1)
    else:
        return color(now*(m-num)%mod,num+1,kaburi,ima+1),color(now,num,kaburi+1,ima+1)

color(m,1,0,0)

print(an%mod)

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 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:
n, m, k = map(int, input().strip().split())

ways = [0] * n
ways[0] = m

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

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

print(total % 998244353)

Submission status: Wrong Answer

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

P = MOD
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
#print(inv_t)
          
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:
def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
    x = x*x
    n = n >> 1
  return ans
n, m, k = map(int, input().split())
ans = 0
for i in range(k + 1):
    ans += (pow(m - 1, n - i - 1) * (i + 1) * m) % 998244353
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 = 998244353 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
ans =0
ml =[m-1]*n

if n ==1:
    print(m)
    exit()

for l in range(1,n):
    ml[l] = ml[l-1]*(m-1) % mod

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 )

for j in range(k+1):
    if n-2-j >=0:
        a = m*ml[n-2-j]*cmb(n-1,j,mod)
        ans +=a
    elif n - 2- j == -1:
        a = n
        ans +=a
    elif n - 2- j == -2:
        a = 1
        ans +=a        
print(ans % mod)

Submission status: Wrong Answer

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

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

s = [1]
for i in range(2, n+1):
    s.append(s[-1]*i%MOD)

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

Submission status: Wrong Answer

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

dp=[[0]*(K+1) for _ in range(N)]#Kは０組の場合もあるのでK＋1

MOD=998244353

def pow_mod(n,k,m):#nのk乗をmod mしたものを算出する関数
    if k==0:
        return 1
    if k%2==0:
        return (pow_mod(n,k//2,m)**2)%m
    if k%2==1:
        return (pow_mod(n,k-1,m)*n%m)%m

dp[0][0]=M%MOD
for i in range(1,N):
    dp[i][0]=(M%MOD)*pow_mod(M%MOD-1,N,MOD)#((M%MOD-1)**(N))

for j in range(1,K+1):
    for i in range(1,N):
        #print(i,j,dp)
        dp[i][j]=(dp[i-1][j]*(M-1)%MOD+dp[i-1][j-1])%MOD

#print(dp)
print(sum(dp[N-1][j] for j in range(K+1))%MOD)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    mod = 998244353
    ans = 0
    for i in range(K+1):
        ans += pow(M-1, N-1-i, mod) * pow(M, i+1, mod)
        ans %= mod
    ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
c = 0
d= []
from scipy.special import comb
for i in range(k+1):
    a = m * (m-1)**(n-k-1) * comb(n-1, k , exact = True)
    d.append(a)
ans = sum(d) % 998244353
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
mod = 998244353

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

Submission status: Wrong Answer

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

print(t)

Submission status: Wrong Answer

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

if m == 1:
    if k == n-1:
        print(count)
    else:
        print(0)
    exit()

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count += count_tmp
    count %= 998244353

print(count)

Submission status: Wrong Answer

Solution code:
def mod_frac(k, mod):
    ans = 1
    for i in range(1, k + 1):
        ans *= i
        ans %= mod
    return ans


def mod_comb(n, r, mod):
    ans = 1
    mul1 = mod_frac(n, mod)
    mul2 = pow(mod_frac(r, mod), mod - 2, mod)
    mul3 = pow(mod_frac(n - r, mod), mod - 2, mod)

    ans *= mul1
    ans %= mod
    ans *= mul2
    ans %= mod
    ans *= mul3
    ans %= mod

    return ans


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

mod = 998244353
x = m

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

ans = 0

for i in range(k + 1):
    ans += mod_comb(n - 1, i, mod)
    ans %= mod

ans *= x
ans %= mod

print(ans)

Submission status: Wrong Answer

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

if m == 1:
    if k == n-1:
        print(0)
    else:
        print(count)
    exit()

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count += count_tmp
    count %= 998244353

print(count)

Submission status: Wrong Answer

Solution code:
import sys

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

if n>m+k:
  print(0)
  sys.exit()

# 前処理
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 COM(n, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
  
  
MAX=n+1
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

def HCOM(n,r):
  return COM(n+r-1,r)
  
#t=max(1,n-k)!
t=m
if n-k>1:
  for i in range(2,max(2,n-k)):
    t*=m-1
    t%=MOD
#print(t)

ans=0
for c in range(max(1,n-k),n+1):
  if c>1:
    t*=m-1
  t%=MOD
  #print("c=",c,"t=",t,"HCOM=",HCOM(c,n-c))
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

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

    def comb(n,r,p = mod):
        r = min(r,n-r) # nCr
        res = 1
        div = 1 # nCr := n*n-1*...n-r+1 // 1*2*3...r
        for i in range(n-r+1,n+1):
            res *= i
            res %= p
        for i in range(1,r+1):
            div *= i
            div %= p
        res *= pow(div,p-2,p) # 掛け算に
        res %= p
        return res


    if n - k >= m:
        print(comb(n - 1 + m,m))
    else:
        print(m)
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] % mod

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

Submission status: Wrong Answer

Solution code:
def solve():
    N,M,K = map(int,input().split())
    dp = [[0] * (K+1) for _ in range(N)]
    dp[0][0] = M
    MOD = 998244353

    for i in range(1,N):
        if K + 1 == i:
            break
        dp[i][i] = dp[i-1][i-1] % MOD * M % MOD

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

count = 0
for i in range(k + 1):
    num = n - i
    temp = m
    for j in range(num - 1):
        temp *= m - 1
        temp %= mod
    temp *= combination(num, i, mod)
    temp %= mod
    count += temp
count %= mod
print(count)

Submission status: Wrong Answer

Solution code:
import sys

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

if n>m+k:
  print(0)
  sys.exit()

# 前処理
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 COM(n, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
  
  
MAX=10000000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

def HCOM(n,r):
  return COM(n+r-1,r)
  
#t=max(1,n-k)!
t=m
if n-k>1:
  for i in range(2,max(2,n-k)):
    t*=m-1
    t%=MOD
#print(t)

ans=0
for c in range(max(1,n-k),n+1):
  if c>1:
    t*=m-1
  t%=MOD
  #print("c=",c,"t=",t,"HCOM=",HCOM(c,n-c))
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

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 = 998244353 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
ans =0
ml =[m-1]*n
for l in range(1,n):
    ml[l] = ml[l-1]*(m-1) % mod

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 )

for j in range(k+1):
    a = m*ml[n-2-j]*cmb(n-1,j,mod)
    ans +=a
print(ans % mod)

Submission status: Wrong Answer

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

MOD = 998244353
ans = 0
plu = M*pow(M-1, N-1, MOD)
l = [0]*N
l[0] = 1
for i in range(1,N):
  l[i] = l[i-1]*(M-1)
  l[i] = l[i]%MOD

ans = M*l[N-1]%MOD
i = 1
while i<=K:
  ans += (M*l[N-1-i])%MOD * (N-i)
  ans %= MOD
  i += 1
  
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):
    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:
MOD = 998244353

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


def getModInv(a):
    return modPow(a, MOD-2, MOD)


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

s = 0
c = 1
c1 = N-1
c2 = 1
d = modPow(M-1, N, MOD)
d1 = getModInv(M-1)


for k in range(K+1):
    d = d*d1%MOD

    s = (s + c*d)%MOD

    c = c*c1%MOD*getModInv(c2)%MOD
    c1 -= 1
    c2 += 1


print((s*M)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def mod_fra(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

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

def mod_comb(n, k, mod):
    a=mod_fra(n, mod)
    b=mod_fra(k, mod)
    c=mod_fra(n-k, mod)
    return (a * mod_power(b, mod-2, mod) * mod_power(c, mod-2, mod)) % mod
def main():
    n,m,k=map(int,input().split())
    mod=998244353
    ans=0
    for kx in range(k+1):
        ans+=mod_comb(n-1,kx,mod)*m*(m-1)**(n-1-kx)%mod
        print(kx)
    print(ans%mod)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M, K = [int(x) for x in input().strip().split()]
    MOD = 998244353
    if M == 1:
        if N == 1:
            print(1)
            exit()
    
    fact = [1] * (N+1)
    inv_fact = [1] * (N+1)
    for i in range(1, N+1):
        fact[i] = ((i) * fact[i-1]) % MOD
    
    inv_fact[-1] = pow(fact[-1], MOD-2, MOD)
    for i in range(N-1):
        inv_fact[N-i-1] = (inv_fact[N-i] * (N - i)) % MOD

    def nCr(n, r):
        if r == 0 or r == n:
            return 1
        r = min(r, n - r)
        return fact[n] * inv_fact[n-r] * inv_fact[r] % MOD

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

    print(ans)

if __name__ == '__main__':
    main()