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:
n, m, k = map(int, input().split())
mod = 998244353
def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % mod

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

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

Submission status: Wrong Answer

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

for i in range(k):
  x = 1

Submission status: Wrong Answer

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

    fac = [0] * 10 ** 6
    inv = [0] * 10 ** 6
    finv = [0] * 10 ** 6

    def COM_init():
        fac[0] = 1
        fac[1] = 1
        inv[1] = 1
        finv[0] = 1
        finv[1] = 1

        for i in range(2, 10**5+10):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = -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[n-k] * finv[k] % MOD) % MOD

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod if n>= r else 0
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m , k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    inv = pow(m-1,mod-2,mod)
    rem = pow(m-1, n-1, mod)
    for i in range(k+1):
        ans += c.combination(n-1,i)*rem
        ans %= mod
        rem *= inv
        rem %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m , k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    inv = pow(m-1,mod-2,mod)
    rem = pow(m-1, n-1, mod)
    for i in range(k+1):
        ans += c.combination(n-1,i)*rem
        ans %= mod
        rem *= inv
        rem %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m , k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    inv = pow(m-1,mod-2,mod)
    rem = pow(m-1, n-1, mod)
    for i in range(k+1):
        ans += c.combination(n-1,i)*m*rem
        ans %= mod
        rem *= inv
        rem %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m , k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    bym = pow(m-1,mod-2,mod)
    rem = pow(m-1, n-1, mod)
    for i in range(k+1):
        ans += c.combination(n-1,i)*m*rem
        ans %= mod
        rem *= bym
        rem %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Cmb:
    def __init__(self, N, mod=998244353):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,m,k = map(int,input().split())
mod = 998244353
ans = 0
c = Cmb(N=n, mod=mod)
for x in range(k+1):
    if x==0:
        ans += m*pow(m-1, n-1, mod)
        ans %= mod
    else:
        ans += m*pow(m-1, n-1-x, mod)*c(n-1, x)%mod
        ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:

"""nCk (逆元ver) """
def comb(n,k):
    nCk = 1
    mod = 10**9+7
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
    for i in range(1, k+1):
        nCk *= pow(i, mod-2, mod)
        nCk %= mod
    return nCk

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

for x in range(k+1):
    if x==0:
        ans += m*pow(m-1, n-1, mod)
        ans %= mod
    else:
        ans += m*pow(m-1, n-1-x, mod)*comb(n-1, x)
        ans %= mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math
#import copy

from operator import mul
from functools import reduce

def cmb(g1, g2, 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

def pow_kai(a, n):
    x = 1
    while(n > 0):
        if(n&1):
            x = x*a
        a = a*a
        n >>= 1
    return x


def paint(N,M,K):
    return 

def main():
    N, M, K = map(int, input().split())
    ans = 0

    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 )

    for i in range(0,K+1):
        ans = ans + M*cmb(g1, g2, N-1, i, mod)*(pow_kai(M-1, N-1-i))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=998244353
def comb(a,b):
  s=1
  t=1
  for i in range(1,b+1):
    s=s*i%mod
    t=t*(a-i+1)%mod
  return (t*pow(s,mod-2,mod))%mod
ans=0
for i in range(k+1):
  ans+=comb(n-1,i)*m*pow(m-1,i,mod)
  ans%=mod
print(ans)

Submission status: Wrong Answer

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

CONV = [0] * (K + 1)
KAIJ = [0] * (K + 1)
ans = 0
CONV[0] = 1
KAIJ[0] = (M-1) ** (N-1-K) % MOD

for k in range(1, K+1):
  CONV[k] = CONV[k-1] * (N-k) // k % MOD
  KAIJ[k] = KAIJ[k-1] * (M-1) % MOD

for k in range(K+1):
  # M x (N-1)Ck x (M-1) ^ (N - 1 - k)
  ans += (CONV[k] * KAIJ[-k-1]) % MOD
  
print(ans * M % MOD)

Submission status: Wrong Answer

Solution code:
def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


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

    nCi = [1]
    for i in range(1, N):
        nCi.append(nCi[i - 1] * (N - i) * inverse(i, mod) % mod)
        # nCi.append(nCi[i - 1] * (N - i + 1) // i)
    print(nCi)
    ans = 0
    for k in range(K + 1):
        n = N - k
        ans += M * int(pow((M - 1), n - 1, mod)) * nCi[k]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod = 998244353
nCi = [1]#n-1からi個えらぶ場合の数
for i in range(n):
  next = nCi[i]*(n-1-i)*pow(i+1,mod-2,mod)
  next %= mod
  nCi.append(next)
print(nCi)
ans = 0
for i in range(k+1):
  ans += m*pow(m-1,n-i-1,mod)*nCi[i]
  ans %= mod
print(ans)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

if N == 1:
  print(M)
  exit()

now = M * pow(M-1, N-1, MOD)
ans = now
if K == 0:
  print(ans % MOD)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

now = M * pow(M-1, N-1, MOD)
ans = now
if K == 0:
  print(ans % MOD)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

now = M * pow(M-1, N-1, MOD)
ans = now
if K == 0:
  print(ans)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

now = M * pow(M-1, N-1, MOD)
ans = now
if K == 1:
  print(ans)
  exit()

for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

now = M * pow(M-1, N-1, MOD)
ans = now
for ki in range(1, K+1):
  now = now * invmod[M-1] * (N-ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

MOD = 998244353
invmod = [pow(i, MOD-2, MOD) for i in range(200002)]

now = M * pow(M-1, N-1, MOD)
ans = now
for ki in range(1, K+1):
  now = now * invmod[M] * (N+ki) * invmod[ki] % MOD
  ans += now
  
print(ans % MOD)

Submission status: Wrong Answer

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

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)

    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=pow(M-1,N-1-i,MOD)

        if i!=0:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
p = 998244353
N = 2*10**5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

def main():
    n, m, k = [int(i) for i in input().split()]
    res = 0
    for tk in range(0, k+1):
        res += (m * cmb(n-1, tk, p) * (m-1)**(n-tk-1)) % p
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
p = 998244353
N = 10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

def main():
    n, m, k = [int(i) for i in input().split()]
    res = 0
    for tk in range(0, k+1):
        res += (m * cmb(n-1, tk, p) * (m-1)**(n-tk-1)) % p
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
p = 998244353
N = 10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

def main():
    n, m, k = [int(i) for i in input().split()]
    res = 0
    for tk in range(0, k+1):
        res += m * cmb(n-1, tk, p) * (m-1)**tk % p
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
pass

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
  
  
  ncp = m * pow(m-1, n-1, MAX)
  divmm1 = pow(m-1, MAX-2, MAX)
  cnt = ncp
  cmb = 1
  for ik in range(1, k+1):
    ncp *= divmm1
    ncp %= MAX
    
    cmb *= ((n-ik) * pow(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 998244353
  n, m, k = map(int, input().split())
  
  def pow_mod_p(n, k, p):
    x = 1
    while k:
      if k % 2 == 1:
        x *= n
        x %= p
      n **= 2
      n %= p
      k >>= 1
    return x
  
  ncp = m * pow_mod_p(m-1, n-1, MAX)
  divm = pow_mod_p(m-1, MAX-2, MAX)
  cnt = ncp
  cmb = 1
  for ik in range(1, k+1):
    ncp *= divm
    ncp %= MAX
    
    cmb *= ((n-ik) * pow_mod_p(ik, MAX-2, MAX))
    cmb %= MAX
    
    cnt += ncp * cmb
    cnt %= MAX
    
  print(cnt % MAX)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
stdin=sys.stdin


ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))


p=998244353
N,M,K=nm()

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

def comb(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_M=[0,(M-1)%p]
for i in range(2,N):
    mod_M.append((mod_M[i-1]*(M-1))%p)

ans=0
ans+=(M*mod_M[N-1])%p

if(K>0):
    for i in range(1,K+1):
        ans+=(M*mod_M[N-i-1]%p)*comb(N-1,i,p)
        ans%=p

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin=sys.stdin


ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))


p=998244353
N,M,K=nm()

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

def comb(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_M=[0,(M-1)%p]
for i in range(2,N):
    mod_M.append(mod_M[i-1]*(M-1)%p)

ans=0
ans+=(M*mod_M[N-1])%p

if(K>0):
    for i in range(1,K+1):
        ans+=M*mod_M[N-i-1]*comb(N-1,i,p)
        ans%=p

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin=sys.stdin


ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))


p=998244353
N,M,K=nm()

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

def comb(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_M=[0,(M-1)%p]
for i in range(2,N):
    mod_M.append(mod_M[i-1]*(M-1)%p)

ans=0
ans+=(M*mod_M[N-1])%p
for i in range(1,K+1):
    ans+=M*mod_M[N-i]*comb(N-1,i,p)
    ans%=p

print(ans)

Submission status: Wrong Answer

Solution code:
#factorial
MOD = 998244353 
N = 1000000
modinv_t = [0, 1]
modfact_t = [1, 1]
modfactinv_t = [1, 1]
for i in range(2,N+1):
  modfact_t.append(modfact_t[-1] * i % MOD)
  modinv_t.append(modinv_t[MOD%i] * (MOD-(MOD//i)) % MOD)
  modfactinv_t.append(modfactinv_t[-1] * modinv_t[-1] % MOD)
# permutation
def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD
# combination
def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD
#
def nHr(n, r):
  return  nCr(n+r-1,r)
#

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# nCr(mod) -- START --
class ComMod():
  def __init__(self,n,mod):
    self.n=n
    self.mod=mod
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=self.mod
    self.ifact[n]=pow(self.fact[n],self.mod-2,self.mod)
    for i in range(n,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=self.mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod
# nCr(mod) --- END ---

# n^p(mod m) -- START --
def powMod(n,p,m):
  if p==0:
    return 1
  if p%2==0:
    t=powMod(n,p//2,m)
    return t*t%m
  return n*powMod(n,p-1,m)%m
# n^p(mod m) --- END ---

def main():
  n,m,k=LI()
  mod=998244353
  c=ComMod(200005,mod)


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

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
# 組み合わせ(N > 10 ** 7 でも可能)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 998244353

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


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

print(ans%mod)

Submission status: Wrong Answer

Solution code:
# 組み合わせ(N > 10 ** 7 でも可能)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 998244353

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


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

print(ans%mod)

Submission status: Wrong Answer

Solution code:
# 組み合わせ(N > 10 ** 7 でも可能)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 998244353

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


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

print(ans%mod)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0:return 1
    over = reduce(mul,range(n,n-r,-1))
    under = reduce(mul,range(1,r+1))
    return over//under


if __name__ == '__main__':
    nkm = input()
    nkm = nkm.split()
    n = int(nkm[0])
    m = int(nkm[1])
    k = int(nkm[2])

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

    ans%=998244353

    print(ans)

Submission status: Wrong Answer

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

c = [1 for i in range(K+1)]
if K > 1:
    c[1] = N-1
for i in range(2, K+1):
    c[i] = ( c[i-1] * (N-i) / i ) %mod
ans = 0
for k in range(K+1):
    x = M * pow(M-1, N-1-k, mod) * c[k]
    ans += x%mod
    ans = ans %mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
P=998244353
class FactInv:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[0]*(N+1);ifact=[0]*(N+1);fact[1]=1
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def Comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
FI=FactInv(N+10,P)
ans=0
for i in range(0,K+1):
    ans+=(M*FI.Comb(N-1,i)*pow(M-1,N-1-i,P))%P
    ans%=P
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


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

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


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

Submission status: Wrong Answer

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

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 = 2 * 10**5 + 1

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

y = [0,m]
for i in range(n):
    y.append((y[-1]*(m-1))%p)
r = 0
for i in range(k+1):
    r += (y[n-i]*cmb(n-1, i, p))%p
print(r)

Submission status: Wrong Answer

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

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 = 2 * 10**5 + 1

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

y = [0,m]
for i in range(n-1):
    y.append(y[-1]*(m-1))
r = 0
for i in range(k+1):
    r += (y[n-i]*cmb(n-1, i, p))%p
print(r)

Submission status: Wrong Answer

Solution code:
# from scipy.special import comb # comb(n,k,exact=True). 'exact=True' to return integer.
n, m, k = map(int,input().split())
mod = 998244353

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

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

for i in range(1,k+1): # choose pairs and add
    count_tmp //= (m-1)
    comb_tmp *= ((n-1)-(i-1))
    comb_tmp = max(comb_tmp, 1)//i
    count += (count_tmp * comb_tmp)
    # print(count_tmp,comb_tmp,count)
    # print(i,comb_tmp,comb(n-1,i,exact=True),((n-1)-(i-1))%i)
    # if comb_tmp != comb(n-1,i,exact=True):
    #     break

print(count%mod)
# print(479519525)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def caa(m,n):
    x = m * ((m-1) ** (n-1))
    return x

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

for i in range(0,K+1):
    c = combinations_count(N-i,i)
    y = caa(M,(N-i))
    ans += c * y
    ans = ans % 998244353

print('{}'.format(ans))