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: Time Limit Exceeded

Solution code:


def diff_colors(x, m, modp):
    """
    長さxの列をm色で塗る
    このとき、連続して同じ色を使わないパターン数を数える
    """
    ans = m
    x -= 1
    while x:
        ans *= (m - 1)
        ans %= modp
        x -= 1
    return ans

def factorial(x, modp):
    fact = dict()
    fact[0] = 1
    curr = 1
    while curr <= 2 * x:
        fact[curr] = fact[curr - 1] * curr
        fact[curr] %= modp
        curr += 1
    return fact


def pow(x, k, modp):
    ans = 1
    while k:
        if k % 2:
            ans *= x
            ans %= modp
        x *= x
        x %= modp
        k //= 2
    return ans


def combi(fact, n, k, modp):
    ans = fact[n + k - 1]
    ans *= pow(fact[k], modp - 2, modp)
    ans %= modp
    ans *= pow(fact[n - 1], modp - 2, modp)
    ans %= modp
    return ans


def submit():
    n, m, k = map(int, input().split())
    modp = 998244353
    fact = factorial(n, modp)

    ans = 0
    base_pattern = diff_colors(n - k, m, modp)
    for i in range(k + 1):
        ans += base_pattern * combi(fact, n - (k - i), k - i, modp)
        ans %= modp
        base_pattern *= (m - 1)
        base_pattern %= modp

    print(ans)
    

if __name__ == "__main__":
    submit()

Submission status: Time Limit Exceeded

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

s = (m-1) ** (n-1)
c = 1
for i in range(1, k + 1):
  c = c * (n-i) // i
  s += (m-1) ** (n-1-i) * c % MOD

s = s* m % MOD
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
#n=int(input())
n,m,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]



a=0
for i in range(n-k,n+1):
    a+=m*((m-1)**(i-1))*math.factorial(n-1)//math.factorial(i-1)//math.factorial(n-i) #comb(n-1,n-i)
    a=a%998244353
print(a%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map (int,input().split())
def comb(n, r, mod):
  a = 1
  b = 1
  r = min(r, n - r)
  for i in range(r):
    a = a * (n - i) % mod
    b = b * (i + 1) % mod
  return a * pow(b, mod - 2, mod) % mod
mod = 998244353
ans = 0
for i in range(k+1):

    ans += (comb (n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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

def print2Num(x,y):
	print(str(x) + " " + str(y))

MOD = 998244353
def cmb_mod(n,r,mod = MOD):
    x=1
    y=1
    if n/2<r:
        r=n-r
    for i in range(r):
        x*=n-i
        if x>mod:
            x%=mod
        y*=r-i
        if y>mod:
            y%=mod
    val=x*pow(y,mod-2,mod)%mod
    return val


N, M, K = input_multiple_number()



ans = M
summation = 0

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

print(ans*summation%MOD)

Submission status: Time Limit Exceeded

Solution code:
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod

def cmb(n, r, MOD):
    if n < r:
        return 0
    if n-r < r:
        r = n-r
    comb = 1
    for x in range(n-r+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, r+1):
        d = (d * x) % MOD
    comb *= powmod(d, MOD-2, MOD)
    return comb % MOD


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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

# def comb(n,r):
#     return(factorial(n) // (factorial(n-r) * factorial(r)))

def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


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

s = 0

for x in range(k+1):
    s += m * (power_func(m-1,n-1-x,998244353)% 998244353) * (cmb(n-1,x,998244353) % 998244353)
    s %= 998244353
print(s)

Submission status: Time Limit Exceeded

Solution code:

import math
import sys
sys.setrecursionlimit(999999999)

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

jo = 998244353

memo = {}
def calc(n,m,k):
	if k < 0: return 0
	if n == 1: return m%998244353
	key = (n,k)
	if key not in memo:
		raw_ans = calc(n-1,m,k-1) + (m-1)*calc(n-1,m,k)
		ans = raw_ans % jo
		memo[key] = ans
	return memo[key]

n0,m0,k0 = input_num()
ans = calc(n0,m0,k0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
# tmp = m
mod = 998244353
ans = m * pow(m-1, n-1, mod)
ans %= mod
ncm = 1
for i in range(k):
    ncm *= n-1-i
    ncm *= pow(i+1, mod-2, mod)
    ans += m * pow(m-1, n-i-2, mod) * ncm
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
MAXN = 2*(10**5)+10
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod


N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
    tmp = pow(M-1, N-i-1, MOD) * M % MOD
    tmp *= nCr(N-1,i,MOD)
    ans += tmp % MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

mod = 998244353

n, m, k = [int(x) for x in input().split()]

def make_tables(n, mod = 998244353):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

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

def nCk(n, k, mod = 998244353):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

fac, finv = make_tables(n)
cal = m
ans = 0
for i in range(n - 1 - k):
    cal *= m - 1
    cal %= mod
ans += cal * nCk(n - 1, k)
ans %= mod
for i in range(1, k + 1):
    cal *= (m - 1)
    ans += cal * nCk(n - 1, k - i)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, power(b, mod-2, mod), mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

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

powers = [0] * n
a = m
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
comb = 1
kk = 0
a = n - kk
c += powers[a - 1] * comb

for kk in range(1, k + 1):
    a = n - kk
    comb = (div(comb,  kk, mod) * (a))%mod
    c = c + powers[a - 1] * comb
    c = c%mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
def cmb(a, b, m=998244353):
    if (b > a - b):
        return cmb(a, a - b, m)
    c = d = 1
    for i in range(b):
        c *= (a - i)
        d *= (b - i)
        c %= m
        d %= m
    return c * pow(d, m - 2, m) % m


def resolve():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    for i in range(k + 1):
        ans += cmb(n - 1, i) * pow(m - 1, n - i - 1, mod)
    ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  answer=M*ans%MOD
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

mod = 998244353

def nCr(N,a):
    if a == 0:
        return 1
    num = reduce(lambda x,y:x * y % mod,range(N,N-a,-1))
    den = reduce(lambda x,y:x * y % mod,range(1,a+1))
    return num * pow(den,mod-2,mod)%mod

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

Submission status: Time Limit Exceeded

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  term1=powmod(M-1,N-1)
  inv_M1=invmod(M-1)
  term2=1
  ans_k=M
  for i in range(K+1):
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

mod = 998244353

def nCr(N,a):
    if a == 0:
        return 1
    num = reduce(lambda x,y:x * y % mod,range(N,N-a,-1))
    den = reduce(lambda x,y:x * y % mod,range(1,a+1))
    return num * pow(den,mod-2,mod)%mod

n,m,k = map(int,input().split())
ans = 0
nu = [1]
for i in range(n-1):
    nu.append((nu[-1]*(m-1))%mod)
for i in range(k+1):
    ans += (nu[-(i+1)]*nCr(n-1,i))% mod
print((m * ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
POWER = []
cur = 1#Nc0
for k in range(K+1):
    NcK.append(cur % MOD)
    cur *= (N-1-k)
    if k==K:break
    cur //= (k+1)    
curpower = 1
for n in range(N):#M-1 ** n
   POWER.append(curpower)
   curpower *= M-1
   curpower %= MOD

ans = 0

for k in range(K+1):
    ans += M * POWER[N-1-k] * NcK[k]
    #M-1 ** N-1-k ということは…？
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
String = input()
list1 = String.split(" ")
n = int(list1[0])
m = int(list1[1])
k = int(list1[2])
lis = [0]*n
result = 0

while lis[n-1] < m:
    judge = 0
    for a in range(n-1):
        if lis[a] == lis[a+1]:
            judge += 1
    if judge <= k:
        result += 1
    lis[0] += 1
    for b in range(n -1):
        if lis[b] == m:
            lis[b] = 0
            lis[b+1] += 1
print(result)

Submission status: Time Limit Exceeded

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  term1=powmod(M-1,N-1)
  inv_M1=invmod(M-1)
  term2=1
  ans_k=M
  for i in range(K+1):
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  print(answer)

Submission status: Time Limit Exceeded

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 = {}
#c = 1
#for i in range(N - M, N):
#	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
	return (c * 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: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

count = 0
for i in range(k+1):
    count_tmp = 0
    count_tmp = m*((m-1)**(n-1-i))
    count_tmp *= combinations_count(n-1,i)
    count += count_tmp

print(count%998244353)

Submission status: Time Limit Exceeded

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  term2=1
  for i in range(K+1):
    ans_k=M
    term1=powmod(M-1,N-i-1)
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
cur = 1#Nc0
for k in range(K+1):
    NcK.append(cur)
    cur *= (N-1-k)
    if k==K:break
    cur //= (k+1)    

ans = 0
def power_func(a,n,p):#a**n mod P
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
for k in range(K+1):
    ans += M * power_func(M-1,N-1-k,MOD) * NcK[k]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, power(b, mod-2, mod), mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

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

powers = [0] * n
a = 1
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
for kk in range(k + 1):
    if kk != 0:
        comb = (div(comb,  kk, mod) * (n - kk))%mod
    else:
        comb = 1
    c += m * powers[n - kk - 1] * comb
    c = c%mod
print(c)

Submission status: Time Limit Exceeded

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

fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % 998244353

def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

result = 0
for i in range(K + 1):
    result += M * mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
print(result)

Submission status: Time Limit Exceeded

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  for i in range(K+1):
    ans_k=M
    term1=powmod(M-1,N-i-1)
    term2=comb_mod(N-1,i)
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    
  print(answer)

Submission status: Time Limit Exceeded

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)

def C(n, m):
	c = 1
	for i in range(n - m + 1, n + 1):
		c = (c * i) % X
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
	return (c * 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: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


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


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)

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

    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def c(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

n,m,k = [int(i) for i in input().split()]
md  = 998244353
ans = 0
for i in range(k+1):
   cmb = c(n-1,i) * m * ((m-1)**(n-i-1))
   cmb %= md
   ans += cmb
   ans %= md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def main():
    n,m,k = getList()
    dp = [m]
    # dp[0] = m
    for i in range(n-1):
        tmp = [0 for _ in range(min(i+2, k+1))]
        for j, d in enumerate(dp):
            # print(tmp, j)
            # print(dp)
            tmp[j] += d * (m-1)
            if j < k:
                tmp[j+1] += d
                tmp[j+1] = tmp[j+1] % MOD
            # print("   ", tmp)
        dp = tmp
        # print(dp)

    ans = 0
    for d in dp:
        ans += d
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    for i in range(K + 1):
        if i > 0:
            m = m * (N - i) // i
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())

Submission status: Accepted

Solution code:
# https://kmjp.hatenablog.jp/entry/2020/05/10/0900
# 数学的な問題


mod = 998244353

class COM:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
        self.fac = [0] * (n+1)
        self.finv = [0] * (n+1)
        self.inv = [0] * (n+1)
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, n+1):
            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, k):
        if k < 0:
            return 0
        return self.fac[self.n] * (self.finv[k] * self.finv[self.n-k] % self.MOD) % self.MOD

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

    # 隣り合う組がK以下のパターンを総当たりして解く
    if N > 1:
        cmbclass = COM(N-1, mod)
        cmb = cmbclass.calc
    else:
        cmb = lambda x:1
    res = 0
    for i in range(K+1):
        res += M * cmb(i) % mod * pow(M-1, N-i-1, mod)


    print(res % mod) 


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

# sys.setrecursionlimit(10000001)
INF = 10 ** 16
# MOD = 10 ** 9 + 7
MOD = 998244353


def ni(): return int(sys.stdin.readline())
def ns(): return map(int, sys.stdin.readline().split())
def na(): return list(map(int, sys.stdin.readline().split()))


# ===CODE===

class ModCombination:
    # https://atcoder.jp/contests/abc167/submissions/13058694
    # https://ikatakos.com/pot/programming_algorithm/number_theory/mod_combination

    def __init__(self, maxN, MOD):
        self._maxN = maxN
        self._MOD = MOD
        self.facts = [1]
        self.invs = [1]*(self._maxN+1)

        fact = 1
        for i in range(1, self._maxN+1):
            fact *= i
            fact %= self._MOD
            self.facts.append(fact)

        inv = pow(fact, self._MOD-2, self._MOD)
        self.invs[self._maxN] = inv
        for i in range(self._maxN, 1, -1):
            inv *= i
            inv %= self._MOD
            self.invs[i-1] = inv

    def nCr(self, n, r):
        return self.facts[n]*self.invs[r]*self.invs[n-r] % self._MOD


def main():

    n, m, k = ns()

    mc = ModCombination(n, MOD)

    result = 0

    for ki in range(k + 1):
        ans = 1
        ans *= m % MOD
        ans *= pow(m - 1, n - 1 - ki, MOD)
        ans %= MOD
        ans *= mc.nCr(n-1, ki)
        ans %= MOD
        result += ans
        result %= MOD

    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

f= [0]*(n+1)
p= [0]*(n+1)

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

def nCk(n,k):
    return f[n]*p[k]*p[n-k]%mod

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

Submission status: Accepted

Solution code:
#解説通り
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m #すべて違う色,k=0
alpha = 1#n-1Ck, k=0の値で初期化
for k in range(1,K+1):
    alpha = (alpha*(N-k)*pow(k,m-2,m))%m#逆元で計算しないとTLE
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
m = 998244353
ans = (M*pow(M-1,N-1,m))%m
alpha = 1
for k in range(1,K+1):
    alpha = (alpha*(N-k)*pow(k,m-2,m))%m
    ans = (ans + M*alpha*pow(M-1,N-k-1,m))%m
print(ans)

Submission status: Accepted

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

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 npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % mod) % mod

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

ans = 0
m = M
comb = Combination(N)
for k in reversed(range(N)):
    now = m
    now *= comb.ncr(N - 1, k)
    now %= mod
    if k <= K:
        ans += now
        ans %= mod
    m *= M - 1
    m %= mod

print(ans)

Submission status: Accepted

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

  
def genCombinationFunction(max_k,mod):
    modinv_table = [-1] * (max_k+1)
    modinv_table[1] = 1
    for i in range(2, max_k+1):
        modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

    def binomial_coefficients(n, k):
        ans = 1
        for i in range(k):
            ans *= n-i
            ans *= modinv_table[i + 1]
            ans %= mod
        return ans
    return binomial_coefficients,modinv_table
f,table=genCombinationFunction(10**6,mod)

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

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
mod=998244353
P=[1 for i in range(10**6+1)]
for i in range(10**6):
  P[i+1]=P[i]*(i+1)%mod

def comb(a,b):
    if a>=b:
        return P[a]*pow(P[a-b],mod-2,mod)*pow(P[b],mod-2,mod)%mod
    else:
        return 0
ans=0
for i in range(K+1):
  ans+=M*comb(N-1,i)*pow(M-1,N-1-i,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,n+10):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,n+10):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,2*10**5+100):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,2*10**5+100):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()