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 main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        print(1)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac = [0]*(N+1)
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
    
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
    
    ans = 0
    base = [1,pow(M-1,N-K-1,MOD)]
    for i in range(K+1):
        base.append((base[-1]*(M-1))%MOD)

    
    for i in range(K+1):
        ret = comb(N-1,i)*(M*base[-i-2])
        ans += ret
    
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

nurikata=[M]
for i in range(N-1):
    nurikata.append(nurikata[-1]*(M-1)%mod)
#print(nurikata)

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

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

print(ans)

Submission status: Wrong Answer

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

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

def comb(n, k):
    if (n < k) or (k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
    
if K == 0:
    ans = (M*pow(M-1, N-1, MOD))%MOD 
if K >= 1:
    ans = (M*(pow(M-1, N-1, MOD)+pow(M-1, N-1, MOD)*(N-1)))%MOD
if K > 1:
    for i in range(K-1):
        ans = (ans + M*pow(M-1, N-3-i, MOD)*comb(N-1,i+2)%MOD)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
while N >= 1 and M >= 1:
    B = N * M
    M -= 1
    B += B
for K in range (1, N + 1):
    print(B)
    break
else:
    print(B/2)

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:
    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:
print(0)

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
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:
    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:
def inv_mod(a, p):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, M, K = inpl()

q = pow(M-1,N-1,MOD) * M % MOD
S = q
f = inv_mod(M-1,MOD)
for k in range(1,K+1):
    q *= f * (N-k) * inv_mod(k,MOD)
    q %= MOD
    S += q
    S %= MOD
print(S)

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
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):
  t*=m-1
  t%=MOD
  #print("t=",t,"COM=",COM(c,n-c))
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

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(N):
        fact[i+1] = (i * fact[i]) % 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, MOD)) * nCr(N-1, k+1)) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD = 998244353
N, M, K = map(int, input().split())
Mp = [0]*(K+1)
nck = [0]*(K+1)
nck[0] = 1
for i in range(K):
  nck[i+1] = (nck[i]*(N-i-1)*(i+1)) % MOD
p = 1
for i in range(1,N):
  p = p*(M-1)%MOD #(M-1)^i
  if(i >= N-K-1):
    Mp[N-i-1] = p
ans = 0
for i in range(K+1):
  ans = (ans+M*Mp[i]*nck[i])%MOD
print(ans)

Submission status: Wrong Answer

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

fac = [1]
tmp = 1
for i in range(N):
  fac.append(tmp)
  tmp *= (i+2)



def combinations_count(n, r):
    return fac[n] // (fac[n - r] * fac[r])

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

print(ans)

Submission status: Wrong Answer

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

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
  
ans = 0
ans2 = 1
#X = 1
for i in range(K + 1):
  if i == 0:
    X = 1
  else:
    X = int(X * (N - i) / i) % MOD
  ans2 = X * B[N - 1 - i] % MOD 
  ans += ans2
  ans = ans % MOD
  
ans = (M * ans) %MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=998244353
fact=[1]
fact_inv=[1]
for i in range(n+1):#<< Nの最大値
    new_fact=fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

def mod_comb(n,k,mod):
    return fact[n]*fact_inv[k]%mod*fact_inv[n-k]%mod

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 998244353
N, M, K = map(int, input().split())
if M == 1:
	print(1)
	sys.exit()
def cumprod(x, MOD = mod):
	L = len(x)
	Lsq = int(L**.5 + 1)
	x = np.resize(x, Lsq ** 2).reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		x[:,n] *= x[:,n-1]
		x[:,n] %= MOD
	for n in range(1,Lsq):
		x[n] *= x[n-1, -1]
		x[n] %= MOD
	return x.flatten()[:L]

def make_fact(U, MOD = mod):
	x = np.arange(U, dtype = np.int64)
	x[0] = 1
	fact = cumprod(x, MOD)
	x = np.arange(U, 0, -1, dtype = np.int64)
	x[0] = pow(int(fact[-1]), MOD - 2, MOD)
	fact_inv = cumprod(x, MOD)[::-1]
	return fact, fact_inv

fact, fact_inv = make_fact(N+10)


ans = 0
D = M * ((M-1) ** (N-1))
D %= mod
for i in range(K+1):
	if i == 0:
		ans += D
	else:
		d = fact[N-1]
		d *= fact_inv[i]
		d %= mod
		d *= fact_inv[N-1-i]
		d %= mod

		tmp = d * D
		tmp %= mod
		ans += tmp

	ans %= mod		
	D *= pow(M-1, mod-2, mod)
	D %= mod

ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
# 10 ** 7 might cause MLE
fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

mod = 998244353
p = mod

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(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

initNCMMod(3 * (10**5))
def main():
    n, m, k = LI()
    m1l = [0] * (n+1)
    m1l[0] = 1
    for i in range(n):
        m1l[i+1] = (m1l[i] * (m-1)) % p
    cnt = 0
    for l in range(k+1):
        x = (m1l[n-l] * m * inv[m-1]) % p
        x *= NCMMod(n-1, l)
        cnt += x
        cnt %= p
    print(cnt % p)




main()

Submission status: Wrong Answer

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

dp = [[0] * (K+2) for _ in range(N+1)]
dp[0][0] = M
# dp[i][j] := i番目のブロックまで見た時に隣り合うブロックで同じ色で塗られている組がj組
for i in range(N):
    dp[i+1][0] = dp[i][0] * (M-1) % mod
    for j in range(K):
        dp[i+1][j+1] += dp[i][j] + dp[i][j+1]

print(sum(dp[N-1])%mod)

Submission status: Wrong Answer

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

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)

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

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:
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * m.i % MOD)
    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)
    def __truediv__(self, m):
        return mint(self.i * (m ** (MOD - 2)).i % MOD)
    def __repr__(self):
        return repr(self.i)

fact_range = 200005
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % MOD

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], MOD - 2, MOD)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % MOD

def comb(n, k):
    if k < 0 or n < k:
        return mint(0)
    else:
        return mint(facts[n] * ifacts[n-k] % MOD * ifacts[k] % MOD)

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


l = [mint(m) * (mint(m-1) ** (n-1-i)) * comb(n-1, n-1-i) for i in range(n)]
ans = mint(0)
for i in range(k+1):
    ans = ans + l[i]
print(ans)

Submission status: Wrong Answer

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

mod = 998244353
NUM = 3*(10**5)
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

for i in range( 2, NUM + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inv.append( ( -inv[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inv[-1]) % mod )

def comb(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

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

print(ans)

Submission status: Wrong Answer

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

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
  
ans = 0
ans2 = 1
#X = 1
for i in range(K + 1):
  if i == 0:
    X = 1
  else:
    X = int(X * (N - i) / i) % MOD
  ans2 = X * B[N - 1 - i] % MOD 
  ans += ans2
  ans = ans % MOD
  
ans = (M * ans) %MOD
print(ans)

Submission status: Wrong Answer

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

C = [1]
for i in range(N):
    if i == 0:
        C.append(M)
    else:
        C.append((C[i] * (M-1)) % 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 )


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


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

if M == 1:
    print(1)
else:
    print(ans % MOD)

Submission status: Wrong Answer

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

A = [0]*(K+1)
A[0] = (M*pow(M-1,N-1,mod)) % mod

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

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

print(ans)

Submission status: Wrong Answer

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

MAX = 2 * 10 ** 5 + 10

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = (fact[i-1] * i) % mod

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

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ans = 0
power = pow(m - 1, n - 1, mod)
for i in range(k + 1):
    ans += comb(n - 1, i) * m * power
    ans %= mod
    power *= inv[m - 1]
    power %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
INF=998244353
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
for i in range(k+1):
    if i==0:
        c=1
        temp=(m*pow(m-1,n-1))%INF
    else:
        x=modinv(i,INF)
        c=(c*x*(n-i))%INF
        temp=(temp*modinv(m-1,INF))%INF
    ans=(ans+c*temp)%INF
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        print(1)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac = copy.deepcopy(fac)
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
    
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
    
    ans = 0
    base = pow(M-1,N-K-1,MOD)
    for i in reversed(range(K+1)):
        ret = comb(N-1,i)*(M*base)
        ans += ret
        base *= (M-1)
    
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dict = {}
def pow(x, n):
    ans = 1
    if n in dict:
        return dict[n]
    n_tmp = n
    while n:
        if n % 2:
            ans *= x
            ans %= mod
        x *= x
        n >>= 1
    dict[n_tmp] = ans
    return ans


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] #逆元テーブル計算用テーブル

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*pow(m-1, n-1) % mod
for i in range(1, k+1):
    tmp_ans = cmb(n-1, i, mod)
    tmp_ans *= pow(m, i)
    tmp_ans %= mod
    tmp_ans *= pow(m-1, n-i+1)
    tmp_ans %= mod
    ans += tmp_ans
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import math

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

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    fact_inv.append(pow(fact[-1],MOD-2,MOD))

def combinations_count(n, r):
    return (fact[n] * fact_inv[n-r] * fact_inv[r])%MOD


for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * pow(M-1,N-1-i,MOD) * combinations_count(N-i,i)
        SUM %= MOD

print(SUM)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 998244353
N, M, K = map(int, input().split())
def cumprod(x, MOD = mod):
	L = len(x)
	Lsq = int(L**.5 + 1)
	x = np.resize(x, Lsq ** 2).reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		x[:,n] *= x[:,n-1]
		x[:,n] %= MOD
	for n in range(1,Lsq):
		x[n] *= x[n-1, -1]
		x[n] %= MOD
	return x.flatten()[:L]

def make_fact(U, MOD = mod):
	x = np.arange(U, dtype = np.int64)
	x[0] = 1
	fact = cumprod(x, MOD)
	x = np.arange(U, 0, -1, dtype = np.int64)
	x[0] = pow(int(fact[-1]), MOD - 2, MOD)
	fact_inv = cumprod(x, MOD)[::-1]
	return fact, fact_inv

fact, fact_inv = make_fact(N+10)


ans = 0
D = M * ((M-1) ** (N-1))
D %= mod
for i in range(K+1):
	if i == 0:
		ans += D
	else:
		d = fact[N-1]
		d *= fact_inv[i]
		d %= mod
		d *= fact_inv[N-1-i]
		d %= mod

		tmp = d * D
		tmp %= mod
		ans += tmp

	ans %= mod		
	D *= pow(M-1, mod-2, mod)
	D %= mod

ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    fact_inv.append(pow(fact[-1],MOD-2,MOD))

print(fact)

def combinations_count(n, r):
    return (fact[n] * fact_inv[n-r] * fact_inv[r])%MOD


for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * pow(M-1,N-1-i,MOD) * combinations_count(N-i,i)
        SUM %= MOD

print(SUM)

Submission status: Wrong Answer

Solution code:
def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        print(1)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*pow(fac[y],MOD-2,MOD)*pow(fac[x-y],MOD-2,MOD))%MOD
    
    ans = 0
    base = pow(M-1,N-K-1,MOD)
    for i in reversed(range(K+1)):
        ret = comb(N-1,i)*(M*base)
        ans += ret
        ans %= MOD
        base *= (M-1)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 998244353
N, M, K = map(int, input().split())
def cumprod(x, MOD = mod):
	L = len(x)
	Lsq = int(L**.5 + 1)
	x = np.resize(x, Lsq ** 2).reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		x[:,n] *= x[:,n-1]
		x[:,n] %= MOD
	for n in range(1,Lsq):
		x[n] *= x[n-1, -1]
		x[n] %= MOD
	return x.flatten()[:L]

def make_fact(U, MOD = mod):
	x = np.arange(U, dtype = np.int64)
	x[0] = 1
	fact = cumprod(x, MOD)
	x = np.arange(U, 0, -1, dtype = np.int64)
	x[0] = pow(int(fact[-1]), MOD - 2, MOD)
	fact_inv = cumprod(x, MOD)[::-1]
	return fact, fact_inv

fact, fact_inv = make_fact(N)


ans = 0
D = M * ((M-1) ** (N-1))
D %= mod
for i in range(K+1):
	if i == 0:
		ans += D
	else:
		d = fact[N-1]
		d *= fact_inv[i]
		d %= mod
		d *= fact_inv[N-1-i]
		d %= mod

		tmp = d * D
		tmp %= mod
		ans += tmp

	ans %= mod		
	D *= pow(M-1, mod-2, mod)
	D %= mod

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float("INF")
fact = [i for i in range(2 * 10 ** 5 + 1)]
fact[0] = 1
for i in range(2 * 10 ** 5):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod
invfact = [None] * (2 * 10 ** 5 + 1)
invfact[-1] = pow(fact[-1], mod - 2, mod)
for i in range(2 * 10 ** 5, 0, -1):
    invfact[i - 1] = invfact[i] * i
    invfact[i - 1] %= mod
def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = fact[n]
    b = invfact[k]
    c = invfact[n - k]
    return (a * b * c) % mod
#solve
def solve():
    n, m, k = LI()
    ans = 0
    tmp = m
    for i in range(n - 1):
        tmp *= m - 1
        tmp %= mod
    for i in range(k + 1):
        ans += tmp * combination_mod(n - 1, i, mod)
        tmp *= pow(m - 1, mod - 2, mod)
        tmp %= mod
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
nn = 200200
P = 998244353

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

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0
N, M, K = map(int, input().split())
ans = 0
t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
for i in range(K+1):
    ans = (ans + t * C(N-1, i)) % P
    t = t * m % P
print(ans * M % P)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*pow(b,p-2,p)*pow(c,p-2,p))%p
n, m, k = map(int, input().split())
ans = 0
mod = 998244353
for i in range(k+1):
    ans += m*comb(n-1, i, mod)*pow(m-1, n-i-1, mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = alpha*(N-k)//(k)
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
from functools import reduce
from functools import lru_cache

mod = 998244353


# \n
def input():
    return sys.stdin.readline().rstrip()

def cmb(n, r):
    if r==0:
        return 1
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod


def main():
    N, M, K = map(int, input().split())
    ans = 0
    for i in range(K + 1):
        basic = M * pow(M - 1, N - 1 - i, mod) % mod
        ans += basic * cmb(N - 1, i)
        ans = ans%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def cin():  return list(map(int,input().split()))

def cmb(n, r):
    INF = 998244353
    r = min(n - r, r)
    if r == 0:  return 1
    numer = reduce(lambda x, y: (x * y) % INF, range(n, n - r, -1))
    denom = reduce(lambda x, y: (x * y) % INF, range(1, r + 1))
    return (numer * pow(denom, INF - 2, INF)) % INF

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
factorial = None
inverse_factorial = None


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


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


def init_nCr(max_n):
    global factorial, inverse_factorial
    factorial = [1]*(max_n+1)
    inverse_factorial = [0]*(max_n+1)
    for i in range(1, max_n+1):
        factorial[i] = (factorial[i-1]*i)%MOD
        inverse_factorial[i] = modpow(factorial[i], MOD-2)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
factorial = [1]
inverse_factorial = [0]


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


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


def init_nCr(max_n):
    for i in range(1, max_n+1):
        f = (factorial[-1]*i)%MOD
        factorial.append(f)
        inv_f = modpow(f, MOD-2)
        inverse_factorial.append(inv_f)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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


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


def paint(k):
    res = (m * comb(n-1, k) % mod) * pow(m-1, n-1-k, mod)
    res % mod
    return res

ans = 0
for k in range(K+1):
    ans += paint(k)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

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

if N==1:
    print(M)
else:
    ans = 0
    mm_1 = M
    if K < (N-1):
        mm_1 = (mm_1 * (M-1)**(N-K-2))%MOD


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

    print(ans)