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

MOD = 998244353
N = 3 * 10**5

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

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

print(ans)

Submission status: Accepted

Solution code:
class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

n,m,k = map(int, input().split())
if n==1:
    print(m)
    exit()

mod = 998244353

PCM = PERM_COMB_MOD(n+10, mod)

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

print(ans)

Submission status: Accepted

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


factorial = [1]
inverse = [1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))

def comb(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

## inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

## nCkをmodしつつ返す
def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

N,M,K = LI()

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

fl = fact_all(N)
il = fact_inv_all(fl)

ans = 0
for j in range(K+1):
    ans += nCk(N-1,j,fl,il)*Ma[N-1-j]*M
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,k = map(int,input().split())
class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討
A = pow(m,n,mod) 
count = 0
for i in range(n-k-1,0,-1):
  count += invt.cmb(n-1,i-1) * m * pow(m-1,i-1,mod)
  count %= mod
# print(count)
print((A-count) % mod)




# B = pow(m,n,mod) * invt.fac[n-k] % mod
# C = pow(m,n-k,mod)
# print((A-C)%mod)
# print(pow(m,n,mod) * invt.fac[n-k] % mod)

Submission status: Accepted

Solution code:
from collections import Counter

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

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i % MOD)
inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

ans = 0
for j in range(K + 1):
    ans += (
        pow(M - 1, N - 1 - j, MOD)
        * factorial[N - 1]
        * inv_factorial[j]
        * inv_factorial[N - 1 - j]
        % MOD
    )
    if ans >= MOD:
        ans -= MOD
ans = ans * M % MOD
print(ans)

Submission status: Accepted

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

ans = pow(M, N, MOD)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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


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

print(ans)

Submission status: Accepted

Solution code:
X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - K - 1, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
#	print(m)
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
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

N, M, K = MAP()

lim = 2*10**5+10  # 必要そうな階乗の限界を入れる
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = (fact[n-1] * n) % mod
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

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

list_size = 10**5*5   # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

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

def comb(n,r):
    if n < r:
        return 0
    if n == 0 or r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD


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

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

ans = 0
for i in range(K+1):
    ans += (X[N-i-1] * comb(N-1,i)) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353


def pow(a, b):
	if b == 0:
		return 1

	if (b % 2) == 0:
		x = pow(a, b // 2) % MOD
		return x * x % MOD
	else: 
		return a * pow(a, b - 1) % MOD

def inverse(x):
	return pow(x, MOD - 2)

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

result = 0

bin_coeff = 1

for k in range(K + 1):
	incr = (((bin_coeff * m % MOD)) % MOD) * pow(m - 1, n - k - 1) % MOD
	#print(incr, bin_coeff)
	result = (result + incr)  % MOD
	bin_coeff = ((bin_coeff * (n - k - 1) % MOD) * inverse(k + 1)) % MOD

print(result)

Submission status: Accepted

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

N = n + 5
bikkuri = [0 for i in range(N)]
bikkuri[0] = 1
gyaku = [0 for i in range(N)]
gyaku[0] = 1
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
    gyaku[i] = pow(bikkuri[i], mod - 2, mod)


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    if r == 0 or n - r == 0:
        return 1
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0

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

Submission status: Accepted

Solution code:
nn = 200200
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
    exit()
ans = 0
t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
for i in range(K+1):
    ans = (ans + t * C(N-1, i)) % P
    t = t * m % P
print(ans * M % P)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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


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



def main():
    N, M, K = [int(x) for x in input().split()]

    MOD = 998244353

    global fact, factinv, inv
    for i in range(2, 10 ** 6 + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)


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

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def make_table(n, mod = MOD):
    # 元テーブル
    g1 = [0] * (n + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (n + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元計算用テーブル
    inverse = [0] * (n + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return tuple(g1), tuple(g2), tuple(inverse)

g1, g2, inverse = make_table(N)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 998244353
INF = 10 ** 18
SIZE = 10 ** 6

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

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

Submission status: Accepted

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

MAX = 2 * 10 ** 5 + 10

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

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

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


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


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

print(ans)

Submission status: Accepted

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

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

def chng2(n): #10進数nを2進数に変換(配列)
    ans = list(bin(n))
    return ans

def pwr(n,k): #nのk乗高速版 n^k
    memo = chng2(k)
    lng = len(memo)

    li = [0 for i in range(lng-1)]
    li[0] = 1
    
    a = n
    ans = 1
    for i in range(1,lng-1):
        li[i] = a%p
        a *= a
        a %= p
 
    for i in range(1,lng-1):
        if memo[-i]=='1':
            ans *= li[i]
            ans %= p

    return ans



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

ans = 0
for k in range(K+1):
    memo1 = cmb(N-1,k,p)
    memo2 = pwr(M-1,N-k-1)*M
    ans += memo1*memo2
    ans %= p
    # print(k,memo1,memo2)
# print((100*(99**99))%p)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
INF=998244353
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
if m==1:
    if k==n-1:
        print(m)
    else:
        print(0)
    sys.exit()
for i in range(k+1):
    if i==0:
        c=1
        temp=(m*pow(m-1,n-1))%INF
    else:
        x=modinv(i,INF)
        c=(c*x*(n-i))%INF
        temp=(temp*modinv(m-1,INF))%INF
    ans=(ans+c*temp)%INF
print(ans)

Submission status: Accepted

Solution code:
#code
p=998244353
N,M,K=map(int,input().split())
power=[0 for i in range(N)]
power[0]=1
for i in range(1,N):
    power[i]=(power[i-1]*(M-1))%p
ans=M*power[N-1]
ans%=p
pre_compute=[0 for i in range(K+1)]
num = den = 1
for i in range(1,K+1):
    num*=(N-i)
    den*=i
    num%=p
    den%=p
    pre_compute[i]=(num * pow(den, p - 2, p)) % p 
for i in range(1,K+1):
    ans+=M*power[N-1-i]*pre_compute[i]
    ans%=p
print(ans)

Submission status: Accepted

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

memo = [0]*n


def com(n, r):
    if n < r or r < 0:
        return 0
    if n-r < r:
        r = n-r
    if r == 0:
        memo[r] = 1
        return memo[r]
    if memo[r] != 0:
        return memo[r]
    X = Y = 1
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
        memo[i] = X*pow(Y, MOD-2, MOD)
    return memo[r]


com(n-1, n//2)

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

Submission status: Accepted

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

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

ans = 0
for k in range(K+1):
    tmp = factorials[N-1]
    tmp *= fact_invs[k]
    tmp %= MOD
    tmp *= fact_invs[N-1-k]
    tmp %= MOD
    tmp *= M * pow(M-1, N-1-k, MOD)
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, M, K = map(int, input().split())
    mod = 998244353
    dp = [1]*(K+1)
    for i in range(1,K+1):
        dp[i] = dp[i-1]*(N-i)*pow(i,mod-2,mod)%mod
    ans = 0
    for i in range(K+1):
        ans += dp[i]*M*pow(M-1,N-1-i,mod)
        ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m,k = map(int, input().split())
mod = 998244353
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n)]
combi[0] = 1
for i in range(1,n):
    combi[i] = (combi[i-1]*(n-i)*mod_inv(i,mod)) % mod
for i in range(k+1):
    plus = m * pow(m-1,n-1-i,mod)
    plus *= combi[n-i-1]
    plus %= mod
    ans += plus
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

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

N = 10**5*2+100
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans=m*pow(m-1,n-1,mod)
ans%=mod
# print(ans)
for i in range(k):
    tmp=cmb(n-1,i+1)*m*pow(m-1,n-(i+2),mod)
    # print(cmb(n-1,i+1),m,pow(m-1,n-(i+1),mod))
    # print(tmp)
    tmp%=mod
    ans+=tmp
    ans%=mod
    # print(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

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

#mod = 10**9+7 #出力の制限
N = n+3
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 )

# a = cmb(n,r,mod)

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

Submission status: Accepted

Solution code:
MOD = 998244353
def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    fu = FactorialUtils(N)
    ans = Mint()
    for i in range(K + 1):
        tmp = Mint(1)
        tmp *= fu.choose(N - 1, i)
        tmp *= M
        tmp *= pow(M - 1, N - 1 - i, MOD)
        ans += tmp
    print(ans)

class FactorialUtils:
    def __init__(self, n, mod=MOD):
        self.__mod = mod
        self.fac = [1] * (n + 1)
        self.ifac = [1] * (n + 1)
        for i in range(2, n + 1): self.fac[i] = self.fac[i - 1] * i % mod
        self.ifac[n] = pow(self.fac[n], mod - 2, mod)
        for i in range(n, 1, -1): self.ifac[i - 1] = self.ifac[i] * i % mod

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n - r] % self.__mod) * self.ifac[r] % self.__mod

    def multichoose(self, u, k):
        return (self.fac[u + k - 1] * self.ifac[u - 1] % self.__mod) * self.ifac[k] % self.__mod

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()

Submission status: Accepted

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

fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)

def combination(n,fact,ifact):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[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
        ifact[i] = (ifact[i-1]*inv[i])%MOD
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%MOD
combination(N,fact,ifact)

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

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
ans = 0
now = m
c = 1
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
for i in range(n):
    if n-i-1 <= k:
        ans += now*c
        ans %= mod
    now *= (m-1)
    now %= mod
    c = c*(n-1-i)%mod
    c = c*mod_inv(i+1,mod)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

        self.fac[0], self.fac[1] = 1, 1
        self.finv[0], self.finv[1] = 1, 1
        self.inv[1] = 1

        for i in range(2, max_num):
            self.fac[i] = self.fac[i-1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

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


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


n, m, k = map(int, input().split())
com = Combination(998244353, 510000)
all_ptn = modpow(m, n, 998244353)
exct_ptn = 0

for i in range(k+1, n):
    cnt = com.calc(n-1, i) * m * modpow(m - 1, n - 1 - i, 998244353)
    exct_ptn += cnt
    exct_ptn %= 998244353

ret = all_ptn - exct_ptn
if ret < 0:
    ret += 998244353

print(ret)

Submission status: Accepted

Solution code:
F = 2*10**5+5
mod = 998244353
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

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

ans=0

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

Submission status: Accepted

Solution code:
import sys
mod = 998244353
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

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

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

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 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())
r = 0
for i in range(K+1):
    r += (cmb(N-1, i) * M * pow(M-1, N-i-1, mod)) % mod
    r %= mod
print(r)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
m=998244353
max_n=4*10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
a=0
for i in range(K+1):
    a=(a+M*pow(M-1,N-1-i,m)*comb(N-1,N-i-1))%m
print(a)

Submission status: Accepted

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

num = 200010
fact = [1] * (num+1)
ifact = [1] * (num+1)
inv = [pow(i,MOD-2,MOD) for i in range(num+1)]
for i in range(1,num+1):
    fact[i] = (fact[i-1] * i) % MOD
    ifact[i] = (ifact[i-1] * inv[i]) % MOD

def nCr(n,r):
    return (fact[n] * ifact[r] * ifact[n-r]) % MOD

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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
MOD = 998244353
n = N
fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % MOD
            p //= 2
        else:
            res = res * n % MOD
            p -= 1
    return res % MOD


for i in range(1, n):
    fac.append((fac[i - 1] * i) % MOD)
    caf.append(pow(fac[i], MOD - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return fac[n] * caf[r] * caf[n - r]


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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
MOD = 998244353
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)

comb = [M] * (K + 1)
for i in range(1, K + 1):
    comb[i] = comb[i - 1] * (N - i) % MOD
    comb[i] = comb[i] * modinv(i) % MOD

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

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 998244353
def factrial(N):
    fc = [1, 1] + [None] * N
    inv = [0, 1] + [None] * N
    fcInv = [1, 1] + [None] * N
    for i in range(2, N+1):
        fc[i] = i*fc[i-1]%mod
        inv[i] = mod-(inv[mod%i]*(mod//i))%mod
        fcInv[i] = fcInv[i-1]*inv[i]%mod
    return fc, fcInv

def modCom(n, k):
    return 0 if n < k else fc[n] * fcInv[k] * fcInv[n-k] % mod

N, M, K = map(int, input().split())
fc, fcInv = factrial(N+1)
ans, C = 0, 0
for k in range(K+1):
    C = modCom(N-1, k)
    C %= mod
    ans += C * M * pow(M-1, N-k-1, mod)
    # print(ans)
    ans %= mod
print(ans)