Problem: 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.

Submission attempts (in order):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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


N = 10**3*3
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 )

if n//2 > k:
    print(aall-cmb(n+p,p,mod))
    exit()

print(aall)

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353

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

N = 10 ** 6  
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

ans = 0

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

print(ans*m%mod)

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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

mod = 10**9+7 
N = 10**3*3
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 )

if n//2 > k:
    print(aall-cmb(n+p,p,mod))
    exit()

print(aall)

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353
aall = pow(m,n,mod)

p = n-k+1


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

mod = 10**9+7 
N = 10**3*3
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 )

print(aall-cmb(n+p,p,mod))

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
mod = 998244353


fact = [0] * 220000
invfact = [0] * 220000
 
fact[0] = 1
for i in range(1, 220000):
    fact[i] = fact[i-1] * i % mod
 
invfact[220000 - 1] = pow(fact[220000 - 1], mod-2, mod)
 
for i in range(220000 - 2, -1, -1):
    invfact[i] = invfact[i+1] * (i+1) % mod
 
def nCk(n, k):
    if k < 0 or n < k:return 0
    return fact[n] * invfact[k] * invfact[n-k] % mod
 
ans = 0

for i in range(k+1):
    ans += pow(m-1,n-i-1,mod)*nCk(n-1,i)

print(ans*m%mod)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Accepted