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:
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    N, M, X = LI()
    C = [LI()for _ in range(N)]
    loop = 2**N
    ans = inf
    for l in range(loop):
        cur = 0
        A = [0]*M
        for j in range(N):
            if (1<<j)&l>0:
                cur += C[j][0]
                for k in range(M):
                    A[k] += C[j][k+1]
        flag = True
        for i in range(M):
            if A[i]<X:
                flag = False
                break
        if flag:
            ans = min(ans,cur)
    if ans==inf:
        print(-1)
        return
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    locat_doubling = [[0]*N for _ in range(100)]
    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][i] = A[i]-1
    for k in range(2,100):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
    #print(locat_doubling)
    ans = [i for i in range(N)]
    for k in range(100):
        for i in range(N):
            if K&(1<<k)>0:
                ans[i] = locat_doubling[k+1][ans[i]]
    print(ans[0]+1)
    return

def examE():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N, M, K = LI()
    C = combination(N,mod2)
    ans = 0
    for i in range(N):
        if i>K:
            break
        cur = C.comb(N-1,i) * M * pow((M - 1), N - i - 1, mod2) % mod2
        #print(cur)
        ans += cur
        ans %= mod2
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
mod = 998244353
fact = [1]*(2*10**5+1)
for n in range(2*10**5):
    fact[n+1] = (n+1)*fact[n]
    fact[n+1] %= mod

factinv = [1]*(2*10**5+1)
for n in range(2*10**5):
    factinv[n+1] = pow(fact[n+1],mod-2,mod)

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

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

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

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

Submission status: Accepted

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

fac = [0]*(n+1)
per = [0]*(n+1)

fac[0]=1
per[0] = 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):
    if i == 0:
        ans += m*pow(m-1,n-1-i,mod)%mod
    else:
        ans += m*pow(m-1,n-1-i,mod)%mod * nCk(n-1,i)%mod
    ans %= mod
print(ans)

Submission status: Accepted

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

if M==1:
    print(1 if K==N-1 else 0)
    exit()

mod = 998244353

f = [0]*N
f[0] = p = 1
for i in range(1,N):
    f[i] = p = p*i%mod

finv = [0]*N
finv[N-1] = p = pow(f[N-1],mod-2,mod)
for i in range(N-2, -1, -1):
    finv[i] = p = p*(i+1)%mod

ans = 0
for k in range(K+1):
    x = M * pow(M-1, N-k-1, mod) % mod
    y = (f[N-1]*finv[N-1-k]%mod)*finv[k]%mod
    ans = (ans + x*y%mod)%mod

print(ans)

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

print(ans)

Submission status: Accepted

Solution code:
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 998244353

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

    # max_nCrまで調べられる
    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod
    
    # nCrを求める
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

MAX = 2 * 10**5 + 5
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


mm = [1]
for j in range(n):
    mm.append((mm[-1] * (m - 1)) % MOD)
# print(mm)
dp = [(comb(n - 1, j) * m * mm[n - 1 - j]) % MOD for j in range(k + 1)]
# print(dp)

ans = sum(dp) % MOD
print(ans)

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
MOD = 998244353
if M==1:
    print(1 if K==N-1 else 0)
    exit()

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    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,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

cs = []
ms = [(M * pow(M-1, N-1-K, MOD)) % MOD]
for i in range(K+1):
    cs.append(comb(N-1, i))
    if i:
        ms.append((ms[-1] * (M-1)) % MOD)

ans = 0
for c,m in zip(cs, ms[::-1]):
    ans += c*m
print(ans%MOD)

Submission status: Accepted

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

        else:
            print(0)
            return
    ans = 0
    tmp = m
    for i in range(n - 1):
        tmp *= m - 1
        tmp %= mod
    for i in range(k + 1):
        ans += tmp * combination_mod(n - 1, i, mod)
        tmp *= pow(m - 1, mod - 2, mod)
        tmp %= mod
        ans %= mod
    print(ans)
    return


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

Submission status: Accepted

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

UPPERLIMIT=2*10**5+1
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

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

Submission status: Accepted

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

mod = 998244353

fac = [1]
inv = [1]
for i in range(1, N + 10) :
  fac.append(fac[-1] * i % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

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

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


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

ans = 0
for s in range(k + 1):
    p = n - s
    ans = (ans + m * pow(m - 1, p - 1, MOD) * facts[n - 1] * invs[s] * invs[n - s - 1]) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 998244353
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N + M, mod)

dp = [0] * (N + 1)
dp[1] = M
for i in range(1, N):
  dp[i + 1] = dp[i] * (M - 1)
  dp[i + 1] %= mod
#print(dp)
res = 0
for i in range(K + 1):
  res += dp[N - i] * f.combi(N - 1, i) % mod
  res %= mod
print(res)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
if m == 1:
  if k == n-1:
    print(1)
  else:
    print(0)
  exit()
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(2))
now = int(m)
for _ in range(n-1):
  now *= m-1
  now %= mod
ans = int(now)
for i in range(k):
  now *= inv(m-1)
  now *= n-1-i
  now *= inv(i+1)
  now %= mod
  #print(now)
  ans += now
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int, input().split())
mod = 998244353
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)

def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

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

ans *= m
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
# MOD = 10 ** 9 + 7
MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, M, K = list(map(int, sys.stdin.buffer.readline().split()))

# dp[i][k]: i までみて、k 回同じ色になった
# dp = [[0] * (K + 2) for _ in range(N)]
# dp[0][0] = 1
# for i in range(N - 1):
#     for k in reversed(range(K + 1)):
#         # 同じ色
#         dp[i + 1][k + 1] += dp[i][k]
#         # 違う色
#         dp[i + 1][k] += dp[i][k] * (M - 1)
# print(np.array(dp))
# li = dp[-1][:K + 1]
# ans = sum(li) * M % MOD
# print(ans)
# print()

comb = Combination(max=max(N, M, K) + 100, mod=MOD)
ans = 0
for k in range(K + 1):
    ans += pow(M - 1, N - 1 - k, MOD) * comb.ncr(N - 1, k)
    ans %= MOD
print(ans * M % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 998244353

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

ans = [0] * (K + 1)
ans[0] = M

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

C = Factorial(N + 1, MOD).comb

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

ans *= M
ans %= MOD

print (ans)

Submission status: Accepted

Solution code:
def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = inv[mod % i] * ((mod - mod // i) % mod)
    for i in range(K + 1):
        if i > 0:
            m = (m * (N - i) * inv[i]) % mod
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())

Submission status: Accepted

Solution code:
SIZE=200001; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

n,m,k = list(map(int,read().split()))

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

print(ans%MOD)

Submission status: Accepted

Solution code:
#!python3

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

# input
N, M, K = LI()

MOD = 998244353
MAX = 10 ** 6
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    comb_init()
    pm = [None] * N
    pm[0] = 1
    for i in range(1, N):
        pm[i] = pm[i - 1] * (M - 1) % MOD
    
    ans = 0
    for k in range(K + 1):
        x = comb(N - 1, k) * M * pm[N - k - 1] % MOD
        ans = (ans + x) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque

N, M, K = [int(x) for x in input().split()]
MOD = 998244353


def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


# Precompute all factorials
fact = [1]
for i in range(1, 2 * (10 ** 5) + 1):
    fact.append((fact[-1] * i) % MOD)


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


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

Submission status: Accepted

Solution code:
MOD = 998244353

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

fac = [1]*(n+1)
fac_inv =  [0]*(n+1)

for i in range(n):
    fac[i+1] = (fac[i] * (i+1)) %MOD
fac_inv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(n,0,-1):
    fac_inv[i-1] = (fac_inv[i] * i) % MOD
    
def comb(n,k):
    if k<0 or k>n:
        return 0
    x = (fac[n] * (fac_inv[k] * fac_inv[n-k])%MOD)%MOD
    return x

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

print(ans)

Submission status: Accepted

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

m = 2*(10**5) +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

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

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

Submission status: Accepted

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



n, m, k = map(int, input().split())
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:
lim, mod = 3*10**5, 998244353
n, m, k = map(int, input().split())
ifac, fac = [1], [1]
for i in range(1, lim):
    fac.append((fac[-1]*i)%mod)
    ifac.append(1)
ifac[-1] = pow(fac[-1], mod-2, mod)
for i in range(1, lim-1):
    ifac[lim-1-i] = (ifac[lim-i] * (lim-i))%mod
pw = [1]
for i in range(1, lim):
    pw.append((pw[-1]*(m-1))%mod)
def C(n, k):
    r = fac[n] * ifac[k]
    r %= mod
    r *= ifac[n-k]
    return r%mod

ans = 0
for i in range(k+1):
    #i adjacent pairs are equal
    N = n - i
    add = C(n-1, i) * m
    add %= mod
    add *= pw[N-1]
    add %= mod
    ans += add
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


#a=[int(x) for x in input().split()]
#n=int(input())

def main():
    mod=998244353

    def po(a,n):
        ans=1
        while n:
            if n&1:
                ans=(ans*a)%mod
            a=(a*a)%mod
            n//=2
        return ans


    n,m,k=[int(x) for x in input().split()]
    
    f=[1]
    for i in range(1,n+5):
        f.append(f[-1]*i%mod)

    def fac(n):
        if n<0:
            return 0
        return f[n]
    
    def nCr(n,r):
        if n<0 or r>n or r<0:
            return 0
        return fac(n)*po(fac(r)*fac(n-r),mod-2)%mod

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

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
mod = 998244353
input = sys.stdin.readline
N, M, K = map(int, input().split())
fact = [1] * (N + 1)
for i in range(1, N + 1): fact[i] = (fact[i-1] * i) % mod
revfact = [1] * (N + 1)
revfact[N] = pow(fact[N], mod - 2, mod)
for i in reversed(range(1, N)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

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


    return  0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    mod = 998244353
    comb = Combination(N + 10, mod)

    ans = 0
    for i in range(K + 1):
        p = comb(N - 1, i) * M * pow(M - 1, N - i - 1, mod) % mod
        ans = (ans + p) % mod
    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 #出力の制限
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
ans = 1
for i in range(K+1):
  m = M
  m *= cmb(N-1,i,mod)
  m *= pow(M-1,N-1-i,mod)
  ans += m
  ans %= mod
print(ans-1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



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

N = 2*10**5 # 必要なテーブルサイズ

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

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M
    
def sub(x):
    return m * pow(m-1, x-1, M)

s = 0
for i in range(k+1):
    if k>0:
        tmp = cmb(n-1, i, M) * sub(n-i)
    else:
        tmp = sub(n)
    s += tmp
    s %= M
#     print(i, tmp)
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M,K = inputIL()

res = 0
for k in range(K+1):
  a = (M*pow(M-1,N-1-k,MOD)) %MOD
  b = nCr(N-1,k)
  res = ( res + a*b )%MOD
  
print(res)