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 sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

    N,M,K = LMIIS()
    ans = 0
    cmb = Combinations(N-1,MOD)
    #i個のブロックを連結、全体でN-i個、どこを連結させるかは(N-1)Ci通り
    powtable = [0] * N
    powtable[N-K-1] = M * pow(M-1,N-K-1,MOD) % MOD
    for i in range(N-K,N):
        powtable[i] = powtable[i-1] * (M-1) % MOD

    for i in range(K+1):
        ans += powtable[N-i-1] * cmb.nCr(i)
        ans %= MOD
    # for i in range(K+1):
    #     ans += M * pow(M-1,N-i-1,MOD) * cmb.nCr(i)
    #     ans %= MOD
    print(ans)

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    N, M, K = map(int, input().split())

    #output
    mod = 998244353

    n_ = 4*10**5 + 5
    fun = [1]*(n_+1)
    for i in range(1,n_+1):
        fun[i] = fun[i-1]*i%mod
    rev = [1]*(n_+1)
    rev[n_] = pow(fun[n_],mod-2,mod)
    for i in range(n_-1,0,-1):
        rev[i] = rev[i+1]*(i+1)%mod
    def cmb(n,r):
        if n <= 0 or r < 0 or r > n: return 0
        return fun[n]*rev[r]%mod*rev[n-r]%mod

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

    answer %= mod

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

    print(answer)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor, inf
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
class Combinations:
    def __init__(self,n,p):
        self.n = n
        self.p = p
        self.g1 = [1,1]
        self.g2 = [1,1]
        inverse = [0,1]
        for i in range(2, self.n + 1):
            self.g1.append( ( self.g1[-1] * i ) % self.p )
            inverse.append( ( -inverse[self.p % i] * (self.p//i) ) % self.p )
            self.g2.append( (self.g2[-1] * inverse[-1]) % self.p )
    def nCr(self,r):
        if r < 0 or self.n < r:
            return 0
        r = min(r, self.n-r)
        return self.g1[self.n] * self.g2[r] * self.g2[self.n-r] % self.p

def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD =  998244353

    N,M,K = LMIIS()
    ans = 0
    cmb = Combinations(N-1,MOD)
    #i個のブロックを連結、全体でN-i個、どこを連結させるかは(N-1)Ci通り
    for i in range(K,-1,-1):
        ans += M * pow(M-1,N-i-1,MOD) * cmb.nCr(i)
        ans %= MOD
    print(ans)

    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

frac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  frac[i] = i*frac[i-1]%MOD
  
inv[n] = pow(frac[n], MOD-2, MOD)
for i in range(n-1, 0, -1):
  inv[i] = inv[i+1]*(i+1)%MOD
  
def nCr(n,r):
  res = frac[n]*inv[n-r]%MOD
  res = res*inv[r]%MOD
  return res
  
ans  = 0
for i in range(k+1):
  num_pair_block = i + 1
  num_seg = n-i
  ans += m*pow(m-1, num_seg-1, MOD)*nCr(n-1, i)%MOD
  ans %= MOD
  
print(ans)

Submission status: Accepted

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


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



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

Submission status: Accepted

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

    # Σ(0<=x<=K){M*pow((M-1),(N-x-1))*Combination(N-1,x)}を求めたい

    fact = [1] * (N+1) # 階乗を格納するリスト
    factinv = [1] * (N+1) # 階乗を格納するリスト
    for i in range(N):
        fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
        factinv[i+1] = pow(fact[i+1], MOD-2, MOD)# MODを法とした逆元（フェルマーの小定理）

    def comb(n,k): # 組み合わせ(MOD)を返却する
        return fact[n] * factinv[n-k] * factinv[k] % MOD

    def solve(k):
        r = M * pow(M-1,N-1-k,MOD) * comb(N-1,k)
        return r

    for k in range(K+1):
        ans += solve(k)
        ans %= MOD
    print (ans)

main()

Submission status: Accepted

Solution code:
import math
import numpy as np

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

def inv(x, mod):
    return pow(x, mod-2, mod)

class combination:
    def __init__(self, n, mod = 10**9 + 7):
        self.MOD = mod
        self.to = np.ones(n,dtype=np.int64)
        self.rev = np.ones(n,dtype=np.int64)
        for i in range(1, n):
            self.to[i] = self.to[i-1] * i % mod
        self.rev[-1] = inv(int(self.to[-1]),mod)
        for i in range(n-1, 0, -1):
            self.rev[i-1] = self.rev[i] * i % mod
    
    def nCk(self, n ,k):
        return self.to[n] * self.rev[k] % self.MOD * self.rev[n-k] % self.MOD

MOD = 998244353

n,m,k = NextInts()

cob = combination(200200, MOD)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        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)
        self.fac, self.finv, self.mod = fac, finv, mod

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

mod = 998244353

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

mc = ModComb(N, mod)

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#https://mathtrain.jp/tyohukuc

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 = n+1 # N は必要分だけ用意する
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)

ans = 0
beki = [1,m-1]
for i in range(2,N+1):
    beki.append(((beki[-1]*(m-1)) % p))

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

Submission status: Accepted

Solution code:
A,B,C=map(int,input().split())

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

p = 998244353
N = 10 ** 6  # N は必要分だけ用意する
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)

i=0
ans=0
while i<=C:
    ans+=B*pow(B-1,A-1-i,p)*cmb(A-1,i,p)
    i+=1

ans=ans%p
print(ans)

Submission status: Accepted

Solution code:
# E - Colorful Blocks
import sys
readline = sys.stdin.readline

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

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i] * (i+1) % MOD)

f_inv = [1] * N
f_inv[N-1] = pow(f[N-1], MOD-2, MOD)
for i in range(N-1)[::-1]:
    f_inv[i] = f_inv[i+1] * (i+1) % MOD

# 組み合わせ関数
def comb_mod(n, r, p):
    return (f[n] * f_inv[r] * f_inv[n-r])%p

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

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 998244353
class Combination(object):
    def __init__(self, N, MOD):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        # 前計算
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    Com = Combination(N-1, MOD)
    ans = 0
    for k in range(K+1):
        ans += M * pow(M-1, N-k-1, MOD) * Com.com(N-1, k)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=998244353

MAX_N=n+5
fac = [1,1] + [0]*MAX_N
finv = [1,1] + [0]*MAX_N
inv = [0,1] + [0]*MAX_N
for i in range(2,MAX_N):
  fac[i] = fac[i-1] * i % mod
  inv[i] = mod - inv[mod % i] * (mod // i) % mod
  finv[i] = finv[i-1] * inv[i] % mod

def nCk(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

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

print(ans)

Submission status: Accepted

Solution code:
# n choose 0, n choose 1, ..., n choose kすべて一気に求める
def binomials_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: [n choose 0 mod p, n choose 1 mod p, ..., n choose k mod p]
    '''
    binomials = [1, n] # binomial[i] = n choose i mod p
    inv = [0, 1] # inv[i] : inverse of i mod p
    for i in range(2, k + 1):
        inv.append(( inv[p % i] * (p - p//i) ) % p ) # inverse of i
        binomials.append(binomials[i - 1] * (n - i + 1) * inv[i] % p)

    return binomials

# a^n mod p
def exp_by_sq_p(a, n, p):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = a % p
    elif  n % 2 == 0:
        exp = exp_by_sq_p(a * a % p, n // 2, p)
    else:
        exp = a * exp_by_sq_p(a * a % p, (n - 1) // 2, p) % p
    return exp % p

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

binomials = binomials_p(N - 1, K, p)
ans = 0
pow = 1 # (m - 1)^0 mod p
for j in range(K + 1):
    ans = (ans + binomials[K - j] * pow % p) % p
    pow = pow * (M - 1) % p

ans = ans * M * exp_by_sq_p(M - 1, N - K - 1, p) % p

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 998244353
class Combination(object):
	def __init__(self, N, MOD):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1
 
		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % MOD
			self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
			self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    if N == 1:
        print(M)
        return

    Com = Combination(N-1, MOD)
    ans = 0
    for k in reversed(range(K+1)):
        ans += M * pow(M-1, N-k-1, MOD) * Com.com(N-1, k)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


mod = 998244353
comb = combination(mod)
n, m, k = inpl()
ans = 0
for i in range(min(n, k + 1)):
    ans += m * pow(m - 1, n - 1 - i, mod) * comb.calc(n - 1, i) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


mod = 998244353
comb = combination(mod)
n, m, k = inpl()
if m == 1:
    if k >= n - 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
ans = 0
for i in range(min(n, k + 1)):
    ans += m * pow(m - 1, n - 1 - i, mod) * comb.calc(n - 1, i) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod=998244353

class Combination:
	def __init__(self,size):
		self.size = size + 2
		self.fact = [1, 1] + [0] * size
		self.factInv = [1, 1] + [0] * size
		self.inv = [0, 1] + [0] * size
		
		for i in range(2, self.size):
			self.fact[i] = self.fact[i - 1] * i % mod
			self.inv[i] = -self.inv[mod % i] * (mod//i) % mod
			self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod
			
	def npk(self,n,k):
		if n < k or n < 0 or k < 0:
			return 0
		return self.fact[n] * self.factInv[n - k] % mod
		
	def nck(self,n,k):
		if n < k or n < 0 or k < 0:
			return 0
		return self.fact[n] * (self.factInv[k] * self.factInv[n - k] % mod) % mod
		
	def nhk(self,n,k):
		return self.nck(n + k - 1, n - 1)


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

comb=Combination(n+k)
res=0

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

Submission status: Accepted

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

MOD = 998244353
FAC = [1]
INV = [1]
for i in range(1,n+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Submission status: Accepted

Solution code:
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
  N, M, K = map(int, readline().split())
  p = 998244353

  cnt = 0
  c = 1
  for i in range(K+1):
    cnt += c * M * pow(M-1, N-1-i, p)
    cnt %= p
    c *= (N - i - 1) * pow(i+1, p-2, p)
    c %= p
  print(cnt)

if __name__ == '__main__':
  main()

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
#abc167_e
n,m,k = map(int,input().split())

mod = 998244353

ans = 0

#precalculation of the factorial
#fact[i] = i!
num = n
fact = [0] * num
fact[0] = 1
for i in range(1,num):
    fact[i] = (fact[i-1] * i) % mod

    
#precalculation of the (M-1)**i
#M_pow[i] = (M-1)^i
M_pow = [0] * num
M_pow[0] = 1
for i in range(1,num):
    M_pow[i] = (M_pow[i-1] * (m-1)) % mod


for i in range(k+1):
    f = M_pow[n-i-1] * pow(fact[i]*fact[n-i-1], mod-2, mod)
    ans += f % mod

ans *= m * fact[n-1]
print(ans % mod)

Submission status: Accepted

Solution code:
# 二項係数のmod (大量のmod計算が必要なとき)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod

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


ans=0

# 同じ色で塗る組数で場合分け
for i in range(k,-1,-1):
    # 同色の組の色の割り当て
    if i==k:
        v1 = m * pow(m - 1, n - i - 1, mod)
    else:
        v1*=m-1
        v1%=mod
    # グループの分け方
    v2=cmb(n-1,i,mod)
    ans+=v1*v2
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
# 二項係数のmod (大量のmod計算が必要なとき)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod

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


ans=0
# 同じ色で塗る組数で場合分け
for i in range(k+1):
    # 同色の組の色の割り当て
    v1=m*pow(m-1,n-i-1,mod)
    # グループの分け方
    v2=cmb(n-1,i,mod)
    ans+=v1*v2
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353

class mod_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 = mod_combination(n)
ans = 0
for x in range(k + 1):
    ans = (ans + C.calc(n - 1, n - x - 1) * m * pow(m - 1, n - x - 1, mod) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
 
input = sys.stdin.readline
 
def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod
 
mod = 998244353
N, M, K = map(int, input().split())
 
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod #n!を計算
# print('fact:{}'.format(fact))
revfact = [1] * (N + 1) #逆元を定義
revfact[N] = pow(fact[N], mod - 2, mod) #n!のmod-2乗を計算
# print('revfact:{}'.format(revfact))
for i in reversed(range(1, N)): #N-1から1まで
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
# print('revfact:{}'.format(revfact))
 
ans = 0
for k in range(K + 1):
    ans += (M * pow(M - 1, N - 1 - k, mod) * comb(N - 1, k)) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
n, m, k = map(int, input().split())
 
fact = [0]*(n+1)
fact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1]*i % MOD
 
invfact = [0]*(n+1)
for i in range(n+1):
    invfact[i] = pow(fact[i], MOD-2, MOD)
 
 
def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]
 
 
ans = 0
for i in range(k+1):
    ans += m*pow(m-1, n-1-i, MOD)*nCk(n-1, i)
    ans %= MOD
print(ans)

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

Submission status: Accepted

Solution code:
def modpow(a, x, mod):
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2, mod)
    else:
        return (modpow((a * a) % mod, x // 2, mod) * a) % mod


N, M, K = map(int, input().split(' '))
max_K = 3 * 10 ** 5
mod = 998244353

inv = [0 for i in range(max_K + 1)]
inv[0] = 1
inv[1] = 1
for i in range(2, K + 1):
    inv[i] = modpow(i, mod - 2, mod)
choose = [0 for i in range(K + 1)]
choose[0] = 1
for i in range(1, K + 1):
    choose[i] = choose[i - 1] * (((N - i) * inv[i]) % mod)
    choose[i] %= mod

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

##### 進数の変換 #####
# bin_str = bin(i)
# oct_str = oct(i)
# hex_str = hex(i)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,K = inputMap()

	cnv = Combination(N, 998244353)

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

		prn = cnv(N-1, i)

		tmp = (tmp * prn) % 998244353
		ans = (ans + tmp) % 998244353

	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    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

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

MOD = 998244353
MAX = 10 ** 5 * 2 + 5

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

comInit(MOD)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, k = map(int, readline().split())

ans = 0
col = m
for x in range(n - 1, -1, -1):
    now = col
    now *= com(n - 1, x, MOD) % MOD
    if x <= k:
        ans += now
    col = (col * (m - 1)) % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

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

fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod #n!を計算
# print('fact:{}'.format(fact))
revfact = [1] * (N + 1) #逆元を定義
revfact[N] = pow(fact[N], mod - 2, mod) #n!のmod-2乗を計算
# print('revfact:{}'.format(revfact))
for i in reversed(range(1, N)): #N-1から1まで
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
# print('revfact:{}'.format(revfact))

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