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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=998244353):
        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 = inpl()
conb = Combination(300010)
res = 0
for i in range(k+1):
    x = n - i - 1
    res += conb(n-1,x) * m * pow(m-1,x,mod)
    res %= mod
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
#mod = 10**9 + 7
mod = 998244353

N, M, K = rl()

class CombMod:
	def __init__(self, N):
		self.fact = [1]
		self.rfact = [1]
		for i in range(1, N+1):
			self.fact.append(self.fact[i-1]*i % mod)
			self.rfact.append(pow(self.fact[i], mod-2, mod))

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

cm = CombMod(N-1)

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

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
ans=0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(cmb((n-1),(n-kk),mod))%mod
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

# Combination under a modulo: nCk % mod
# Modulo must be a prime number.
# Intermediate numerators and denominators are cached and reused.
def combmod(n, k, p=MOD, cache=collections.defaultdict(lambda: [(1, 1)])):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    # Reuse precalculated numerators and denominators.
    numden = cache[n]
    if k < len(numden):
        num, den = numden[k]
    else:
        # Resume from len(numden).
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % p
            den = den * (i + 1) % p
            numden.append((num, den))
    # a^(p-1) ≡ 1 mod p (by Fermat's little theorem)
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


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


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

Submission status: Accepted

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

    fac, finv, inv = COMinit(N+1,MOD)

    ans = 0
    for i in range(K+1):
        ans += M % MOD * pow(M-1,N-1-i,MOD) % MOD * COM(N-1,i,MOD,fac,finv,inv) % MOD
    
    print(ans%MOD)

# COMの前処理
# テーブルを作る
# O(n)
def COMinit(N, mod):
    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

    for i in range(2, 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
    
    return fac, finv, inv

# nCrを計算 前処理としてCOMinitの実行が必要
# O(1)
def COM(n, r, mod, fac, finv, inv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

fact = [ 1, 1 ]       # fact[k] = k!
inv = [ 0, 1 ]        # inv[k] = k^(-1)
fact_inv = [ 1, 1 ]   # fact_inv[k] = (k!)^(-1)
powm_1 = [ 1, m-1 ]
for a in range( 2, 2 * ( 10 ** 5 ) + 1 ):
    fact.append( a * fact[-1] % p )
    inv.append( - inv[p%a] * (p//a) % p )
    fact_inv.append( fact_inv[-1] * inv[a] % p )
    powm_1.append( powm_1[-1] * (m-1) % p )

ans = 0
for i in range( k + 1 ):
    ans = ( ans + m * powm_1[n-1-i] * fact[n-1] * fact_inv[n-1-i] * fact_inv[i] ) % p

print( ans )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

# Combination under a modulo: nCk % mod
# Modulo must be a prime number.
# Intermediate numerators and denominators are cached and reused.
def combmod(n, k, p=MOD, numden=[(1, 1)]):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    # Reuse precalculated numerators and denominators.
    if k < len(numden):
        num, den = numden[k]
    else:
        # Resume from len(numden).
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % p
            den = den * (i + 1) % p
            numden.append((num, den))
    # a^(p-1) ≡ 1 mod p (by Fermat's little theorem)
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


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


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

Submission status: Accepted

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

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-1,MOD))%MOD
for x in range(k,-1,-1):
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
    s*=(m-1)
    s%=MOD
print(ans)

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[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))
# fac[n] = n! mod in o(n)

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353
numden = [(1, 1)]

# Combination under a prime modulo: nCk % mod
def combmod(n, k, mod=MOD):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    # Reuse precalculated numerators and denominators.
    if k < len(numden):
        num, den = numden[k]
    else:
        # Resume from len(numden).
        num, den = numden[-1]
        for i in range(len(numden) - 1, k):
            num = num * (n - i) % mod
            den = den * (i + 1) % mod
            numden.append((num, den))
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, mod - 2, mod)
    return num * inv_dev % mod


def solve():
    ans = 0
    for i in range(K + 1):
        cs = combmod(N - 1, i)
        ans += cs * M % MOD * pow(M - 1, N - 1 - i, MOD) % MOD
        ans %= MOD
    return ans


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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 998244353

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class Combination:
    def __init__(self, max_n=100007, mod=mod):
        self.mod = mod
        self.fac = [0] * max_n
        self.finv = [0] * max_n
        self.inv = [0] * max_n

        self.fac[0] = 1
        self.fac[1] = 1
        self.finv[0] = 1
        self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, max_n):
            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 choose(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(n, p, m):
    if p == 0:
        return 1
    if p % 2 == 0:
        t = modpow(n, p // 2, m)
        return t * t % m
    return n * modpow(n, p - 1, m) % m

n, m, k = na()
C = Combination(10 ** 5 * 4)
ans = 0
for i in range(k + 1):
    ans += C.choose(n - 1, i) * m % mod * modpow(m - 1, n - i - 1, mod) % mod

print(ans % mod)

Submission status: Accepted

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

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k:
        return 0
    return fac[n] * finv[n - k] * finv[k]

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

Submission status: Accepted

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

comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p

print(res)

Submission status: Accepted

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

c = 1

for k in range(K+1):
  out += M * pow(M-1, N-k-1, mod) * c
  out %= mod
  c *= (N-k-1) * pow(k+1, mod-2, mod)
  c %= mod
print(out)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


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

Submission status: Accepted

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

n, m, k = map(int, input().split())
mod = 998244353
c = Combination(n)

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

print(ans)

Submission status: Accepted

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

MOD = 998244353
# 組み合わせ②-1
# nCk % MOD
# n巨大で固定、kは10 ** 5くらいまで
# 前処理O(MAX)、計算O(1)
NN = N-1
MAX = K + 1
com = [0] * MAX
def COM2init():
    com[0] = 1
    for i in range(1, MAX):
        if i > NN: break
        com[i] = (com[i-1] * (NN-i+1) % MOD) * pow(i, MOD-2, MOD) % MOD
COM2init()

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

Submission status: Accepted

Solution code:
def cmb(n,r,p):
    if r<0 or r>n:
        return 0
    r = min(r,n-r)
    return fact[n] * factinv[r] *factinv[n-r] % p
p =  998244353
N = 2*(10**5)+1

fact=[1,1] #fact[n] = (n! modp)
factinv = [1,1] #factinv[n] = ((n!)^(-1) modp)
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[i]) %p)


    

n,m,k = map(int,input().split())
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 += (((cmb(n-1,n-x-1,p) * m) %p)*beki[n-x-1]) %p
    ans = ans % p
print(ans)

Submission status: Accepted

Solution code:
import math
N,M,K=map(int,input().split())
mod=998244353
ans=0
d=[1]+[1]
e=[0]+[1]
f=[0]+[1]

for i in range(2,N+1):
  d += [d[i-1]*i%mod]
  e += [ e[mod % i] * (mod - int(mod / i)) % mod]
  f += [ f[i-1]*e[i]%mod]
def combinations_count(n, r):
  if r==n or r==0:
    return 1
  return d[n] * f[n-r] * f[r]%mod

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

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353
class Combination:
    def __init__(self, N=5*10**5, mod=MOD):
        self.mod = mod
        self.N = N
        self.fact = [1, 1]  # fact[n] = (n! mod p)
        self.factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
        self.inv = [0, 1]  # factinv 計算用
        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)
    def nCr(self, n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n-r] % self.mod

comb = Combination(2 * 10**5)
ans = 0
for i in range(k+1):
    ans += m * pow(m-1, n-1-i, MOD) * comb.nCr(n-1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

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

if m == 1 and n-1 == k:
    print(1)
    sys.exit()



kai = [1]*(n+1)
inv = [1]*(n+1)
for i in range(n):
    kai[i+1] = (kai[i] * (i+1))%mod
    inv[i+1] = (inv[i] * pow(i+1,mod-2,mod))%mod

count_all = 0
pre_pow = pow(m-1,n-1,mod)
inv_m_mai1 = pow(m-1,mod-2,mod)
for i in range(k+1):
    pattern_color = m*pre_pow%mod
    pattern_place = kai[n-1]*inv[n-1-i]*inv[i]%mod
    count_all = (count_all+pattern_color*pattern_place)%mod
    pre_pow = pre_pow * inv_m_mai1 %mod

print(count_all)

Submission status: Accepted

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

p = 998244353

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

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

for i in range(2, n+1):
    fact.append(fact[-1]*i%p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1]*inv[i])%p)
ans = 0

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

Submission status: Accepted

Solution code:
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,m,k=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

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

print(ans%mod)

Submission status: Accepted

Solution code:
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,m,k=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

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

print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


# 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
# 参考：http://www.tbasic.org/reference/old/ExEuclid.html
def extGCD(x, y):
    r = [1, 0, x]
    w = [0, 1, y]

    while w[2] != 1:
        q = r[2] // w[2]
        w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
        r, w = w, w_tmp

    return w[:2]


# 階乗の逆元は(x!)^(-1) * x=((x-1)!)^(-1)を利用する。
# 1 / a mod m を求める。
def mod_inv(a, m):
    x, _ = extGCD(a, m)
    return (x + m) % m


def main():
    MOD = 998244353

    N, M, K = inpl()
    m1 = {}
    m1[0] = 1
    n_comb = {}
    n_comb[0] = 1
    for i in range(1, N + 1):
        m1[i] = (m1[i - 1] * (M - 1)) % MOD
        n_comb[i] = (n_comb[i - 1] * mod_inv(i, MOD) * (N - i)) % MOD

    ans = 0
    for i in range(K + 1):
        ans = (ans + M * n_comb[i] * m1[N - 1 - i]) % MOD

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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 nCk(n,k): # 組み合わせ(MOD)を返却する
    return fact[n] * factinv[n-k] * factinv[k] % MOD

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

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

Submission status: Accepted

Solution code:
MOD = 998244353


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


def make_tables(N):
    fac = [1, 1]
    inv = [1, 1]
    for i in range(2, N + 1):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(modinv(fac[i]))
    return fac, inv


def ncr(n, r):
    return int(fac[n] * inv[r] * inv[n - r]) % MOD


if __name__ == '__main__':

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

    fac, inv = make_tables(N)

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

    print(ans % MOD)

Submission status: Accepted

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

framod=[0]*(2*10**5+1)
framod[0]=1
def xframod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
        framod[i]=a
xframod(2*10**5,mod)

def combmod(n, k, mod):
    a=framod[n]
    b=framod[k]
    c=framod[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
ans=0

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

Submission status: Accepted

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

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

for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

x = m%mod

a = pow(m-1,n-1,mod)
x = (a*x)%mod

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

Submission status: Accepted

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

MOD =  998244353
mod = MOD
MAX = N+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2,MAX):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

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




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

# ans -= minus 
# ans = (ans+MOD)%MOD
# print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math

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

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

p = 998244353
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

Submission status: Accepted

Solution code:
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
size = 2*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 2):
    next = C[-1] * (N-i) * pow(i, mod-2, mod)
    C.append(next % mod)

res = 0

for x in range(K+1):
    crt =  (pow(M-1, N-x-1, mod) * M) % mod 
    crt %= mod
    #print("start")
    idx = min(x, N-1-x)
    crt *= C[idx]
    #print("end")
    crt %= mod
    res += crt
    res %= mod

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
def modpow(x, y, mod):
    ret = 1
    z = x
    n = len(bin(y)) - 2
    for i in range(n):
        if ((y >> i) & 1):
            ret = ret * z % mod
        z = z * z % mod
    return ret

def modinv(x, mod):
    return modpow(x, mod-2, mod)

def main():
    n, m, k = map(int, input().split())
    mod = 998244353

    c1 = 1
    c2 = 1
    for i in range(1, n):
        c1 = c1 * i % mod
        if i == k:
            c2 = modinv(c1, mod)
    c3 = modinv(c1, mod)
    c3_list = [0] * (k+1)
    c3_list[k] = c3
    for i in range(k-1, -1, -1):
        c3 = c3 * (n-(k-i)) % mod
        c3_list[i] = c3
    comb = (c1 * c2 % mod) * c3_list[0] % mod

    x = m * modpow(m-1, n-k-1, mod) % mod

    ret = x * comb % mod

    for i in range(1, k+1):
        c2 =c2 * (k-i+1) % mod
        comb = (c1 * c2 % mod) * c3_list[i] % mod
        x = x * (m-1) % mod

        ret += x * comb % mod
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

f = [(1,1), ]

def ncr(n,r,p):
    num = (f[-1][0] * (n-(r-1))) % p
    den = (f[-1][1] * ((r-1) + 1)) % p
    f.append([num, den])
    return (num * pow(den, p-2, p)) % p

n,m,k = (int(x) for x in input().split())
p = 998244353
ans = 0

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

Submission status: Accepted

Solution code:
N, M, K = list(map(int, input().split()))
p = 998244353
comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p
print(res)

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)
def run():
    N,M,K = map(int, input().split())
    mod = 998244353
    modM = [1]
    for x in range(1,N):
        val = modM[-1] * (M-1)
        val %= mod
        modM.append(val)

    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        if n < 2:
            return ret[:n+1]

        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(N-1, mod)

    combs = []
    def comb_mod(n, a, mod):
        """
        return: [n, a] % mod
        Note: mod must be a prime number
        """
        combs.append(1)
        ret = 1
        for i in range(1, a+1):
            ret *= n-i+1
            ret %= mod
            ret *= inv[i]
            ret %= mod
            combs.append(ret)
        return None
    comb_mod(N-1, N-1, mod)


    ret = 0
    for k in range(K+1):
        tmp = (modM[N-1-k] * M) % mod
        tmp *= combs[k]
        tmp %= mod
        ret += tmp
        ret %= mod
    print(ret%mod)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
mod = 998244353

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

frac = [0] * (n + 1)
frac[0] = frac[1] = 1

for i in range(1, n):
    frac[i + 1] = frac[i] * (i + 1)
    frac[i + 1] %= mod

inv_frac = [0] * (n + 1)
inv_frac[n] = pow(frac[n], mod - 2, mod)

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

ans = 0

for i in range(k + 1):
    ans += m * pow(m - 1, n - 1 - i,
                   mod) * frac[n - 1] * inv_frac[i] * inv_frac[n - 1 - i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=998244353):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    # テーブルを作成し、K回使いまわす
    fac, finv = COMinit(N-1, MOD)
    m_mod = [1]
    for _ in range(N):
        m_mod.append(m_mod[-1] * (M - 1) % MOD)

    ans = 0
    for k in range(K+1):
        cmb = Combination(N-1, k)
        ans += (M%MOD) * (m_mod[N-k-1]%MOD) * cmb
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    resolve()