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 a():
    mod = 998244353

    def bi(x):
        o = []
        while x != 0:
            o.append(x%2)
            x //= 2
        return o

    o = bi(mod - 2)
    leo = len(o)
    p = [0] * leo

    def modinv(m):
        p[0] = m
        for i in range(1,leo):
            a = p[i-1]
            a *= a
            a %= mod
            p[i] = a
        b = 1
        for i in range(leo):
            if o[i]:
                b *= p[i]
                b %= mod
        return b

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

    C = [1]*(K+1)
    for i in range(1,K+1):
        C[i] = (C[i-1] * (N-i) * modinv(i))%mod

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

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

    print(ans)

a()

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

Solution (Python):
def powmod(x, n,mod):
  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%mod

  return K * x 

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

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

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
N,M,K=map(int,input().split())
mod=998244353
A=0
for i in range(K+1):
 A+=powmod(M-1, N-1-i,mod)*cmb(N-1,i,mod)
 A%=mod
print((A*M)%mod)

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

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

mod = 998244353 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
ans =0
ml =[m-1]*n

if n ==1:
    print(m)
    exit()
elif m ==1:
    if k ==n-1:
        print(1)
        exit()
    else:
        print(0)
        exit()
for l in range(1,n):
    ml[l] = ml[l-1]*(m-1) % mod

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 )

for j in range(k+1):
    if n-2-j >=0:
        a = m*ml[n-2-j]*cmb(n-1,j,mod)
        ans +=a
    elif n - 2- j == -1:
        a = n
        ans +=a
    elif n - 2- j == -2:
        a = 1
        ans +=a        
print(ans % mod)

Solution (Python):
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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)

n, m, k = [int(i) for i in input().split()]

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)

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

mod = 998244353
n,m,k = map(int,input().split())
MAX_N = 10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

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


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




res = 0

tmp = m*pow(m-1,n-k-1,mod)

for r in range(n-k-1,n):
    res = (res + tmp*mod_comb_k(n-1,r,mod)%mod)%mod
    tmp = tmp*(m-1)%mod

print(res)

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 = 998244353
N = 2*10 ** 5 
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)
s = m
x = m
for i in range(k):
  s = (m*s)%p
for i in range(n-k-1):
  y = x*cmb(k+i,i,p)
  s = (m*s-y)%p
  x = (x*(m-1))%p
print(s)

Solution (Python):
MOD = 998244353
def main():
    N, M, K = (int(_) for _ in input().split())
    fact = [0] * (N + 1) 
    ifact = [0] * (N + 1)

    for i in range(N+1):
        if i == 0:
            fact[i] = 1
            continue
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N)[::-1]:
        ifact[i] = ((i+1) * ifact[i+1])%MOD

    out = [0] * N
    coef = 1
    for i in range(N):
        out[N-1-i] = (coef * M * fact[N-1] * ifact[i] * ifact[N-1-i])%MOD
        coef *= M-1
        coef %= MOD
    ret = 0
    for i in range(K+1):
        ret += out[i]
        ret %= MOD
    print(ret)
    return


if __name__ == '__main__':
    main()

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

N, M, K = map(int, readline().split())
P = 998244353
def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

ans = 0
_n = N - 1
for k in range(K + 1):
    a = N - k
    
    if k == 0:
        comb = 1
    elif k == 1:
        comb = _n
    else:
        comb = comb * mod_div((_n - k + 1), k) % P
    b = M * mod_pow(M-1, a-1) % P
    b = b * comb % P
    ans += b
    ans %= P


print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        fac = self.fac
        finv = self.finv
        mod = self.MOD
        return fac[n] * (finv[k]*finv[n-k] % mod) % mod


def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


def solve(N: int, M: int, K: int):

    cmb = Combination(N)
    tot = 0
    for k in range(N-K, N+1):
        buf = cmb(N-1, k-1)
        buf *= (M*pow(M-1, k-1, MOD)) % MOD
        buf %= MOD
        
        tot += buf
        tot %= MOD
    print(tot)
    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):
import sys

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


def COMinit():
  fac[0] = 1
  fac[1] = 1
  finv[0] = 1
  finv[1] = 1
  inv[1] = 1
  for i in range(2,MAX):
    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
  
  
MAX=n+1
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

def HCOM(n,r):
  return COM(n+r-1,r)
  

t=m
if n-k>1:
  for i in range(1,n-k-1):
    t*=m-1
    t%=MOD


ans=0
for c in range(n-k,n+1):
  if c>1:
    t*=m-1
  t%=MOD
  
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

Solution (Python):

import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache

readline=sys.stdin.readline
sys.setrecursionlimit(2000000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)

def main():
    m=998244353
    N,M,K=list(map(int,input().split()))
    facs=get_facs(10**6,m)
    ssum=0
    for a in range(0,K+1):
        p=(pow(M-1,N-a-1,m)*M)%m
        q=comb(N-1,a,m,facs)
        r=(p*q)%m
        ssum+=r
        ssum%=m
    print(ssum)
main()

Solution (Python):
N, M, K = map(int, input().split())
dp = [0]*(K+1)
P = 998244353
dp[0] = pow(M-1, N-1, P) * M % P

inv_t = [0]*(2*10**5+1)
inv_t[1] = 1
for i in range(2,2*10**5+1):
  inv_t[i] = inv_t[P % i] * (P - int(P / i)) % P

if M == 1 and K == N-1:
    print(1)
else:
    for i in range(1, K+1):
        temp = dp[i-1]*(N-i)
        temp %= P
        temp *= inv_t[i]
        temp %= P
        temp *= inv_t[M-1]
        temp %= P
        dp[i] = temp

    ans = 0
    for i in range(K+1):
        ans += dp[i]
        ans %= P

    print(ans)

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

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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 )

p=mod
ans=0
for i in range(k+1):
  x=power_func(m-1,n-1-i,p)
  y=cmb(n-1, i, mod)
  ans=(ans+m*x*y)%p
print(ans)

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

def cmb(n,r):
    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+100
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())
P=[1] 

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

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

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

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

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


n, m, k = map(int, input().split())
r = m
x = [m]
for i in range(n-1):
    r = (r*(m-1))%p
    x.append(r)
z = n//2

for i in range(1, k+1):
    r = (r + x[-i-1]*cmb(n-1,i,p))%p
print(r)

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

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

p = 998244353
_N = N + 100 
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)

Mpower = [1, M]
lpower = [1, M-1]
for i in range(2, _N + 1):
    Mpower.append((Mpower[-1] * M) % p)
    lpower.append((lpower[-1] * (M-1)) % p)

ans = Mpower[N]
for i in range(K+2, N+1):
    ans = ans - (cmb(N-1, i-1,p)*M *lpower[N-i]) % p
    ans = ans % p

print(ans)

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

Solution (Python):

import bisect
import collections
import sys
import functools
import scipy
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  




from operator import mul
from functools import reduce


def modinv(a,*args):
    return pow(a, MOD - 2, MOD)

def combination_list(n, mod=MOD):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst


def comb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    
    
    
    
    
    
    
    
    
    
    
    
    
    n = N - 1
    nCr = 1
    _sum = 0
    
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    
    nCrArr = combination_list(n,MOD)
    for k in range(K + 1):
        
        
        _sum += M * e[N - k - 1] * nCrArr[k] % MOD
        
        
        
    print(_sum % MOD)
    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):

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

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

def comb(n, k):
    if (n < k) or (k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
    
if K == 0:
    ans = (M*pow(M-1, N-1, MOD))%MOD 
if K >= 1:
    ans = ((M*pow(M-1, N-1, MOD))%MOD + (M*pow(M-1, N-2, MOD)*(N-1)))%MOD
if K > 1:
    for i in range(K-1):
        ans = (ans + M*pow(M-1, N-3-i, MOD)*comb(N-1,i+2)%MOD)%MOD
print(ans)

Solution (Python):
def inv_mod(a, p):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, M, K = inpl()

if M == 1:
    if K == N-1:
        print(1)
    else:
        print(0)
else:
    q = pow(M-1,N-1,MOD) * M % MOD
    S = q
    f = inv_mod(M-1,MOD)
    for k in range(1,K+1):
        q *= f * (N-k) * inv_mod(k,MOD)
        q %= MOD
        S += q
        S %= MOD
    print(S)

Solution (Python):
class Combination:

    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 resolve():
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n, mod)
    ans = 0
    for i in range(k + 1):
        ans += c(n - 1, i) * pow(m - 1, n - i - 1, mod)
    ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
n, m, k = map(int, input().split())
MOD = 998244353
fact = [0 for _ in range(n+1)]
fact[1] = m

for i in range(2, n+1):
    fact[i] = fact[i-1] * (m - 1)
    fact[i] %= MOD

class Facts():
    
    def __init__(self, max_num=2 * 10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        
        
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def comb_base(self, n, k):
        
        
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a, b = 1, 1
        for i in range(k):
            a *= (n-i)
            a %= MOD
        for i in range(k):
            b *= (k-i)
            b %= MOD
        return (a*self.power_func(b, self.p-2)) % self.p

    def perm(self, n, k):
        
        
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[n-k]
        return (a * self.power_func(b, self.p-2)) % self.p


    def power_func(self, a, b):
        
        
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans


facts = Facts(p=MOD)
ans = 0
for i in range(n-k, n+1):
    if i != n:
        ans += fact[i] * facts.comb(n-1, n-i)
    else:
        ans += fact[i]
    ans %= MOD
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, k = list(map(int, readline().split()))
    MM = 998244353

    ans = 0
    com = 1

    for i in range(k + 1):
        l = n - i
        x = pow(m - 1, l - 1, MM)
        ans += m * x * com
        ans %= MM
        com *= n - (i + 1)
        com *= pow(i + 1, MM - 2, MM)
        com %= MM

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m,k = mi()

mod = 998244353

dp = [0]*n

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

'''
ここは任意
'''
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 )

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

ans = 0
for i in range(k+1):
    tmp = cmb(n-1,i,mod)*dp[n-1-i] % mod
    ans += tmp
    ans %= mod
print(ans)

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

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

PRIME = 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 ) % PRIME )
    inverse.append( ( -inverse[PRIME % i] * (PRIME//i) ) % PRIME )
    g2.append( (g2[-1] * inverse[-1]) % PRIME )

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

print(ans)

Solution (Python):
def resolve():
    mod = 998244353
    MAX_N = 2 * (10 ** 5)

    fact = [1]
    fact_inv = [0] * (MAX_N + 4)
    for i in range(MAX_N + 3):
        fact.append(fact[-1] * (i + 1) % mod)

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

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

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

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


resolve()

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

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

fac,ifac=make_tables(998244353,n)



ans=0
for  i in range(k+1):
    
    ans+=cmb(n-1,i,998244353,fac,ifac)*m*pow(m-1,n-1-i,998244353)
    ans%=998244353

print(ans)

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

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

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

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

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

Solution (Python):

mod = 998244353

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

ans = 0


class Mint(object):
    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  
        self.g2 = [1, 1]  
        inverse = [0, 1]  

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


mint = Mint()
mint.cmb_prep(N-1, mod)

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

print(ans % mod)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M, K = [int(x) for x in input().strip().split()]
    MOD = 998244353
    if M == 1:
        if N == 1:
            print(1)
            exit()
    
    fact = [1] * (N+1)
    inv_fact = [1] * (N+1)
    for i in range(1, N+1):
        fact[i] = ((i) * fact[i-1]) % MOD
    
    inv_fact[-1] = pow(fact[-1], MOD-2, MOD)
    for i in range(N-1):
        inv_fact[N-i-1] = (inv_fact[N-i] * (N - i)) % MOD

    def nCr(n, r):
        if r == 0 or r == n:
            return 1
        r = min(r, n - r)
        return (fact[n] * inv_fact[n-r] * inv_fact[r]) % MOD

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

    print(ans)

if __name__ == '__main__':
    main()

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

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

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

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

Solution (Python):
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import itertools
import math
n,m,k = ma()
mod = 998244353
nmax = 10**6

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

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

Solution (Python):
def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        if K == N-1:
            print(1)
        else:
            print(0)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac = [0]*(N+1)
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
    
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
    
    ans = 0
    base = [1,pow(M-1,N-K-1,MOD)]
    for i in range(K+1):
        base.append((base[-1]*(M-1))%MOD)

    
    for i in range(K+1):
        ret = comb(N-1,i)*(M*base[-i-2])
        ans += ret
    
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
n,m,k=map(int,input().split())
factorials=[]
current=1
for i in range(n):
  factorials.append(current)
  current=((i+1)*current)%998244353
inverselist=[]
for i in range(n):
  inverselist.append(pow(factorials[i],998244351,998244353))
ans=0
for i in range(0,k+1):
  ans=(ans+m*pow(m-1,n-i-1,998244353)*factorials[n-1]*inverselist[i]*inverselist[n-1-i])%998244353
print(ans)