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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

#コンビネーション
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 = 3 * (10 ** 5)  # N は必要分だけ用意する
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)

n, m, k = MAP()

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

Submission status: Accepted

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

mod = 998244353

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, n):
    fac.append(fac[-1] * i % mod)
    inv.append(-inv[mod%i] * (mod // i) % mod)
    finv.append(finv[-1] * inv[-1] % mod)

ans = 0
for i in range(n-k-1, n):
    com = fac[n-1] * finv[i] * finv[n-i-1] % mod
    res = m
    e = m - 1
    while i > 0:
        if i & 1:
            res = res * e % mod
        e = e * e % mod
        i >>= 1
    res = res * com % mod
    ans = (ans + res) % mod

print(ans)

Submission status: Accepted

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

start=(M*pow(M-1,N-1,P))%P



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

    def comb(n,k):
        return fac[n]*(finv[k]*finv[n-k]%P)%P



    comp=0
    last=(N-1)-K #K=0ならthru
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
    comp=(comp*M)%P

    print((start+comp)%P)

else:
    print(M%P)

Submission status: Accepted

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

fac = [1]*(n+1)
per = [1]*(n+1)
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    per[i] = pow(fac[i],mod-2,mod)

def nCk(n,k):
    return fac[n]*per[k]%mod*per[n-k]%mod

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

Submission status: Accepted

Solution code:
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):
        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):
        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 main():
    n,m,k=map(int,input().split())
    mod=998244353
    modPow=[1]
    mPow=1
    ans=0
    if n==1:
        print(m)
    elif m==1:
        if k==n-1:
            print(1)
        else:
            print(0)
    else:
        comb=Combination(n-1)
        for i in range(n-1):
            mPow=(mPow*(m-1))%mod
            modPow.append(mPow)
        for i in range(n-1-k,n):
            ans+=(((m*modPow[i])%mod)*comb(n-1,i))%mod
        print(ans%mod)
if __name__=="__main__":
    main()

Submission status: Accepted

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):
    ans+=m*pow(m-1,n-1-i,mod)*mod_comb(n-1,i,mod)%mod
ans%=mod
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m,k=map(int,open(0).read().split())
p=998244353
'''
c=[1]*(k+1)
for i in range(1,k+1):
  c[i]=c[i-1]*(n-i)//i
  c[i-1]%=mod
'''
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 = n  # N は必要分だけ用意する
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)
ans=0
for i in range(k+1):
  ans+=m*pow(m-1,n-1-i,p)*cmb(n-1,i, p)
  ans%=p
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

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 998244353
ans = 0
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

Submission status: Accepted

Solution code:
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=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

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


n,m,k = map(int, input().split())
MOD = 998244353
ans = 0
comb = Combination(n)
for i in range(k + 1):
    tmp = m*power_func(m - 1, n - i - 1,MOD)%MOD
    tmp *= comb(n - 1,i)
    ans += tmp%MOD
print(ans%MOD)

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())

if k==n-1:
  print(pow(m,n,mod))
  exit()

ans = 0
a= m*pow(m-1,n-1-k-1,mod)

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

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
ans = 0
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 = 10**6  # N は必要分だけ用意する
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)
for i in range(0,k+1):
  ans += m*pow(m-1,n-1-i,mod)*cmb(n-1,i,p)
  ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

    # n-1Crとmの開錠を計算する
    X = max(N,M)+1
    a = [None] * X
    inva = [None] * X
    a[0] = 1

    for i in range(1, X):
        a[i] = i * a[i-1] % p

    inva[X-1] = pow(a[X-1],p-2,p)
    for i in range(X-1):
        inva[X-i-2] = inva[X-i-1] * (X-i-1) % p

    ans = 0
    for i in range(K+1):
        tmp = (a[N-1] * inva[i] % p) * inva[N-1-i] % p
        tmp = tmp * (M * pow(M-1,N-i-1,p) % p) % p 
        ans = (ans + tmp) % p
    print(ans % p)

if __name__ == '__main__':
    main()

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())

dp = [0]*(N+1)

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def a():
    mod = 998244353

    def bi(x):
        o = []
        while x != 0:
            o.append(x%2)
            x //= 2
        return o

    o = bi(mod - 2)
    leo = len(o)
    p = [0] * leo

    def modinv(m):
        p[0] = m
        for i in range(1,leo):
            a = p[i-1]
            a *= a
            a %= mod
            p[i] = a
        b = 1
        for i in range(leo):
            if o[i]:
                b *= p[i]
                b %= mod
        return b

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

    C = [1]*(K+1)
    for i in range(1,K+1):
        C[i] = (C[i-1] * (N-i) * modinv(i))%mod

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

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

    print(ans)

a()

Submission status: Accepted

Solution code:
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 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 = 998244353 #出力の制限
N = 10**6
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())
mod=998244353
A=0
for i in range(K+1):
 A+=powmod(M-1, N-1-i,mod)*cmb(N-1,i,mod)
 A%=mod
print((A*M)%mod)

Submission status: Accepted

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

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

mod = 998244353 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
ans =0
ml =[m-1]*n

if n ==1:
    print(m)
    exit()
elif m ==1:
    if k ==n-1:
        print(1)
        exit()
    else:
        print(0)
        exit()
for l in range(1,n):
    ml[l] = ml[l-1]*(m-1) % mod

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 998244353
n,m,k = map(int,input().split())
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod


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




res = 0

tmp = m*pow(m-1,n-k-1,mod)

for r in range(n-k-1,n):
    res = (res + tmp*mod_comb_k(n-1,r,mod)%mod)%mod
    tmp = tmp*(m-1)%mod

print(res)

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 = 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)
s = m
x = m
for i in range(k):
  s = (m*s)%p
for i in range(n-k-1):
  y = x*cmb(k+i,i,p)
  s = (m*s-y)%p
  x = (x*(m-1))%p
print(s)

Submission status: Accepted

Solution code:
MOD = 998244353
def main():
    N, M, K = (int(_) for _ in input().split())
    fact = [0] * (N + 1) # fact[n] = n!
    ifact = [0] * (N + 1)

    for i in range(N+1):
        if i == 0:
            fact[i] = 1
            continue
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N)[::-1]:
        ifact[i] = ((i+1) * ifact[i+1])%MOD

    out = [0] * N
    coef = 1
    for i in range(N):
        out[N-1-i] = (coef * M * fact[N-1] * ifact[i] * ifact[N-1-i])%MOD
        coef *= M-1
        coef %= MOD
    ret = 0
    for i in range(K+1):
        ret += out[i]
        ret %= MOD
    print(ret)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  # type: int


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        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
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        fac = self.fac
        finv = self.finv
        mod = self.MOD
        return fac[n] * (finv[k]*finv[n-k] % mod) % mod


def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


def solve(N: int, M: int, K: int):

    cmb = Combination(N)
    tot = 0
    for k in range(N-K, N+1):
        buf = cmb(N-1, k-1)
        buf *= (M*pow(M-1, k-1, MOD)) % MOD
        buf %= MOD
        # print(N, k, cmb(N, k), buf)
        tot += buf
        tot %= MOD
    print(tot)
    return


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:
import sys

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

# 前処理
def COMinit():
  fac[0] = 1
  fac[1] = 1
  finv[0] = 1
  finv[1] = 1
  inv[1] = 1
  for i in range(2,MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

# 二項係数計算
def COM(n, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
  
  
MAX=n+1
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################
def main():
    m=998244353
    N,M,K=list(map(int,input().split()))
    facs=get_facs(10**6,m)
    ssum=0
    for a in range(0,K+1):
        p=(pow(M-1,N-a-1,m)*M)%m
        q=comb(N-1,a,m,facs)
        r=(p*q)%m
        ssum+=r
        ssum%=m
    print(ssum)
main()

Submission status: Accepted

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

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

if M == 1 and K == N-1:
    print(1)
else:
    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: Accepted

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

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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 )

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

Submission status: Accepted

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

def cmb(n,r):
    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+100
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())
P=[1] #m-1のi乗

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

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

Submission status: Accepted

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

p = 998244353
N = 2* (10**5) +2 # N は必要分だけ用意する
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)


n, m, k = map(int, input().split())
r = m
x = [m]
for i in range(n-1):
    r = (r*(m-1))%p
    x.append(r)
z = n//2

for i in range(1, k+1):
    r = (r + x[-i-1]*cmb(n-1,i,p))%p
print(r)

Submission status: Accepted

Solution code:
N, M, K = list(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 = N + 100 # N は必要分だけ用意する
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)

Mpower = [1, M]
lpower = [1, M-1]
for i in range(2, _N + 1):
    Mpower.append((Mpower[-1] * M) % p)
    lpower.append((lpower[-1] * (M-1)) % p)

ans = Mpower[N]
for i in range(K+2, N+1):
    ans = ans - (cmb(N-1, i-1,p)*M *lpower[N-i]) % p
    ans = ans % p

print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
fact,factinv,mod=[1]*n,[1]*n,998244353
for i in range(2,n):
  fact[i]=fact[i-1]*i%mod
factinv[n-1]=pow(fact[n-1],mod-2,mod)
for i in range(n-2,0,-1):
  factinv[i]=factinv[i+1]*(i+1)%mod
ncr=lambda n,r:fact[n]*factinv[r]%mod*factinv[n-r]%mod
ans=pow(m,n,mod)
for i in range(k+1,n):
  ans+=mod-m*pow(m-1,n-i-1,mod)*ncr(n-1,i)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import scipy
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int

# def comb(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

from operator import mul
from functools import reduce


def modinv(a,*args):
    return pow(a, MOD - 2, MOD)

def combination_list(n, mod=MOD):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


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


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    nCrArr = combination_list(n,MOD)
    for k in range(K + 1):
        # print(nCr)
        # nCr = cmb(N - 1, k)%MOD
        _sum += M * e[N - k - 1] * nCrArr[k] % MOD
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        # nCr = nCr * (n - k) // (k + 1) * modinv(k ) % MOD
        # nCr= nCr%MOD
    print(_sum % MOD)
    return


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:

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))%MOD + (M*pow(M-1, N-2, 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: Accepted

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()

if M == 1:
    if K == N-1:
        print(1)
    else:
        print(0)
else:
    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)