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


class Bigint:

    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n % self.mod

    @classmethod
    def set_mod(cls, mod):
        cls.mod = mod

    @staticmethod
    def _to_int(n):
        t = type(n)
        if t == int:
            return n
        elif t == Bigint:
            return n.n
        else:
            raise

    @staticmethod
    def _to_bigint(n):
        t = type(n)
        if t == int:
            return Bigint(n)
        elif t == Bigint:
            return n
        else:
            raise

    def __str__(self):
        return f"{self.n}"

    def __add__(self, other):
        return Bigint(self.n + self._to_int(other))

    def __iadd__(self, other):
        self.n = (self.n + self._to_int(other)) % self.mod
        return self

    def __sub__(self, other):
        return Bigint(self.n - self._to_int(other))

    def __isub__(self, other):
        self.n = (self.n - self._to_int(other)) % self.mod
        return self

    def __mul__(self, other):
        return Bigint(self.n * self._to_int(other))

    def __imul__(self, other):
        self.n = (self.n * self._to_int((other))) % self.mod
        return self

    def __pow__(self, other):
        assert type(other) == int, "power should be integer"
        #
        if other < 0:
            return self ** (other % (self.mod-1))
        ret = Bigint(1)
        now = Bigint(self.n)
        while other > 0:
            if other & 1:
                ret *= now
            other >>= 1
            now *= now
        return ret

    def __truediv__(self, other):
        return self * (self._to_bigint(other) ** (self.mod-2))

    def __itruediv__(self, other):
        self *= (self._to_bigint(other) ** (self.mod-2))
        return self


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n, m, k = _ia()
    Bigint.set_mod(998244353)
    power = [Bigint(1)]
    for i in range(n-1):
        power.append(power[i] * (m-1))

    fact = Bigint(1)
    inv = [Bigint(1)] * n
    for i in range(1, n):
        fact *= i
        inv[i] = inv[i-1] * Bigint(i) ** (-1)

    ans = Bigint(0)
    for i in range(k+1):
        c = fact * inv[n-1-i] * inv[i]
        ans += (c * m * power[n-1-i])

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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


# D = list(map(int,input().split()))
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
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):
    #print(ans)
    ans += M * pow(M - 1, N - i - 1, MOD) * nCk(N - 1, i) % MOD
print(int(ans % MOD))

Submission status: Accepted

Solution code:

from collections import defaultdict

MOD = 998244353

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


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

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
color = M
for x in reversed(range(N)):
    now = color
    now *= combination(N-1, x)
    now %= MOD
    if x <= K:
        ans += now
        ans %= MOD
    color *= M - 1
    color %= MOD

print(ans)

Submission status: Accepted

Solution code:
def e_colorful_blocks(MOD=998244353):
    N, M, K = [int(i) for i in input().split()]

    class Combination(object):
        """素数 mod に対する二項係数の計算"""
        __slots__ = ['mod', 'fact', 'factinv']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], -1, mod))
            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.fact, self.factinv = mod, fac, inv[::-1]

        def combination(self, n, r):
            return (0 if n < 0 or r < 0 or n < r
                    else self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.mod)

    ans = 0
    comb = Combination(max(N, M), MOD).combination
    for x in range(K + 1):
        a = (M * pow(M - 1, N - 1 - x, MOD)) % MOD
        b = comb(N - 1, x)
        ans = (ans + a * b) % MOD
    return ans

print(e_colorful_blocks())

Submission status: Accepted

Solution code:
P = 998244353


nn = 200200

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P


def comb(a, b):
    return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


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

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


t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
ans = 0
for k in range(K+1):
    ans = (ans + t * comb(N-1, k)) % P
    t = t * m % P
print(ans * M % P)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M,K=map(int,input().split())
mod=998244353
fac=[1,1]
for i in range(2,N*2):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    if a<b:
        return(0)
    return(fac[a]*ifac[b]*ifac[a-b]%mod)


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

Submission status: Accepted

Solution code:
#E
n,m,k = list(map(int,input().split()))
fac = [1]*n
finv = [1]*n
inv = [1]*n
MOD = 998244353
for i in range(2,n):
    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 comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += comb(n-1,i)*m*pow(m-1,n-i-1,MOD)%MOD
    ans %= 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 = 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)

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

Submission status: Accepted

Solution code:
n,m,k = map(int, input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 998244353
N = 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):
  a = m*pow(m-1,n-i-1,p)
  a *= cmb(n-1, i, p)%p
  ans += a
print(ans%p)

Submission status: Accepted

Solution code:
n,m,k = map(int, input().split())
#ncr
mod = 998244353
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod 
    def ncr(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod 
cmb = Combination(n)
ans = 0
for i in range(k+1):
  a = m*pow(m-1,n-i-1,mod)%mod
  a *= cmb.ncr(n-1,i)
  ans += a%mod
print(ans%mod)

Submission status: Accepted

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

facs = [1] * N
invs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

s = 0
for i in range(K+1):
    d = facs[N-1] * invs[i] * invs[N-1-i] \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

Submission status: Accepted

Solution code:
MOD = 998244353
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
n,m,k = map(int,input().split())
c = 0
for i in range(k+1):
    c += comb_mod(n-1, i)*m*pow(m-1,n-i-1,MOD)
    c %= MOD
print(c)

Submission status: Accepted

Solution code:
import itertools

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


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


p = 998244353
N = 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

l2 = m*(m-1)**(n-k-1)
for _k in range(k, -1, -1):
    # print(_k)

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p

    l2 %= p
    l2 *= (m - 1)
    l2 %= p


print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, n):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
p = 998244353
fct, inv = [1], [1]
for i in range(1, max(n, m) + 1):
    fct.append((fct[-1] * i) % p)
    inv.append((inv[-1] * pow(i, p - 2, p)) % p)
ans = 0
for i in range(k + 1):
    cmb = fct[n - 1] * inv[i] * inv[n - 1 - i]
    ans = (ans + cmb * m * pow(m - 1, n - 1 - i, p)) % p
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

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

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

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

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

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
mod =998244353
 
def cmb1(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 )
 
def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res
 
ans = 0
for x in range(k+1):
    temp = cmb1(n-1, x, mod)
    temp *= m*power(m-1, n-1-x, mod)
    ans += temp
print(ans%mod)

Submission status: Accepted

Solution code:
import itertools

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


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


p = 998244353
N = 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

l2 = m*(m-1)**(n-k-1)
for _k in range(k, -1, -1):
    # print(_k)

    ncr = cmb(n - 1, _k, p)
    ans += ncr * l2
    ans %= p
    l2 %= p
    l2 *= (m - 1)


print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
def nCr(n,r,fac,finv):
    mod = 998244353
    ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    return ans
ans = 0
mod = 998244353
fac = [1,1]+[0]*n
finv = [1,1]+[0]*n
inv = [1,1]+[0]*n
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod%i] * (mod//i) % mod
    finv[i] = finv[i-1] * inv[i] % mod
for i in range(k+1):
    ans += m*pow(m-1,n-1-i,mod)*nCr(n-1,i,fac,finv) % mod
    ans %= mod
    # print(m*pow(m-1,n-1-i,mod)*nCr(n-1,i,fac,finv) % mod)
print(ans)

Submission status: Accepted

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

MOD = 998244353


def inv(x, m):
  y, u, v = m, 1, 0

  while y != 0:
    t = x // y
    x -= t * y
    u -= t * v
    x, y = y, x
    u, v = v, u

  return u % m


def main():
  N, M, K = map(int, input().split())
  color = M
  division = 1
  count = 0

  if K == N - 1:
    count += color * division

  for i in range(N - 2, -1, -1):
    color = (color * (M - 1)) % MOD
    division = division * (i + 1) * inv(N - 1 - i, MOD) % MOD

    if i <= K:
      count = (count + color * division) % MOD

  print(count)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 998244353
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


# 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


def main():
    N, M, K = MI()

    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):
        group_color = M * pow(M - 1, N - k - 1, MOD)
        group_number = cmb(N-1, k, MOD)
        ans += (group_color * group_number) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

def mypow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return mypow(x * x % MOD, n // 2) % MOD
    else:
        return x * mypow(x * x % MOD, n // 2) % MOD

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

inv = [1] * (N+1)
inv[N] = mypow(fact[N], MOD-2)
for i in range(N, 1, -1):
    inv[i-1] = inv[i] * (i) % MOD


def cmb(n,r):
    return fact[n] * inv[r] * inv[n-r] % MOD

ans = M * mypow(M-1, N-1) % MOD
for k in range(1, K+1):
    ans += M * mypow(M-1, N-1-k) * cmb(N-1, k)
    ans %= MOD

print(ans)

Submission status: Accepted

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

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

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

ans = 0
for x in range(k+1):
    temp = cmb1(n-1, x, mod)
    temp *= m*power(m-1, n-1-x, mod)
    ans += temp
print(ans%mod)

Submission status: Accepted

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

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

count = 0
m_pow = [1]
for i in range(n):
    m_pow.append(m_pow[-1] * (m - 1) % mod)
for i in range(k + 1):
    temp = m
    temp *= m_pow[n - i - 1]
    temp *= combination(n - 1, i, mod)
    temp %= mod
    count += temp
count %= mod
print(count)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from numba import jit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

@jit
def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs

facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod
    now *= facts[n-1]*invs[n-1-i]*invs[i]%mod
    if i <= k:
        point += now%mod

print(point%mod)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
mod = 998244353
wariate = 1
point = 0

def prepare(n, MOD=mod):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs
facts, invs = prepare(n, mod)
for i in range(n-1,-1,-1):
    now = m
    if i != n-1:
        wariate *= m-1
        wariate %= mod
    now *= wariate%mod

    now *= facts[n-1]*invs[n-1-i]*invs[i]
    if i <= k:
        point += now%mod

print(point%mod)

Submission status: Accepted

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

mod = 998244353

ans = 0

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(N+1)]
        self.invs = [1 for i in range(N+1)]
        
        for i in range(1, N+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r): 
        return self.ncr(n+r-1, n-1)

comb = Combination(N)

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

print(ans)

Submission status: Accepted

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

fact = [1 for i in range(N+1)]
fact_inv = [1 for i in range(N+1)]

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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

def prepare(n, MOD):
    """
    nCr mod MOD
    :param n:
    :param MOD:
    :return:
    """
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs

facts, invs = prepare(N, MOD)
ans = 0
col = M*(M-1)**(N-K-1)%MOD
for i in range(K+1)[::-1]:
    combi = facts[N-1]*invs[N-1-i]*invs[i]
    ans += col*combi
    ans %= MOD
    col *= (M - 1)
    col %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, 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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD



@mt
def slv(N, M, K):
    m = Mod(998244353)
    C = Combination(N, 998244353)

    ans = 0
    for i in range(K+1):
        n = N - i
        tmp = m.mul(M, m.pow(M-1, n-1))
        tmp = m.mul(tmp, C(N-1, i))
        ans = m.add(ans, tmp)

    return ans


def main():
    N, M, K = read_int_n()
    print(slv(N, M, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 998244353

ans = 0

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(N+1)]
        self.invs = [1 for i in range(N+1)]
        
        for i in range(1, N+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

comb = Combination(N)

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod):
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % mod
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv


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


def main():
    input = stdin.buffer.readline
    n, m, k = map(int, input().split())
    mod = 998244353

    fac, finv = initialize_cmb(n + 10, mod)

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

    ans = c[n - 1]

    for i in range(k):
        ans += c[n - i - 2] * cmb(n - 1, i + 1, mod, fac, finv)
        ans %= mod

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

di = 998244353
summ = m

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K*x)%di
        x = (x*x)%di
        n //= 2

    return (K * x)%di

for i in range(n-1):
    summ = (summ*(m-1))%di

a=[]

for i in range(max(m,k+2)):
    a.append(pow_k(i,di-2))


lis = [0 for i in range(k+1)]
lis[0] = summ
for i in range(k):
    gm = a[m-1]
    gi = a[i+1]
    lis[i+1] = (lis[i]*(n-1-i)*gm*gi)%di

if k==n-1 and m==1:
    print(1)
else:
    print(sum(lis)%di)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, 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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD



@mt
def slv(N, M, K):
    m = Mod(998244353)
    C = Combination(N, 998244353)

    ans = 0
    col = M
    for x in range(N-1, -1, -1):
        tmp = col
        tmp = m.mul(tmp, C(N-1, x))
        if x <= K:
            ans = m.add(ans, tmp)
        col = m.mul(col, M-1)
    return ans


def main():
    N, M, K = read_int_n()
    print(slv(N, M, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

factorials = [0] * (N + 1)
factorials[0] = 1
for i in range(1, N + 1):
    factorials[i] = factorials[i - 1] * i % MOD
invs = [None] * (N + 1)
invs[1] = 1
for i in range(2, N + 1):
    invs[i] = (invs[i - 1] * pow(i, MOD - 2, MOD)) % MOD


def nCr(n, r):
    if n <= 0 or n <= r or r <= 0:
        return 1
    if n - r < r:
        return nCr(n, n - r)
    return factorials[n] * invs[n - r] * invs[r] % MOD


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