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):
def modpow(a, n, mod):
    if n == 0:
        return 1
    else:
        if n % 2 == 0:
            return (modpow((a * a)%mod, n//2, mod)) % mod
        else:
            return ((a%mod) * modpow(a, n-1, mod)) % mod


def modinv(a, mod):
    return modpow(a, mod-2, mod) % mod

def moddiv(a, b, mod):
    return ((a%mod) * modinv(b, mod)) % mod

def modbase(n, k, mod):
    fact = [1 for _ in range(n+1)]
    inv = [1 for _ in range(n+1)]
    finv = [1 for _ in range(n+1)]

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


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

fact, inv, finv = modbase(N-1, K, mod)
dic = {}
dic[0] = 1
for k in range(1, K+1):
    dic[k] = fact[N-1] * (finv[k] * finv[N-k-1] % mod) % mod

sum = 0
for k in range(K+1):
    sum += M * (modpow(M-1 , N-1-k, mod) * dic[k] % mod) % mod
    sum %= mod
print(sum)

Solution (Python):
mod=998244353
n,m,k=map(int,input().split(' '))
F=[1 for i in range(n+1)]
for i in range(1,n+1):
    F[i]=F[i-1]*i%mod
I=[1 for i in range(n+1)]
for i in range(2,n+1):
    I[i]=(mod-int(mod/i))*I[mod%i]%mod
for i in range(2,n+1):
    I[i]=I[i]*I[i-1]%mod
def binom(n,k):
    return F[n]*I[k]%mod*I[n-k]%mod
pw=[1 for i in range(n+1)]
for i in range(1,n+1):
    pw[i]=pw[i-1]*(m-1)%mod
ans=0
for i in range(k+1):
    sz=n-i
    ans+=binom(n-1,i)*m%mod*pw[sz-1]%mod
    ans%=mod
print(ans)

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

def inv(a):
  return pow(a,MOD-2,MOD)
fact=[0,1]
for i in range(2,N+1):
  fact.append((fact[-1]*i)%MOD)
def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD
exp=[1]

def pow_k(x,n):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=K*x%MOD
            x=x**2%MOD
            n=(n-1)//2
        else:
            x=x**2%MOD
            n=n//2
    return K*x%MOD 

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

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


def inv(a):
  return pow(a,MOD-2,MOD)


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


def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD


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


ans=0
for i in range(K+1):
  ans+=(M*choose(N-1,i)*exp[N-1-i]%MOD)  
  ans%=MOD
print(ans)

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


def inv(a):
  return pow(a,MOD-2,MOD)


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


def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    return fact[n]*inv(fact[r])*inv(fact[n-r])%MOD


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


ans=0
for i in range(K+1):
  ans+=(M*choose(N-1,i)*exp[N-1-i]%MOD)  
  ans%=MOD
print(ans)

Solution (Python):
MOD = 998244353

lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m, k = [int(_) for _ in input().split()]
ans = 0
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    
print(ans)

Solution (Python):
MOD = 10000000007
lim = 200000
MOD = 998244353

inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        if inv_t[i] == -1:
            _ = mod_inv(i)
            inv_t[i] = _


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % MOD


n, m, k = [int(_) for _ in input().split()]
ans = 0
set_inv()
set_factrial()
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    
print(ans)

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

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

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

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

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

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

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

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

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1 for i in range(n+1)]
frac_inv=[1 for i in range(n+1)]
beki=[m for i in range(n+1)]

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

Solution (Python):
def inv(a,m):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=998244353
n,m,k=map(int,input().split())
frac=[1];frac_inv=[1]
beki=m
ans=0

for i in range(1,n+1):
    frac.append(frac[-1]*i%mod)
    frac_inv.append(inv(frac[-1],mod))

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

Solution (Python):
def main():
  
  

  
  

  
  MOD=998244353
  
  if 'get_ipython' in globals(): 
    
    n, m, k = 60522, 114575, 7559

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

  
  fac = [1] * (n+1)
  inv = [1] * (n+1)

  for i in range(n):
    fac[i+1] = fac[i] * (i+1) % MOD 
    inv[i+1] = pow(fac[i+1], MOD-2, MOD) 
  
  def nCr(n, r):
    if 2*r > n: nCr(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % MOD
  
  ans = 0
  for i in range(k+1):
    tmp = nCr(n-1, i) * m * pow(m-1, n-1-i, MOD) 
    ans += tmp
    ans %= MOD
  print(ans)

main()

Solution (Python):
def main():
  
  

  
  

  
  MOD=998244353
  
  if 'get_ipython' in globals(): 
    
    n, m, k = 60522, 114575, 7559

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

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

main()

Solution (Python):
def main():
  
  

  
  

  
  MOD=998244353
  
  if 'get_ipython' in globals(): 
    
    n, m, k = 60522, 114575, 7559

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

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

main()

Solution (Python):
MOD = 998244353

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

fact = [0 for _ in range(n)]
invfact = [0 for _ in range(n)]
fact[0] = 1
for i in range(1, n):
    fact[i] = fact[i - 1] * i % MOD

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

for i in range(n - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
for i in range(0, k + 1):
    ans += m * pow(m - 1, n - i - 1, MOD) * nCk(n - 1, i) % MOD
    
print(ans % MOD)

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

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

MOD = 998244353

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

p = MOD
N = 2 * 10 ** 5 + 10
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)

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

res %= MOD
print(res)

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

fact = [0] * 200001
invfact = [0] * 200001
fact[0] = 1
invfact[0] = 1

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

for i in reversed(range(1, 200000)):
    invfact[i] = invfact[i+1] * (i+1) % mod

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

ans = ans * M * fact[N-1] % mod

print(ans)

Solution (Python):

import sys

MOD = 998244353  


MAX = 600000
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD
 
def combination(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD

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

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, M, K)

if __name__ == '__main__':
    main()

Solution (Python):

def main():
    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

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

    print(ans%MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MAX = 600000
MOD = 998244353
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD
n, m, k = map(int ,input().split())
ans = 0
color = m
for i in reversed(range(n)):
    val = color
    val *= combinations(n-1,i)
    val %= MOD
    if i <= k:
        ans += val
        ans %= MOD
    color *= (m-1)
    color %= MOD
print(ans)

Solution (Python):
import sys
from functools import lru_cache
 

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
n,m,k=reads()
N = n-1 
mod =  998244353
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

mod=998244353
numbers=[m]
for i in range(n-1):
  numbers.append(numbers[i]*(m-1)%mod)
ans=0
for i in range(k+1):
  ans+=numbers[n-i-1]*cmb(n-1,i)
ans%=mod

print(ans)

Solution (Python):
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
nums = 2*(10**5) 
g1, g2, inverse = [1, 1] , [1, 1], [0, 1]
 
for num in range(2, nums + 1):
    g1.append((g1[-1] * num) % mod)
    inverse.append((-inverse[mod % num] * (mod//num)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

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

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


basum=0
for i in range(k+1):
	if i == 0:
		kumiawase=1
	else:
		kumiawase = kumiawase*(n-i)*pow(i,wari-2,wari)
		kumiawase %= wari
	basum += m * pow(m-1,n-i-1,wari) * kumiawase
	basum %= wari

print(basum)

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

def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % 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
 
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*cmb(n-1, i, mod)*pow(m-1, n-i-1, mod)
  ans %= mod
print(ans)

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

def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % 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
 
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*cmb(n-1, i, mod)*powerDX(m-1, n-i-1, mod)
  ans %= mod
print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m,k=map(int,input().split())
mod=998244353
n_max=2*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

    def get_fact(maxim,mod):
        maxim += 1
        fact = [0]*maxim

        fact[0] = 1
        for i in range(1,maxim):
            fact[i] = fact[i-1] * i % mod

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

        for i in reversed(range(maxim-1)):
            invfact[i] = invfact[i+1] * (i+1) % mod

        return fact, invfact

    def powerful_comb(n,r,mod,fact,invfact):
        return fact[n] * invfact[r] * invfact[n-r] % mod

    ans = 0
    fact, invfact = get_fact(N+1,MOD)
    for i in range(K+1):
        ans += (M*pow(M-1,N-i-1,MOD) * powerful_comb(N-1,i,MOD,fact,invfact)) % MOD

    print(ans % MOD)

if __name__ == "__main__":
  main()

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

    fac = [0] * 10 ** 6
    inv = [0] * 10 ** 6
    finv = [0] * 10 ** 6

    def COM_init():
        fac[0] = 1
        fac[1] = 1
        inv[1] = 1
        finv[0] = 1
        finv[1] = 1

        for i in range(2, 2 * 10**5 +10):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = -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[n-k] * finv[k] % MOD) % MOD

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

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
M=998244353
n,m,k=map(int,input().split())
p,c=[m]*n,[1]*n
for i in range(1,n):
  p[i]=p[i-1]*(m-1)%M
  c[i]=c[i-1]*(n-i)*pow(i,M-2,M)%M
print(sum(p[n-i-1]*c[i]%M for i in range(k+1))%M)

Solution (Python):
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 998244353

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

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]; fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]; fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N+1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N-1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]; finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]; finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    comb = fac[a] * finv[b] % mod * finv[a-b] % mod
    return comb


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

res = 0
for i in range(k + 1):
    res += m * prt[n - i - 1] % mod * nCr(n-1, i)
    res %= mod
print(res)

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

fa = [1] * (lim + 1)
fa_inv = [1] * (lim + 1)

for i in range(lim):
    fa[i+1] = fa[i] * (i+1) % modi

fa_inv[-1] = pow(fa[-1], modi - 2, modi)
for i in range(lim - 1, 0, -1):
    fa_inv[i] = fa_inv[i+1] * (i+1) % modi


def ncr(a, b):
    if a < b:
        return 0
    else:
        return fa[a] * fa_inv[b] % modi * fa_inv[a - b] % modi


prt = [1] * (n + 1)
for i in range(n):
    prt[i+1] = prt[i] * (m - 1) % modi

res = 0
for i in range(k + 1):
    res += m * prt[n - i - 1] * ncr(n - 1, i) % modi
    res %= modi
print(res)

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


mod = 998244353
N = 2 * 10**5  
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

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


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

m_pow = [0] * N
m_pow[0] = 1

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

ans = 0

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

print(ans)

Solution (Python):
mod  = 998244353
MAX = 2*10**5 + 100

inv=[0]*(MAX+1)
inv[1]=1
for i in range(2,MAX+1):
    inv[i]=-(mod//i)*inv[mod%i]%mod

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(g2[-1]*inv[i]%mod)
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod


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

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

Solution (Python):
def comb(n,r,m):
    if 2*r > n:
        r = n - r
    nume,deno = 1,1
    for i in range(1,r+1):
        nume *= (n-i+1)
        nume %= m
        deno *= i
        deno %= m

    return (nume * pow(deno,m-2,m)) % m

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

    ans,comb_r = pow(M-1,N-1,mod),1
    for r in range(1,K+1):
        comb_r = (comb_r * (N-r) * pow(r,mod-2,mod)) % mod
        ans = (ans + comb_r * pow(M-1,N-r-1,mod)) % mod
    ans = (ans * M) % mod

    print(ans)

if __name__ == "__main__":
    main()

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




class combination_mod: 
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] 
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) 
        self.N_factorials_inv = [1 for _ in range(N)] 
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): 
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): 
        if n == 0 or n == self.N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m 
            c = (c * self.N_factorials_inv[n]) % self.m 
            return c
if N == 1:
    print(M%m)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)

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

class Combination:
  def __init__(self, n_max, mod=998244353):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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

comb = Combination(2*10**5)

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

print(res % MOD)

Solution (Python):

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

MOD = 998244353
nCr = Factorial(5*10**5, MOD).comb
N, M, k = map(int, input().split())
print(sum(nCr(N - 1, x) * M * pow(M - 1, N - x - 1, MOD) % MOD for x in range(-~k)) % MOD)

Solution (Python):
class Cmb:
    def __init__(self, N, mod=998244353):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=998244353):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,m,k = map(int,input().split())
mod = 998244353
ans = 0
c = Cmb(N=n, mod=mod)
for x in range(k+1):
    if x==0:
        ans += m*pow(m-1, n-1, mod)
        ans %= mod
    else:
        ans += m*pow(m-1, n-1-x, mod)*c(n-1, x)%mod
        ans %= mod
print(ans%mod)

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

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

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 k in range(K+1):
    ans += M*pow(M-1, N-1-k, mod)*cmb(N-1, k, mod)
    ans %= mod

print(ans)

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

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

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 k in range(K+1):
  ans+=(M*pow(M-1,N-1-k,mod)*cmb(N-1,k,mod))%mod
  ans=ans%mod
print(ans%mod)

Solution (Python):
M=998244353
n,m,k=map(int,input().split())
p,c=[m],[1]
for i in range(1,n):
  p+=[p[-1]*(m-1)%M]
  c+=[c[-1]*(n-i)*pow(i,-1,M)%M]
print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Solution (Python):
M=998244353
n,m,k=map(int,input().split())
a,c=0,1
for i in range(k+1):
  a+=c*m*pow(m-1,n+~i,M)
  c=c*(n+~i)*pow(i+1,-1,M)%M
print(a%M)

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

Solution (Python):
M=998244353
n,m,k=map(int,input().split())
p,c=[m],[1]
for i in range(1,n):
  p+=[p[-1]*(m-1)%M]
  c+=[c[-1]*(n-i)*pow(i,M-2,M)%M]
print(sum(p[n-i-1]*c[i] for i in range(k+1))%M)

Solution (Python):
M=998244353
n,m,k=map(int,input().split())
p,c=[m]*n,[1]*n
for i in range(1,n):
  p[i]=p[i-1]*(m-1)%M
  c[i]=c[i-1]*(n-i)*pow(i,M-2,M)%M
print(sum(p[n-i-1]*c[i]%M for i in range(k+1))%M)

Solution (Python):
import math


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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


def paint(N,M,K):
    return 

def main():
    N, M, K = map(int, input().split())
    ans = 0
    mod = 998244353
    cmb = Combination(N, mod)

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

if __name__ == '__main__':
    main()