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

Solution (Python):
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


g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 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


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

Solution (Python):
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)

Solution (Python):
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")) 
  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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

import sys

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

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):

import sys

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

Solution (Python):
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)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys

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

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

mod = 998244353

ans = 0

facts = [1 for i in range(N+1)]
invs = [1 for i in range(N+1)]

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

for i in range(1, N+1):
    facts[i] = facts[i-1] * i % mod
    invs[i] = inv(facts[i])

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

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

print(ans)

Solution (Python):
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
n,m,k = mp()
mod = 998244353
conb = [1]
pows = [pow(m-1, n-1-k, mod)]
for i in range(1,k+1):
    conb.append(conb[i-1]*(n-i)*pow(i,mod-2,mod) % mod)
    pows.append(pows[i-1]*(m-1) % mod)
pows.reverse()

ans = 0
for i in range(k+1):
    ans += m * conb[i] * pows[i]
    ans %= mod
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    fac = [0] * (N + 10)
    finv = [0] * (N + 10)
    inv = [0] * (N + 10)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N + 2):
        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

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

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

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

def modinv(a, mod=998244353):
    return pow(a, mod-2, mod)

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

def combi(n,r,mod=998244353):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

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

print(ans%mod)

Solution (Python):

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

def cmb(n, k, mod, fac, ifac):    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

def make_tables(mod, n):
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 
 
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

f = [0 for _ in range(N)]
for i in range(N):
    if i == 0:
        f[i] = M
    else:
        f[i] = (f[i-1] * (M-1)) % mod
if K == 0:
    print(f[N-1])
else:
    fac, ifac = make_tables(mod, N)
    ans = 0
    c = 1
    for i in range(K+1):
        ans += f[N-1-i] * c
        ans %= mod
        c = cmb(N-1, i+1, mod, fac, ifac)
    print(ans % mod)

Solution (Python):
import sys
N,M,K= list(map(int, input().split()))
mod = 998244353

if N == 1:
    print(M)
    sys.exit()


def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    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
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0

    return fac[n] * (finv[r] * finv[n - r] % mod) %mod




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


print(ans%mod)

Solution (Python):
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n] * finv[r] * finv[n-r] % p

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

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1
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

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

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

N, M, K = MAP()

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

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

N, M, K = MAP()

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

Solution (Python):
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=comb(n-1,i)*po%mod
    po*=iii
    po%=mod
print(ans%mod)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

fac = [1, 1]     
f_inv = [1, 1]   
inv = [0, 1]     

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    N,M,K = map(int, readline().split())

    MOD = 998244353
    prepare(N + 10, MOD)

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

    m = M
    for _ in range(N-1):
        m *= M - 1
        m %= MOD

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

        m *= pow(M-1, MOD-2, MOD)
        m %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def pre_cmb(N, MOD):
    FACT = [1, 1]  
    INV = [0, 1]  
    FACTINV = [1, 1]  

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i,MOD-2,MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


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

prelist = pre_cmb(n, mod)

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

print(cnt % mod)

Solution (Python):


import sys






















def main():
    mod = 998244353
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, k = mi()

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

    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n - r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m
    
    ans = 0
    for j in range(k + 1):
        ans = (ans + (m * pow(m - 1, n - j - 1, mod) * comb(n - 1, j, mod)) % mod) % mod
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

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

def com(n,r,m):
    
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod

p = pow(m-1,n-k-2,mod)

c = com(n-1,k+1,mod)

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

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


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


def nCk(n,k):
    if k<0 or n<k:return 0
    return fact[n]*invfact[k]*invfact[n-k]%mod

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

print(ans%mod)

Solution (Python):
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    from itertools import accumulate
    MOD = 998244353

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

    cc = Calc(max_value=N, mod=MOD)
    *m_1, = accumulate([1] + [M - 1] * (N - 1), func=lambda a, b: a * b % MOD)

    ans = 0
    for bond in range(K + 1):
        t = cc.nCr(N - 1, bond)  
        t = t * m_1[N - 1 - bond] % MOD  
        ans = (ans + t) % MOD
    ans = ans * M % MOD
    print(ans)


if __name__ == '__main__':
    main()

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

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

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

ans = 0
col = M
for x in range(N - 1, -1, -1):
    now = col
    now *= cmb(N - 1, x, p)
    now %= p
    if x <= K:
        ans += now
        ans %= p
    col *= (M - 1)
    col %= p
print(ans)