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):
N,M,K=map(int,input().split())
MOD=998244353
ans=0
x,y=1,1
for k in range(K+1):
    ans=ans+M*x*pow(y,MOD-2,MOD)*pow(M-1,N-1-k,MOD)
    ans=ans%MOD
    x=x*(N-k-1)
    y=y*(k+1)
    x=x%MOD
    y=y%MOD
print(ans%MOD)

Solution (Python):
MOD = 998244353
MAX = 510000
fac = [1,1] 
finv = [1,1] 
inv = [None, 1] 

def comb_init():
	for i in range(2, MAX):
		fac.append(fac[i-1] * i % MOD)
		inv.append(MOD - inv[MOD % i] * (MOD//i) % MOD)
		finv.append(finv[i-1] * inv[i] % MOD)

def inverse_mod(a):
	""" Calculate inverse of the integer in a modulo MOD """
	return pow(a, MOD-2, MOD)

def comb_mod(n, r):
	""" Calculate nCr modulo MOD. """
	if n < r: return 0
	if n < 0 or r < 0: return 0
	return fac[n]* (finv[r]*finv[n-r] % MOD) % MOD

def solve(n, m, k):
	ans = 0
	for k in range(K+1):
		ans = (ans + m*(comb_mod(n-1,k)*pow(m-1, n-k-1, MOD) % MOD) % MOD) % MOD
	return ans

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


class ComMod():
  def __init__(self,n,mod):
    self.n=n
    self.mod=mod
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=self.mod
    self.ifact[n]=pow(self.fact[n],self.mod-2,self.mod)
    for i in range(n,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=self.mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod



def powMod(n,p,m):
  if p==0:
    return 1
  if p%2==0:
    t=powMod(n,p//2,m)
    return t*t%m
  return n*powMod(n,p-1,m)%m


def main():
  n,m,k=LI()
  mod=998244353
  c=ComMod(200005,mod)

  ans=0
  for i in range(k+1):
    
    ans=(ans+m*c.com(n-1,i)*powMod(m-1,n-1-i,mod))%mod

  return ans


print(main())

Solution (Python):


M = 998244353

def facts(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

(fcs, invs) = facts(n, M)

c = 0
for i in range(k + 1):
    c = (c + m * fcs[n - 1] * invs[i] * invs[n - 1 - i] * pow(m - 1, n - 1 - i, M)) % M

print(c)

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

MAX = 2*10**5+100
MOD = 998244353
fact = [0]*MAX 
inv = [0]*MAX 
finv = [0]*MAX 
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

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

for i in range(N):
    if N-1-i<=K:
        ans += C(N-1, i)*M*pow(M-1, i, MOD)
        ans %= MOD

print(ans)

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

p = 998244353

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



for k in range(K+1):
    counter += factorial[N-1]*pow(factorial[k],p-2,p)*pow(factorial[N-k-1],p-2,p)*M*pow(M-1,N-1-k,p)
print(counter%p)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class ComMod():
  def __init__(self,n_max,mod):
    self.mod=mod
    self.fact=[0]*(n_max+1)
    self.ifact=[0]*(n_max+1)
    self.fact[0]=1  
    for i in range(1,n_max+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=mod
    self.ifact[n_max]=pow(self.fact[n_max],mod-2,mod)
    for i in range(n_max,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod

def main():
  n,m,k=LI()
  res=0
  mod=998244353
  tmp=m*pow(m-1,n-k-1,mod)

  c=ComMod(200005,mod)

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


print(main())

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class ComMod():
  def __init__(self,n,mod):
    self.n=n
    self.mod=mod
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=self.mod
    self.ifact[n]=pow(self.fact[n],self.mod-2,self.mod)
    for i in range(n,0,-1):
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=self.mod
  def com(self,n,k):
    if n<0 or k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod

def main():
  n,m,k=LI()
  res=0
  mod=998244353
  tmp=m*pow(m-1,n-k-1,mod)

  c=ComMod(200005,mod)
  for r in range(n-k-1,n):
    res=(res+tmp*c.com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res


print(main())

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

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

class nCrMod():
  def __init__(self,n,mod):
    self.n=n
    self.mod=mod
    self.fact=[0]*(n+1)
    self.ifact=[0]*(n+1)
    self.fact[0]=1  
    for i in range(1,n+1):
      self.fact[i]=self.fact[i-1]*i
      self.fact[i]%=self.mod
    self.ifact[n]=pow(self.fact[n],self.mod-2,self.mod)
    for i in range(1,n+1)[::-1]:
      self.ifact[i-1]=self.ifact[i]*i
      self.ifact[i-1]%=self.mod
  def comb(self,n,k):
    if k<0 or n<k:
      return 0
    return self.fact[n]*(self.ifact[k]*self.ifact[n-k]%self.mod)%self.mod

def main():
  n,m,k=LI()
  res=0
  mod=998244353
  tmp=m*pow(m-1,n-k-1,mod)

  c=nCrMod(200005,mod)
  for r in range(n-k-1,n):
    res=(res+tmp*c.comb(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res


print(main())

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  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 or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  res=0
  tmp=m*pow(m-1,n-k-1,mod)
   
  for r in range(n-k-1,n):
    res=(res+tmp*com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res


print(main())

Solution (Python):

MOD = 998244353 

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

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

def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD

def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD

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



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

t %= MOD
print(t)

Solution (Python):
class Combination:

    """
    (使用例)
    comb = Combination(n_max, mod)
    comb(n, r)

    (注意)
    n_max != 0
    """

    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


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

ans = 0
for k in range(K+1):
    t1 = M % mod
    t2 = pow(M-1, N-1-k, mod)
    t3 = comb(N-1, k)
    ans = (ans + t1 * t2 * t3) % mod

print(ans)

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

ans=0
if m==1:
  	print(1 if k==n-1 else 0)
  	exit()
tmp=m*pow(m-1,n-1,mod)
m_inv=pow(m-1,mod-2,mod)
invs=[0]+[pow(i+1,mod-2,mod) for i in range(n)]
for i in range(1,k+2):
    ans+=tmp
    
    tmp*=m_inv
    if i<n:
        tmp*=n-i
        tmp*=invs[i]
    tmp%=mod
print(ans%mod)

Solution (Python):
p = 998244353
max = 2 * (10**5)
fact = [1,1]
facti = [1,1]
inv = [0,1]
for i in range(2, max + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    facti.append((facti[-1] * inv[-1]) % p)

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

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

Solution (Python):
mod = 998244353
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
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):
    tmp_c = cmb(N-1, k, mod)
    tmp_pow = pow(M-1, N-1-k, mod)
    ans += (tmp_c * tmp_pow * M) % mod

print(ans%mod)

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

n = N
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
ans = 0

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

print(ans)

Solution (Python):



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


MOD = 998244353
fact = [1, 1]
fact_inv = [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)
    fact_inv.append((fact_inv[-1] * inv[-1])%MOD)
    

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

ans = 0


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


print(ans)

Solution (Python):



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


MOD = 998244353
fact = [1, 1]
fact_inv = [1, 1]
inv = [0, 1]
pow_list = [1, M-1]
for i in range(2, N+1):
    fact.append((fact[-1] * i)%MOD)
    inv.append((-inv[MOD%i] * (MOD//i))%MOD)
    fact_inv.append((fact_inv[-1] * inv[-1])%MOD)
    pow_list.append(pow_list[i-1]*(M-1)%MOD)

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

ans = 0


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


print(ans)

Solution (Python):

class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod
    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod


N,M,K=map(int,input().split())
mod=998244353
ans=0
C=Combi(2*10**5,mod)
for i in range(K+1):
    ans+=M*C.combi(N-1,i)*pow(M-1,N-1-i,mod)
print(ans%mod)

Solution (Python):

class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod


N,M,K=map(int,input().split())
mod=998244353
ans=0
C=Combi(2*10**5,mod)
for i in range(K+1):
    ans+=M*C.combi(N-1,i)*pow(M-1,N-1-i,mod)
print(ans%mod)

Solution (Python):
MOD = 998244353 
fact = [0] * 220000
invfact = [0] * 220000

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

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

for i in range(220000 - 2, -1, -1):
    invfact[i] = invfact[i+1] * (i+1) % MOD

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

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

N = 10 ** 6


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


kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
    kai.append(kai[-1] * i % mod)
    rev_kai.append(rev_kai[-1] * inv_t[i] % mod)


def cmb(n, r):
    return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

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

if m == 1 and k == n-1:
    print(1)
else:
    print(ans)

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

mod = 998244353

def _fac_inv(_n, _mod):
    _fac = [1] * (_n+1)  
    _inv = [1] * (_n+1)  
    for i in range(_n):
        _fac[i+1] = _fac[i] * (i+1) % _mod
    _inv[n] = pow(_fac[n], mod-2, mod)
    for i in range(_n, 0, -1):
        _inv[i-1] = _inv[i] * i % _mod

    return _fac, _inv

fac, inv = _fac_inv(n, mod)

ans = 0
mm = (m * pow(m-1, n-1-k, mod)) % mod
for ii in range(k+1):
    i = k-ii
    ans = (ans + mm * fac[n-1] * inv[i] * inv[n-1-i]) % mod
    mm = mm * (m-1) % mod

print(ans)

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

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

ans = 0
for k in range(K+1):
    x = M *pow(M-1, N-1-k, mod) *fact[N-1] *fact_inv[k] *fact_inv[N-1-k]
    ans += x %mod
    ans = ans %mod
print(ans)

Solution (Python):



def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    iR = [1]
    C = [1]
    for i in range(1, k+1):
        iR.append(max(1, (-(mod//i) * iR[mod % i]) % mod))
        C.append((n-i)*C[i-1]*iR[i] % mod)

    ret = 0
    p = m*pow(m-1, n-1-k, mod) % mod
    for i in range(1, k+1):
        ret += p*C[-i] % mod
        p = p*(m-1) % mod
    ret += p

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):



def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    iR = [1]*(k+1)
    C = [1]*(k+1)
    for i in range(1, k+1):
        iR[i] = max(1, (-(mod//i) * iR[mod % i]) % mod)
        C[i] = (n-i)*C[i-1]*iR[i] % mod

    ret = 0
    p = m*pow(m-1, n-1-k, mod) % mod
    for i in range(1, k+1):
        ret += p*C[-i] % mod
        p = p*(m-1) % mod
    ret += p

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):



def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

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

    ret = p
    iR = [1]*(k+1)
    im = pow(m-1, mod-2, mod)

    for i in range(1, k+1):
        iR[i] = max(1, (-(mod//i) * iR[mod % i]) % mod)
        ncr = (ncr * (n-i)*iR[i]) % mod
        p = (p*im) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
N,M,K=map(int,input().split())
P=998244353
class FactInv:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[1]*(N+1);ifact=[0]*(N+1)
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
FI=FactInv(N+10,P)
ans=0
for k in range(0,K+1):
    ans+=(M*FI.comb(N-1,k)*pow(M-1,N-1-k,P))%P
    ans%=P
print(ans)

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


def modpow(a, n, mod):
    y = 1
    while n:
        if n & 1:
            y = y * a % mod
        a = a * a % mod
        n >>= 1
    return y

MAX = 500000
fac = [0]*MAX
facinv = [0]*MAX
inv = [0]*MAX

def modinv(a, mod):
    b = mod
    x, u = 1, 0
    while b:
        q = a//b
        a, b = b, a-q*b
        x, u = u, x-q*u
    x %= mod
    return x


def mod_nCr_init(n, mod):
    fac[0] = fac[1] = 1
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod


def mod_nCr(n, r, mod):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * (facinv[r] * facinv[n-r] % mod) % mod


mod_nCr_init(MAX, mod)


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

print(ans)

Solution (Python):
mod = 998244353


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

    def calc(self, n, k):  
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


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

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

print(ans)

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

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

Solution (Python):
n,m,k = map(int,input().split())
mod = 998244353
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac = [0]*(n+1)
finv = [0]*(n+1)
fac[0] = finv[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

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

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

fact = [1]
rfact = [1]
for i in range(1, N+1):
    fact.append(fact[i-1]*i%MOD)
    rfact.append(pow(fact[i], MOD-2, MOD))
 
def cmb(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

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

Solution (Python):
import math

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

MOD=998244353

fact = [0] * (n+1)
inv = [0] * (n+1)
factinv = [0] * (n+1)

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

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

def cbn(n, k, fact, factinv, MOD):
    return fact[n] * factinv[n-k] * factinv[k] % MOD

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

s = 0
for i in range(k+1):
    s += cbn(n-1, i, fact, factinv, MOD) * m * power(m-1, n-1-i, MOD)

print(s % MOD)

Solution (Python):



def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*pow(m-1, n-1, mod) % mod
    ret = p
    inv = pow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*pow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):



def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):



def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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,~i+n,M);c=c*(~i+n)*pow(i+1,-1,M)%M
print(a%M)

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

Solution (Python):
M=998244353
class Factorial:
    def __init__(self,n):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        for i in range(1,n+1):f[i]=b=b*i%M
        self.inv=inv=[0]*(n+1)
        inv[n]=b=pow(self.f[n],M-2,M)
        for i in range(n,0,-1):inv[i-1]=b=b*i%M
    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]%M
        else:return 0
comb=Factorial(10**5*5).comb
n,m,k=map(int,input().split())
print(sum(m*comb(n-1,i)*pow(m-1,~i+n,M)for i in range(k+1))%M)

Solution (Python):
M=998244353
class Factorial:
    def __init__(self,n):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        for i in range(1,n+1):f[i]=b=b*i%M
        self.inv=inv=[0]*(n+1)
        inv[n]=b=pow(self.f[n],-1,M)
        for i in range(n,0,-1):inv[i-1]=b=b*i%M
    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]%M
        else:return 0
comb=Factorial(10**5*5).comb
n,m,k=map(int,input().split())
print(sum(m*comb(n-1,i)*pow(m-1,~i+n,M)for i in range(k+1))%M)

Solution (Python):
mod = 998244353
n,m,k = map(int, input().split())
def setFact(n, mod):
    global fact
    global ifact
    fact = [0]*(n+1)
    fact[0] = 1
    ifact = [0] * (n+1)
    for i in range(1, n+1):
        fact[i] = (fact[i-1]*i)%mod
    ifact[n] = pow(fact[n], mod-2, mod)
    for i in range(1, n+1):
        ifact[n-i] = ifact[n-i+1]*(n-i+1)%mod
def combination(n, k, mod):
    global fact
    global ifact
    if k < 0 or k > n:
        return 0
    else:
        return fact[n]*ifact[n-k]*ifact[k]%mod
setFact(n, mod)
ans = 0
now = pow(m-1, n-1-k, mod)
for i in range(k, -1, -1):
    ans = (ans + m*now*combination(n-1, i, mod)) %mod
    now *= m-1
    now %= mod
print(ans)

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





def combination(n, r, p):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return (f[n]*f_inverse[r]*f_inverse[n-r])%p

f = [1, 1] 
f_inverse = [1, 1]
n_inverse = [0, 1] 
for i in range(2, n+1):
    f.append((f[i-1]*i)%mod)
    n_inverse.append( (-1*(mod//i)*n_inverse[mod%i])%mod )
    f_inverse.append((f_inverse[i-1]*n_inverse[i])%mod)







def pow_m(k):
    if k == 0:
        return 1
    elif k%2==0:
        return (pow_m(k//2)**2)%mod
    else:
        return (m-1)*(pow_m(k//2)**2)%mod

count = 0
for i in range(k+1):
    
    count += combination(n-1, i, mod) * m * pow_m(n-1-i)
    count %= mod
    
print(count)

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

y = [0,m]
for i in range(n):
    y.append((y[-1]*(m-1))%p)
r = 0
for i in range(k+1):
    r = (r + y[n-i]*cmb(n-1, i, p))%p
print(r)

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

y = [0,m]
for i in range(n):
    y.append((y[-1]*(m-1))%p)
r = 0
for i in range(k+1):
    r += (y[n-i]*cmb(n-1, i, p))%p
print(r%p)

Solution (Python):
n, m, k = list(map(int, input().split()))
mod = 998244353
m_ = m - 1
n_ = n - 1
m_p = {0: 1}
ans = 0
fac = {0: 1, 1: 1}
finv = {0: 1, 1: 1}
inv = {1: 1}

def comb_init():
    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
def comb(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
def pow_init(m):
    for i in range(1, m):
        m_p[i] = m_p[i - 1] * m_
        m_p[i] %= mod

comb_init()
pow_init(n_ - k)
for i in range(k, -1, -1):
    if n_ - i not in m_p:
        m_p[n_ - i] = m_p[n_ - i - 1] * m_ % mod
    d = m * comb(n_, i) % mod 
    d *= m_p[n_ - i]
    ans += d % mod
    ans %= mod
print(ans)