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):
MOD = 998244353
n, m, k = map(int, input().split())

def init_mod_c(lim=10**6, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i-1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

ans = 0
c = init_mod_c(n, MOD)

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

print(ans)

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

MOD=998244353

ans=0
temp2=1


def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(max(N+3,M-1), MOD)

Vec=[0]*N





'''
for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    cmb=cmb*(N-i-1)*i*invs[i]%MOD
    
'''
for i in range(N):
  if i == 0:
    temp1=M
    Vec[N-i-1]=temp1
  else:
    temp1*=(M-1)*(N-i)
    temp1*=invs[i]
    temp1%=MOD
    Vec[N-i-1]=temp1


ans=sum(Vec[:K+1])

print(ans%MOD)

Solution (Python):

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

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
if M != 1:
  mi = modinv(M-1,m)
  A = M * pow(M-1,N-1,m)
  for k in range(K+1):
    if k>0:
      B = (B*(N-k)*modinv(k,m))%m
    res = (res+ A*B)%m
    A = (A*mi)%m
  print (res)
else:
  if K == N-1:
    
    print(1)
  else:
    print(0)

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



mod = 998244353

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

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m


ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k: ans += colors * nCr(n-1, p, mod) % mod
    colors = colors * (m - 1) % mod
ans %= mod
print(ans)

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



mod = 998244353

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

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m


ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k:
        ans += colors * nCr(n-1, p, mod) % mod
    colors *= m - 1
    colors %= mod
ans %= mod
print(ans)

Solution (Python):
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init_cmb(N,p):
    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)

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

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

    mod=998244353
    ans=0

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

    print(ans%mod)

if __name__ == '__main__':
    main()

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



mod = 998244353

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

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m


ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k:
        groups = nCr(n-1, p, mod)
        ans += groups * colors % mod
        ans %= mod
    colors *= m - 1
    colors %= mod
ans += mod
ans %= mod
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17

mod=998244353
x=220000
fact=[0 for i in range(x)]
invfact=[0 for i in range(x)]
fact[0]=1

def cmod(n,k,mod):
    if n<0 or n<k:
        return 0
    return (fact[n]*invfact[n-k]*invfact[k])%mod
for i in range(1,x):
    fact[i]=(fact[i-1]*i)%mod

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

for j in range(x-1,0,-1):
    
    invfact[j-1]=(invfact[j]*(j))%mod


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

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

Solution (Python):
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)

Solution (Python):
from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)

Solution (Python):
from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)

Solution (Python):
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 = 10 ** 6  
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

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

Solution (Python):
def inverse_mod(a, mod=10**9+7):
    """ Calculate inverse of the integer a modulo mod.
    """
    return pow(a, mod-2, mod)


def combination_mod(n, r, mod=10**9+7):
    """ Calculate nCr modulo mod.
    """

    r = min(r, n-r)
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod

    return numerator * inverse_mod(denominator, mod) % mod


def create_inverses_table(n, mod=10**9+7):
    """ Create table for inverses of the integers 0 to n modulo mod.
    """

    inv_table = [0] + [1] * n
    for x in range(2, n+1):
        inv_table[x] = -(mod//x) * inv_table[mod % x] % mod

    return inv_table


def solve():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())

    if n_colors == 1:
        return int(n_blocks - n_max_pairs == 1)

    mod = 998244353

    inverses = create_inverses_table(max(n_colors, n_max_pairs), mod)

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod) % mod
    e2 = 1
    total = e1 * e2

    for k in range(1, n_max_pairs+1):
        e1 = e1 * inverses[n_colors - 1] % mod
        e2 = e2 * (n_blocks - k) * inverses[k] % mod
        total += e1 * e2
        total %= mod

    return total


def main():
    print(solve())


if __name__ == "__main__":
    main()

Solution (Python):
mod= 998244353

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

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

Solution (Python):
from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	
	def binom(n, k, q):
		return (F[n]*((I[k]*I[n-k])%q))%q

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

if __name__ == "__main__":
	main()

Solution (Python):
from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def binom(n, k, q, F, I):
	return (F[n]*((I[k]*I[n-k])%q))%q

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	ans = 0
	for i in range(n-k, n+1):
		ans += (binom(n-1, i-1, MOD, F, I)*m*pow(m-1, i-1, MOD))%MOD
	print(ans % MOD)

if __name__ == "__main__":
	main()

Solution (Python):
def main():
    mod = 998244353
    fact = [1, 1]
    for i in range(2, 400001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

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

    print(ans)


main()

Solution (Python):
import sys
import math

mod = 998244353

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

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


def nCr(n, r, mod=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    if n == 0 or r == 0:
        return 1

    """
    a = math.factorial(n) % mod
    b = math.factorial(r) % mod
    c = math.factorial(n - r) % mod
    """
    a = fact[n]
    b = fact[r]
    c = fact[n-r]

    inv = modinv(b*c, mod)
    ans = a * inv

    return ans % mod


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

print(ans)

Solution (Python):
def main():
    mod = 998244353
    fact = [1, 1]
    for i in range(2, 400001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

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

    print(ans)


main()

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

mod=998244353

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

def nCk(n,k):
    return fact[n]*pow(fact[n-k]*fact[k],mod-2,mod)

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

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

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

print(ans)

Solution (Python):
MOD = 998244353
n, m, k = map(int, input().split())
c = 1
cnt = 0
for x in range(k + 1):
    cnt += c * m * pow(m - 1, n - 1 - x, MOD) 
    cnt %= MOD
    c *= (n - x - 1) * pow(x + 1, MOD - 2, MOD)
    c %= MOD
print(cnt)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,K=LI()
FACT=FLIST(N+M+1)
FINV=[]
for i in FACT: FINV.append(INV(i))
if N == 1:
    print(M)
    exit()
if M == 1:
    if N - 1 == K: print(M)
    else: print(0)
    exit()

res = 0
def ncr(n, r):
    res = 1
    res *= FACT[n]
    res *= FINV[n-r]
    res %= DVSR
    res *= FINV[r]
    res %= DVSR
    return res

for k in range(K+1):
    v = ncr(N-1, k)*M
    v %= DVSR
    v *= POW(M-1, N-1-k)
    v %= DVSR
    res += v

print(res%DVSR)

Solution (Python):
def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        if K == N - 1:
            return 1
        else:
            return 0
    if N == 1:
        return M
    mod = 998244353
    fact = [1]
    for i in range(1, N):
        fact.append(fact[-1] * i % mod)
    count = 0
    for k in range(K + 1):
        current = pow(M - 1, N - k - 1, mod) * M % mod
        rev = pow(fact[k] * fact[N - 1 - k] % mod, mod - 2, mod)
        current = (current * fact[N - 1] % mod) * rev % mod
        count = (count + current) % mod
    return count


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

Solution (Python):
n,m,k=map(int,input().split())
MOD=998244353
dp=[0] *(k+1)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def binom_preprocess(n, MOD=998244353):
    f = [0 for i in range(n+1)]  
    invf = [0 for i in range(n+1)]  
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=998244353):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K



def solve(N, M, K, MOD=998244353):
    ans = 0
    f, invf = binom_preprocess(N)
    for k in range(K+1):
        ans += binom(N-1, N-k-1, f, invf) * M * pow(M-1, N-k-1, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
import math

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

if N == 1:
    print(M)
    exit(0)

mod = 998244353

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

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

ans = pow(M, N, mod)
for L in range(K + 1, N):
    result = (M * pow(M - 1, N - L - 1, mod) * com(N - 1, N - L - 1)) % mod
    ans -= result

print(ans % mod)

Solution (Python):
from collections import defaultdict
N,M,K=map(int,input().split())
MOD=998244353
 
def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

print(ans%MOD)

Solution (Python):
import numpy as np


class mod_calc():
    def __init__(self, divisor, max_n):
        
        self._divisor = divisor
        
        
        fact = np.empty((max_n+1,), dtype=int)
        fact[1] = fact[0] = f = 1
        for i in range(2, len(fact)):
            f = (f * i) % divisor
            fact[i] = f
        self._fact = fact
        fact_inv = np.empty((max_n+1,), dtype=int)
        fact_inv[max_n] = fi = pow(int(fact[max_n]), divisor-2, divisor)
        for i in range(max_n, 2, -1):
            fi = (fi * i) % divisor
            fact_inv[i-1] = fi
        fact_inv[1] = fact_inv[0] = 1
        self._fact_inv = fact_inv

    def comb(self, n, k):
        k = min(k, n-k)
        if k == 0 or k == n:
            return 1
        return self.mul(self._fact[n], self._fact_inv[n-k], self._fact_inv[k])

    def pow(self, a, n):
        return pow(a, n, self._divisor)

    def mul(self, *a):
        
        
        r = a[0]
        for m in a[1:]:
            r = (r * m) % self._divisor
        return r

    def sum(self, *a):
        r = a[0]
        for m in a[1:]:
            r = (r + m) % self._divisor
        return r


def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        if K == N - 1:
            return 1
        else:
            return 0
    if N == 1:
        return M
    c = mod_calc(998244353, N-1)
    count = 0
    for k in range(K+1):
        count = c.sum(c.mul(c.comb(N-1,k), M, c.pow(M-1, N-k-1)), count)
    return count


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

Solution (Python):
import math

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

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(N+3, MOD)

num = M
nums = []
for i in reversed(range(1,N)):
    nums.append(num)
    num *= i*(M-1)
    num *= invs[N-i]
    num %= MOD
nums.append(num)
nums.reverse()

ans = sum(nums[:K+1])
ans %= MOD
print(ans)

Solution (Python):




import sys
sys.setrecursionlimit(100000000)
DP={}
mod=998244353
product={}
N = 1000001
  

factorialNumInverse = [None] * (N + 1) 
  

naturalNumInverse = [None] * (N + 1) 
  


fact = [None] * (N + 1) 
  

def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] * 
                                   (p - int(p / i)) % p) 
  


def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1
  
    
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                                  factorialNumInverse[i - 1]) % p 
  

def factorial(p): 
    fact[0] = 1
  
    
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 
  

def Binomial(N, R, p): 
      
    
    ans = ((fact[N] * factorialNumInverse[R])% p * 
                      factorialNumInverse[N - R])% p 
    return ans 
def getproduct(M,n):
    
    global mod,product
    fact=1000
    if n-1 in product:
        product[n]=(M*product[n-1])%mod
        return (M*product[n-1])%mod
    if n<fact:
        return (M**n)%mod
    else:
        Q=int(n/fact)
        R=n%fact
        prev=1
        for q in range(Q):
            prev=(prev*((M**fact)%mod))%mod
        prev=prev*((M**R)%mod)
        product[n]=prev%mod
        return prev%mod
def ncr(n, r, p): 
    
    
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 
  
def G(N,M,K):
    global mod
    res=0
    for k in range(K,-1,-1):
        res=(res+((Binomial(N-1,k,mod))%mod *(M*getproduct(M-1,N-k-1))%mod)%mod)%mod
    return res%mod

def F(curr,N,M,K):
    global DP
    if(curr,K) in DP:
        return DP[(curr,K)]
    if curr==N:
        return 1
    if curr==0:
        return M*F(curr+1,N,M,K)
    else:
        a=0
        if K>0:
            a=F(curr+1,N,M,K-1)
        b=(M-1)*F(curr+1,N,M,K)
        DP[(curr,K)]=a+b
        return a+b
N,M,K=map(int,input().strip().split())
InverseofNumber(mod) 
InverseofFactorial(mod) 
factorial(mod) 

print(G(N,M,K))

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

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  fac[i] = (fac[i-1]*i) % mod
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n, 0, -1):
  inv[i-1] = (inv[i]*i) % mod
    
def nCr(n,r):  
  if r < 1:
    return 1
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod

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

Solution (Python):
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 1):
    next = C[-1] * (N-i) * pow(i, mod-2, mod)
    C.append(next % mod)
 
res = 0
 
for x in range(K+1):
    crt =  (pow(M-1, N-x-1, mod) * M) % mod 
    crt %= mod
    
    idx = min(x, N-1-x)
    crt *= C[idx]
    
    crt %= mod
    res += crt
    res %= mod
 
print(res)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

n,m,k = inpl()
conb = Combination(300010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * m * pow(m-1,x,mod)
    res %= mod
print(res)

Solution (Python):
mod=998244353
n,m,k=map(int,input().split())
fac=[1]
for i in range(n):
	fac.append(fac[-1]*(i+1)%mod)
ans=0
for x in range(k+1):
	rev=pow(fac[x]*fac[n-1-x]%mod,mod-2,mod)
	r=fac[n-1]*rev%mod*m*pow(m-1,n-x-1,mod)%mod
	ans+=r
	ans%=mod
print(ans)

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))

mod = 998244353

N, M, K = rl()

class CombMod:
	def __init__(self, N):
		self.fact = [1]
		self.rfact = [1]
		for i in range(1, N+1):
			self.fact.append(self.fact[i-1]*i % mod)
			self.rfact.append(pow(self.fact[i], mod-2, mod))

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

cm = CombMod(N-1)

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

Solution (Python):
n,m,k=map(int,input().split())
ans=0
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 )


  
kk=n-k

color=m*(m-1)**(kk-1)%mod

while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(cmb((n-1),(n-kk),mod))%mod
  kk+=1
  ans+=now
  ans=ans%mod
  
  
  
print(ans)

Solution (Python):

import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353




def combmod(n, k, p=MOD, cache=collections.defaultdict(lambda: [(1, 1)])):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    
    numden = cache[n]
    if k < len(numden):
        num, den = numden[k]
    else:
        
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % p
            den = den * (i + 1) % p
            numden.append((num, den))
    
    
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


def solve():
    ans = 0
    for i in range(K + 1):
        ans += combmod(N - 1, i) * M * pow(M - 1, N - 1 - i, MOD) % MOD
        ans %= MOD
    return ans


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

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

    fac, finv, inv = COMinit(N+1,MOD)

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




def COMinit(N, mod):
    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

    for i in range(2, N):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    
    return fac, finv, inv



def COM(n, r, mod, fac, finv, inv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
if __name__ == '__main__':
    solve()

Solution (Python):
n, m, k = map( int, input().split() )
p = 998244353

fact = [ 1, 1 ]       
inv = [ 0, 1 ]        
fact_inv = [ 1, 1 ]   
powm_1 = [ 1, m-1 ]
for a in range( 2, 2 * ( 10 ** 5 ) + 1 ):
    fact.append( a * fact[-1] % p )
    inv.append( - inv[p%a] * (p//a) % p )
    fact_inv.append( fact_inv[-1] * inv[a] % p )
    powm_1.append( powm_1[-1] * (m-1) % p )

ans = 0
for i in range( k + 1 ):
    ans = ( ans + m * powm_1[n-1-i] * fact[n-1] * fact_inv[n-1-i] * fact_inv[i] ) % p

print( ans )

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353




def combmod(n, k, p=MOD, numden=[(1, 1)]):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    
    if k < len(numden):
        num, den = numden[k]
    else:
        
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % p
            den = den * (i + 1) % p
            numden.append((num, den))
    
    
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


def solve():
    ans = 0
    for i in range(K + 1):
        ans += combmod(N - 1, i) * M * pow(M - 1, N - 1 - i, MOD) % MOD
        ans %= MOD
    return ans


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