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: Accepted

Solution code:
MOD = 10000000007
lim = 200000
MOD = 998244353

inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        if inv_t[i] == -1:
            _ = mod_inv(i)
            inv_t[i] = _


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % MOD


n, m, k = [int(_) for _ in input().split()]
ans = 0
set_inv()
set_factrial()
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    # print(ans)
print(ans)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac_inv[n-i]*frac_inv[i-1]%mod
    ans%=mod
print(ans*frac[n-1]%mod)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac_inv[n-i]*frac_inv[i-1]
    ans%=mod
print(ans*frac[n-1]%mod)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac_inv[n-i]*frac_inv[i-1]%mod
print(ans*frac[n-1]%mod)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac[n-1]%mod*frac_inv[n-i]*frac_inv[i-1]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

for i in range(1,n+1):
    frac[i]=frac[i-1]*i%mod
    frac_inv[i]=inv(frac[i],mod)
    beki[i]=beki[i-1]*(m-1)%mod
ans=0
for i in range(n-k,n+1):
    ans+=beki[i-1]*frac[n-1]*frac_inv[n-i]*frac_inv[i-1]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while 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

mod=998244353
n,m,k=map(int,input().split())
frac=[1];frac_inv=[1]
beki=m
ans=0

for i in range(1,n+1):
    frac.append(frac[-1]*i%mod)
    frac_inv.append(inv(frac[-1],mod))

for i in range(n-k-1):
    beki=beki*(m-1)%mod
for i in range(n-k,n+1):
    ans+=beki*frac[n-1]*frac_inv[n-i]*frac_inv[i-1]%mod
    beki=beki*(m-1)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  MOD=998244353
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, m, k = 60522, 114575, 7559

  else:
    ##INPUT 
    #n = input()
    n, m, k = map(int, input().split())

  ## SUBMITION CODES HERE
  fac = [1] * (n+1)
  inv = [1] * (n+1)

  for i in range(n):
    fac[i+1] = fac[i] * (i+1) % MOD # Calculating the Factorial 
    inv[i+1] = pow(fac[i+1], MOD-2, MOD) # The inverse of the MOD's law (Fermat's Little Theorem)
  
  def nCr(n, r):
    if 2*r > n: nCr(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % MOD
  
  ans = 0
  for i in range(k+1):
    tmp = nCr(n-1, i) * m * pow(m-1, n-1-i, MOD) 
    ans += tmp
    ans %= MOD
  print(ans)

main()

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  MOD=998244353
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, m, k = 60522, 114575, 7559

  else:
    ##INPUT 
    #n = input()
    n, m, k = map(int, input().split())

  ## SUBMITION CODES HERE
  ans, N, K = 0, 1, 1
 
  for i in range(k+1):
    ans += N * pow(K, MOD-2, MOD) * pow(m-1, n-1-i, MOD)
    ans %= MOD
    N *= n-1-i
    N %= MOD
    K *= i+1
    K %= MOD
  
  ans *= m
  ans %= MOD
  print(ans)

main()

Submission status: Accepted

Solution code:
MOD = 998244353

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

fact = [0 for _ in range(n)]
invfact = [0 for _ in range(n)]
fact[0] = 1
for i in range(1, n):
    fact[i] = fact[i - 1] * i % MOD

invfact[n - 1] = pow(fact[n - 1], MOD - 2, MOD)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

p = MOD
N = 2 * 10 ** 5 + 10
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 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

res = 0
for i in range(k + 1):
    res += m * pow(m - 1, n - i - 1, MOD) * cmb(n - 1, i, MOD)
    res %= MOD

res %= MOD
print(res)

Submission status: Accepted

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

fact = [0] * 200001
invfact = [0] * 200001
fact[0] = 1
invfact[0] = 1

for i in range(1, 200001):
    fact[i] = fact[i-1] * i % mod
    
invfact[-1] = pow(fact[-1], mod-2, mod)

for i in reversed(range(1, 200000)):
    invfact[i] = invfact[i+1] * (i+1) % mod

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

ans = ans * M * fact[N-1] % mod

print(ans)

Submission status: Accepted

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

MOD = 998244353  # type: int


MAX = 600000
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD
 
def combination(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD

def solve(N: int, M: int, K: int):
    ans = 0
    for k in range(K+1): 
        ans += combination(N-1,N-k-1) * M * pow(M-1, N-k-1, MOD) % MOD
        ans %= MOD
    
    print(ans)

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def main():
    MOD = 998244353

    n, m, k = map(int, input().split())
    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(0, k+1):
        ans += m * pow(m-1, n-i-1, MOD) * nCk(n-1, i) % MOD

    print(ans%MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX = 600000
MOD = 998244353
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD
n, m, k = map(int ,input().split())
ans = 0
color = m
for i in reversed(range(n)):
    val = color
    val *= combinations(n-1,i)
    val %= MOD
    if i <= k:
        ans += val
        ans %= MOD
    color *= (m-1)
    color %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
n,m,k=reads()
N = n-1 # N は必要分だけ用意する
mod =  998244353
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 + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

mod=998244353
numbers=[m]
for i in range(n-1):
  numbers.append(numbers[i]*(m-1)%mod)
ans=0
for i in range(k+1):
  ans+=numbers[n-i-1]*cmb(n-1,i)
ans%=mod
#print(numbers)
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 998244353
nums = 2*(10**5) # 制約に合わせよう
g1, g2, inverse = [1, 1] , [1, 1], [0, 1]
 
for num in range(2, nums + 1):
    g1.append((g1[-1] * num) % mod)
    inverse.append((-inverse[mod % num] * (mod//num)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

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

Submission status: Accepted

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


basum=0
for i in range(k+1):
	if i == 0:
		kumiawase=1
	else:
		kumiawase = kumiawase*(n-i)*pow(i,wari-2,wari)
		kumiawase %= wari
	basum += m * pow(m-1,n-i-1,wari) * kumiawase
	basum %= wari

print(basum)

Submission status: Accepted

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 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
 
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range(2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

Submission status: Accepted

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 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
 
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range(2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m,k=map(int,input().split())
mod=998244353
n_max=2*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

P=[1]
for i in range(n):
  P.append((P[-1]*(m-1))%mod)

ans=0
for i in range(k+1):
  ans+=m*P[n-1-i]*comb(n-1,i)
  if ans>mod:
    ans%=mod
print(ans)

Submission status: Accepted

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

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

    def get_fact(maxim,mod):
        maxim += 1
        fact = [0]*maxim

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

        invfact = [0]*maxim
        invfact[maxim-1] =  pow(fact[maxim-1],mod-2,mod)

        for i in reversed(range(maxim-1)):
            invfact[i] = invfact[i+1] * (i+1) % mod

        return fact, invfact

    def powerful_comb(n,r,mod,fact,invfact):
        return fact[n] * invfact[r] * invfact[n-r] % mod

    ans = 0
    fact, invfact = get_fact(N+1,MOD)
    for i in range(K+1):
        ans += (M*pow(M-1,N-i-1,MOD) * powerful_comb(N-1,i,MOD,fact,invfact)) % MOD

    print(ans % MOD)

if __name__ == "__main__":
  main()

Submission status: Accepted

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, 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: Accepted

Solution code:
M=998244353
n,m,k=map(int,input().split())
p,c=[m]*n,[1]*n
for i in range(1,n):
  p[i]=p[i-1]*(m-1)%M
  c[i]=c[i-1]*(n-i)*pow(i,M-2,M)%M
print(sum(p[n-i-1]*c[i]%M for i in range(k+1))%M)

Submission status: Accepted

Solution code:
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 998244353

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

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]; fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]; fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N+1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N-1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]; finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]; finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    comb = fac[a] * finv[b] % mod * finv[a-b] % mod
    return comb


prt = [1] * (n + 1)
for i in range(n):
    prt[i + 1] = prt[i] * (m - 1) % mod

res = 0
for i in range(k + 1):
    res += m * prt[n - i - 1] % mod * nCr(n-1, i)
    res %= mod
print(res)

Submission status: Accepted

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

fa = [1] * (lim + 1)
fa_inv = [1] * (lim + 1)

for i in range(lim):
    fa[i+1] = fa[i] * (i+1) % modi

fa_inv[-1] = pow(fa[-1], modi - 2, modi)
for i in range(lim - 1, 0, -1):
    fa_inv[i] = fa_inv[i+1] * (i+1) % modi


def ncr(a, b):
    if a < b:
        return 0
    else:
        return fa[a] * fa_inv[b] % modi * fa_inv[a - b] % modi


prt = [1] * (n + 1)
for i in range(n):
    prt[i+1] = prt[i] * (m - 1) % modi

res = 0
for i in range(k + 1):
    res += m * prt[n - i - 1] * ncr(n - 1, i) % modi
    res %= modi
print(res)

Submission status: Accepted

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


mod = 998244353
N = 2 * 10**5  # 出力の制限
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)


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

m_pow = [0] * N
m_pow[0] = 1

for i in range(1, N):
    m_pow[i] = m_pow[i - 1] * (M - 1) % mod

ans = 0

for i in range(K+1):
    ans = (ans + cmb(N - 1, i, mod) * M * m_pow[N - 1 - i]) % mod

print(ans)

Submission status: Accepted

Solution code:
mod  = 998244353
MAX = 2*10**5 + 100

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

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(g2[-1]*inv[i]%mod)
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod


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

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

Submission status: Accepted

Solution code:
def comb(n,r,m):
    if 2*r > n:
        r = n - r
    nume,deno = 1,1
    for i in range(1,r+1):
        nume *= (n-i+1)
        nume %= m
        deno *= i
        deno %= m

    return (nume * pow(deno,m-2,m)) % m

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

    ans,comb_r = pow(M-1,N-1,mod),1
    for r in range(1,K+1):
        comb_r = (comb_r * (N-r) * pow(r,mod-2,mod)) % mod
        ans = (ans + comb_r * pow(M-1,N-r-1,mod)) % mod
    ans = (ans * M) % mod

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == self.N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c
if N == 1:
    print(M%m)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)

Submission status: Accepted

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

class Combination:
  def __init__(self, n_max, mod=998244353):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

comb = Combination(2*10**5)

res = 0
for x in range(K+1):
  res += (M * pow(M-1, N-x-1, MOD)%MOD * comb(N-1, x)%MOD)%MOD
  res %= MOD

print(res % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class Factorial:
    def __init__(self, n, mod):
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = pow(self.f[n], -1, mod)
        for i in range(n,0,-1):inv[i-1] = b = b * i % mod
        self.mod = mod
    def factorial(self, i):
        return self.f[i]
    def ifactorial(self, i):
        return self.inv[i]
    def comb(self, n, k):
        if n >= k:return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod
        else:return 0

MOD = 998244353
nCr = Factorial(5*10**5, MOD).comb
N, M, k = map(int, input().split())
print(sum(nCr(N - 1, x) * M * pow(M - 1, N - x - 1, MOD) % MOD for x in range(-~k)) % MOD)

Submission status: Accepted

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=998244353):
        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: Accepted

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

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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
ans = 0
for k in range(K+1):
    ans += M*pow(M-1, N-1-k, mod)*cmb(N-1, k, mod)
    ans %= mod

print(ans)

Submission status: Accepted

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

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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Accepted

Solution code:
M=998244353
n,m,k=map(int,input().split())
p,c=[m],[1]
for i in range(1,n):
  p+=[p[-1]*(m-1)%M]
  c+=[c[-1]*(n-i)*pow(i,-1,M)%M]
print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Submission status: Accepted

Solution code:
M=998244353
n,m,k=map(int,input().split())
a,c=0,1
for i in range(k+1):
  a+=c*m*pow(m-1,n+~i,M)
  c=c*(n+~i)*pow(i+1,-1,M)%M
print(a%M)

Submission status: Accepted

Solution code:
M=998244353
n,m,k=map(int,input().split())
a=0
c=1
for i in range(k+1):
  a+=c*m*pow(m-1,n-i-1,M)
  c=c*(n-i-1)*pow(i+1,M-2,M)%M
print(a%M)

Submission status: Accepted

Solution code:
M=998244353
n,m,k=map(int,input().split())
p,c=[m],[1]
for i in range(1,n):
  p+=[p[-1]*(m-1)%M]
  c+=[c[-1]*(n-i)*pow(i,M-2,M)%M]
print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Submission status: Accepted

Solution code:
import math
#import copy

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


def paint(N,M,K):
    return 

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

    pow_list = [0] * (N)
    pow_list[0] = 1
    for i in range(1, N):
        pow_list[i] = pow_list[i-1]*(M-1) % mod
    for i in range(0,K+1):
        ans = ans + M*cmb(N-1, i)*pow_list[N-1-i]
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod2 - 2, mod2)

cms = 10**6
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod2

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod2) * inv(cm[b]) % mod2

def main():
    n,m,k = LI()
    comb_init()

    a = [0] * n
    a[0] = m
    for i in range(1,n):
        a[i] = a[i-1] * (m-1) % mod2

    r = 0
    for i in range(k+1):
        r += a[n-i-1] * comb(n-1, i)
        r %= mod2

    return r

print(main())

Submission status: Accepted

Solution code:
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 invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

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

ans = m * pow(m-1, n-1, mod=c)
temp = 1
for i in range(1, k+1):
    temp = temp*(n-i) % c
    temp = temp*invmod(i, c) % c
    ans += temp * m * pow(m-1, n-1-i, mod=c)
    ans = ans % c
print(ans%c)