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



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
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

# main()
print(main())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

# main()
print(main())

Submission status: Accepted

Solution code:
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

# main()
print(main())

Submission status: Accepted

Solution code:
#factorial
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)
# permutation
def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD
# combination
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)

Submission status: Accepted

Solution code:
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):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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)

Submission status: Accepted

Solution code:
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
    #print(ans)
    tmp*=m_inv
    if i<n:##?
        tmp*=n-i
        tmp*=invs[i]
    tmp%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Problem E - Colorful Blocks

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

# initialization
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

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

# output
print(ans)

Submission status: Accepted

Solution code:
# Problem E - Colorful Blocks

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

# initialization
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

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

# output
print(ans)

Submission status: Accepted

Solution code:
#ライブラリの点検
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)
######################

Submission status: Accepted

Solution code:
#ライブラリの点検
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)
######################

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8


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

Submission status: Accepted

Solution code:
# coding: utf-8


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

Submission status: Accepted

Solution code:
# coding: utf-8


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):  # nCk
        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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8


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

Submission status: Accepted

Solution code:
# coding: utf-8


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

# 隣り合ったブロックを異なる色で塗ると何通りあるか
# 隣り合ったブロック通しで同じ色にする場所をn-1箇所から選ぶ(combination)

# combinationを計算する
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] # n!を計算する
f_inverse = [1, 1]# n!の逆元を計算する
n_inverse = [0, 1] # nの逆元
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)

# c = m * ((m-1)**(n-1))
# L = []
# for i in range(k+1):
#     L.append(c)
#     c=c//(m-1)

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):
    # print(count, c, combination(n-1, i, mod))
    count += combination(n-1, i, mod) * m * pow_m(n-1-i)#L[i]
    count %= mod
    
print(count)

Submission status: Accepted

Solution code:
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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
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)

Submission status: Accepted

Solution code:
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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

lim = 2*10**5
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

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

def C(n, r):
	return (((fact[n]*fact_inv[r])%mod)*fact_inv[n-r])%mod


N, M, K = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

def power(x, n, p):
	ans = 1
	while n:
		if n%2:
			ans = ans*x%p
		x = x*x%p
		n >>= 1
	return ans

lim = 2*10**5
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = power(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


N, M, K = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

lim = 2*10**5
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

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

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


N, M, K = MAP()

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

print(ans)