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:
N,M,K = map(int,input().split())
MOD = 998244353

def nCr(n,r):
  ansMul, ansDiv = 1, 1
  for i in range(r):
    ansMul *= (n-i)
    ansDiv *= (i+1)
    ansMul %= MOD
    ansDiv %= MOD
  return (ansMul * pow(ansDiv, MOD-2, MOD)) % MOD

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
"""nCk (逆元ver) """
def comb(n,k):
    nCk = 1
    mod = 998244353
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
    for i in range(1, k+1):
        nCk *= pow(i, mod-2, mod)
        nCk %= mod
    return nCk

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

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

Submission status: Time Limit Exceeded

Solution code:
M=998244353
n,m,k=map(int,input().split())
a=m*pow(m-1,n-1,M)
c=1
for i in range(1,k+1):
  t=m*pow(m-1,n-i-1,M)
  c=c*(n-i)*pow(i,M-2,M)
  a+=t*c%M
print(a%M)

Submission status: Time Limit Exceeded

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

CONV = [1]
ans = 0

for i in range(1, N):
  CONV.append(CONV[-1] * (N-i) // i)

for k in range(K+1):
  # M x (N-1)Ck x (M-1) ^ (N - 1 - k)
  ans += (CONV[k] * pow(M-1, N-1-k, MOD)) % MOD
  
print(ans * M % MOD)

Submission status: Time Limit Exceeded

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

dp = [[0] * (N + 1) for _ in range(N)] 
dp[0][0] = M

for i in range(N - 1):
  for j in range(N):
    dp[i+1][j] += dp[i][j] * (M-1)
    dp[i+1][j+1] = dp[i][j] * 1
print(sum(dp[-1][:K+1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n, m, k = map(int, input().split())
MOD = 998244353
ans = 0

def nck(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result%MOD


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=deque([])
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)

    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=pow(M-1,N-1-i,MOD)

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)

    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=pow(M-1,N-1-i,MOD)

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

p = 998244353
N, M, K = map(int, input().split())
res = 0

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

for k in range(K + 1):
    res += M * comb_count(N - 1, k) * pow(M - 1, N - 1 - k) % p
    res %= p

print(res)

Submission status: Time Limit Exceeded

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

def solve():
    import sys

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

    """
    xの組を作るとする
    (1) グループ数: N-x
    (2) グループの色の割り当て方：M(M-1)**(N-1)
    (3) グループの分け方：(N-1)C(x)
    """

    bunsi_memo = {}
    bunbo_memo = {}
    pow_memo = {}
    def combination_formula_MOD(n, r, MOD):
        """nCrを O(min(n-r, r)) で高速に計算する"""
        def _inv(x, MOD):
            """xの逆元を返す"""
            if not (x, MOD-2) in pow_memo:
                pow_memo[(x, MOD-2)] = pow(x, MOD-2, MOD)
            return pow_memo[(x, MOD-2)]

        if n < r: return 0

        r = min(n-r, r)
        bunsi, bunbo = 1, 1
        if not r in bunsi_memo:
            for i in range(r):
                bunsi = bunsi*(n-i)%MOD
                bunbo = bunbo*(i+1)%MOD
            bunsi_memo[r] = bunsi
            bunbo_memo[r] = bunbo
        bunsi, bunbo = bunsi_memo[r], bunbo_memo[r]
        return (bunsi*_inv(bunbo, MOD))%MOD


    ans = 0
    col = M
    for x in range(N-1, -1, -1):
        if x <= K:
            now = col%MOD
            now = (now * combination_formula_MOD(N-1, x, MOD))%MOD
            ans += now
            ans %= MOD

        col *= (M-1)
        col %= MOD

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

def solve():
    import sys

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

    """
    xの組を作るとする
    (1) グループの分け方: N-x
    (2) 色の割り当て方：M(M-1)**(N-1)
    (3) 組の作り方：(N-1)C(x)
    """

    def combination_formula_MOD(n, r, MOD):
        """nCrを O(min(n-r, r)) で高速に計算する"""
        def _inv(x, MOD):
            """xの逆元を返す"""
            return pow(x, MOD-2, MOD)

        if n < r: return 0

        r = min(n-r, r)
        bunsi, bunbo = 1, 1
        for i in range(r):
            bunsi = bunsi*(n-i)%MOD
            bunbo = bunbo*(i+1)%MOD
        return (bunsi*_inv(bunbo, MOD))%MOD


    ans = 0
    col = M
    for x in range(N-1, -1, -1):
        now = col%MOD
        now = (now * combination_formula_MOD(N-1, x, MOD))%MOD
        if x <= K:
            ans += now
            ans %= MOD

        col *= M-1
        col %= MOD

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

N = 998244353

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i,N)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i,N)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)

Submission status: Time Limit Exceeded

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

N = 998244353

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N,M,K=map(int,input().split())
total_case=product(range(M),repeat=N)

#すべての色の塗り方の数
count=M**N

#すべての色の塗り方をAとしてリスト化
A=[]
for i in total_case:
    A.append(i)

#各塗り方に対して隣り合う色が存在するか判定する
for j in A:
#色が被ってよい組み合わせ数
    limit=K
    out_flag=0
    for p in range(N-1):
        if j[p]==j[p+1]:
            limit = limit-1
            if limit<0:
              out_flag=-1  
              break
    if out_flag==-1:
        count=count-1

#答えの算出および表示
ans=int(count % 998244353)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def mod_comb(places, objects):
  numerator = 1
  denominator = 1
  for i in range(objects):
    numerator = (numerator*(places-i))%prime_mod
    denominator = (denominator*(i+1))%prime_mod
  ans = prime_cycle_division(numerator, denominator)
  return ans

def combos(j):
  ans = (m*mod_comb(n-1, j))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def prime_factorial(lower, upper):
  total = 1
  for i in range(lower+1, upper+1):
    total = (total*i)%prime_mod
  return total

def mod_comb(places, objects):
  objects = min(objects, places-objects)
  numerator = prime_factorial(places-objects, places)
  denominator = prime_factorial(0, objects)
  ans = prime_cycle_division(numerator, denominator)
  return ans

def combos(j):
  ans = (m*mod_comb(n-1, j))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Submission status: Time Limit Exceeded

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



#mod = 10**9+7 #割る数
mod=998244353 #割る数
N = 2*10**5 #nの上限
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 )

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def prime_factorial(lower, upper):
  total = 1
  for i in range(lower+1, upper+1):
    total = (total*i)%prime_mod
  return total

def mod_comb(places, objects):
  numerator = prime_factorial(places-objects, places)
  denominator = prime_factorial(0, objects)
  ans = prime_cycle_division(numerator, denominator)
  return ans

def combos(j):
  ans = (m*mod_comb(n-1, j))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD

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

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin
from scipy.special import comb


def main():
    N, M, K = [int(x) for x in stdin.readline().rstrip().split()]
    MOD = 998244353
    ans = 0

    for i in range(N - K - 1, N):
        C = comb(N - 1, i, exact=True)
        c = (M - 1) ** i
        ans += M * c * C
        ans = ans % MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def pow_speed(x,n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res *= x
        x *= x
        x%=mod
        n >>= 1
    return res

def comb(n,x):
    rec=1
    for i in range(n-x+1,n+1):
        rec=rec*i%mod
    rec2=1
    for i in range(1,x+1):
        rec2=rec2*i%mod
    rec2=pow_speed(rec2,mod-2)
    return rec*rec2

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

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 998244353

import numpy as np
def create_modC(n, mod):
    if n == 0:
        return (lambda r: 1)
    b = int(math.log(mod-2, 2)) + 1
    fac = np.zeros((b, n+1), dtype=np.int64)
    print(fac.shape)
    inv = np.ones(n+1, dtype=np.int64)
    fac[0, 0], fac[0, 1] = 1, 1
    for i in range(2, n+1):
        fac[0, i] = (fac[0, i-1] * i) % mod
    for i in range(1, b):
        fac[i, :] = (fac[i-1, :] ** 2) % mod

    indice = []
    N = mod - 2
    i = 0
    while N > 0:
        if N % 2 == 1:
            indice.append(i)
        N = N >> 1
        i += 1
    
    for i in indice:
        inv *= fac[i,:]
        inv %= mod
    
    fac = fac[0,:]

    def _modC(r):
        if r == 0 or r == n:
            return 1
        result = fac[n] * inv[n-r]
        result %= mod
        result *= inv[r] % mod
        result %= mod
        return result

    return _modC


def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 60522,114575,7559
    answer = 479519525
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")

    N, M, K = 200000,190000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 1,1,0
    print(f"N={N} M={M} K={K}")
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    N, M, K = 200000,200000,190000
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}")

    for i in range(100):
        N, M = np.random.randint(200000), np.random.randint(200000)
        K = np.random.randint(N-1)
        v = resolve(N, M, K)
        print(f"N={N} M={M} K={K} {v}")




def main():
    test()
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    from datetime import datetime
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = create_modC(N-1, mod)
    
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(k)
        v = b 
        v *= c
        v %= mod
        #if k < 10:
        #    print(f"b={b} c={c} k={k} {v}")
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    MOD = 998244353

    class Comb:
        def __init__(self, N):
            self.fac = [1] * (N+1)
            for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

        def __call__(self, n, r):
            return self.comb(n, r)

        def comb(self, n, r):
            if r < 0 or r > n: return 0
            return (self.fac[n] * pow(self.fac[r], MOD-2, MOD)) % MOD * pow(self.fac[n-r], MOD-2, MOD) % MOD

        def permutation(self, n, r):
            if r == 0: return 1
            return self.fac[n] * pow(self.fac[n-r], MOD-2, MOD) % MOD

    comb = Comb(N)

    ans = 0

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * pow(self.fac[r], MOD-2, MOD)) % MOD * pow(self.fac[n-r], MOD-2, MOD) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * pow(self.fac[n-r], MOD-2, MOD) % MOD

comb = Comb(N)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
t = 1
b = 1
for i in range(k+1):
  ans += t * pow(m-1, n-1-i, mod) * pow(b, mod-2, mod)
  ans %= mod
  #n-1Ci * (m-1)**i
  t *= (n-1-i)
  b *= (i+1)
print(ans*m%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 998244353

def cached_modC(n, mod):
    fac = mod_factorial(mod)
    nf = fac(n)
    def modC(r):
        if r == 0 or r == n:
            return 1
        if r == 1 or r == n-1:
            return n
        nrf = fac(n-r)
        nr_pow = mod_pow(nrf, mod)
        rf = fac(r)
        r_pow = mod_pow(rf, mod)
        result = nf
        result *= nr_pow(mod-2)
        result %= mod
        result *= r_pow(mod-2)
        result %= mod

        return result

    return modC

def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y, x=x):
        nonlocal xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")
    N, M, K = 60522,114575,7559
    answer = 479519525
    v = resolve(N, M, K)
    print(f"N={N} M={M} K={K} {v}={answer}")



def main():
    #test()
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = cached_modC(N-1, mod)
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(k)
        v =  b * c
        v %= mod
        #if k < 10:
        #    print(f"b={b} c={c} k={k} {v}")
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
n, m, k = map(int, input().split())
result = 0
def search(now_node, same_num, diff_num):
    global result
    if(now_node == n):
        result += m * (m-1) ** diff_num
    else:
        if(same_num < k):
            search(now_node + 1, same_num + 1, diff_num)
        search(now_node + 1, same_num, diff_num + 1)
search(1, 0, 0)
print(result % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

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

def main():
  n,m,k=LI()
  ans=0
  col=m
  for x in range(n)[::-1]:
    now=col
    now*=com(n-1,x)
    if x<=k:
      ans+=now
      ans%=mod
    col*=m-1
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

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

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb
n,m,k = map(int,input().split())
ans = 0
MOD = 998244353
for i in range(0,k+1):
  a = (m*(m-1)**(n-i-1))%MOD
  b = comb(n-1, i, exact=True)%MOD
  shokei =(a*b)%MOD
  ans = (ans + shokei) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int


class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD

    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    def mod_fact(self, x: int):
        res = 1
        for i in range(1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD
    
    def mod_partial_fact(self, x: int, y: int):
        res = 1
        for i in range(x - y + 1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_partial_fact(n, k)
        denomintator = self.mod_fact(k)
        return numerator * self.mod_inv(denomintator) % self.MOD

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

    op = ModOperator(MOD)
    sum = 0
    for i in range(K + 1):
        sum += M * op.mod_pow(M - 1, N - 1 - i) * op.mod_comb(N - 1, i)
    print(sum % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

counter =0

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

def painting(length,color_num):
    return color_num*(color_num-1)**(length-1)

for k in range(K+1):
    counter += combinations_count(N-1,k)*painting(N-k,M)
    counter %= 998244353



all = counter 
print(all)

Submission status: Time Limit Exceeded

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

counter =0

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

def painting(length,color_num):
    return color_num*(color_num-1)**(length-1)

for k in range(K+1):
    counter += combinations_count(N-1,k)*painting(N-k,M)



all = counter 
print(all%998244353)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 998244353

def cahched_modC(n, mod):
    factorial = mod_factorial(mod)
    nf = factorial(n)
    def modC(n, r, mod):
        nrf = factorial(n-r)
        rf = factorial(r)
        nr_pow = mod_pow(nrf, mod)
        r_pow = mod_pow(rf, mod)
        v = nf * nr_pow(mod-2) * r_pow(mod-2)
        return v % mod
    return modC

def mod_factorial(mod):
    cache = [1,1,2]
    def _factorial(n):
        nonlocal cache
        if n == 0:
            return 1
        length = len(cache)
        v = cache[-1]
        while n >= length:
            v *= length 
            v %= mod
            cache.append(v)
            length +=1
        return cache[n]
    return _factorial

def mod_pow(x, mod):
    xx = [1, x]
    def _pow(y):
        nonlocal x,xx
        if y == 0:
            return 1
        while len(xx) <= math.log(y, 2)+1:
            v = xx[-1] * xx[-1]
            v %= mod
            xx.append(v)
        i = 1
        result = 1
        while y > 0:
            if y % 2 == 1:
                result *= xx[i]
                result %= mod
            y = y >> 1
            i += 1
        return result
    return _pow

def test():
    n = 3
    mod = 11
    modC = cahched_modC(n, mod)
    for r in range(n+1):
        v = modC(n, r, mod)
        print(f"{n}C{r}={v}")
    N, M, K = 3,2,1
    answer = 6
    v = resolve(N, M, K)
    print(f"{v}={answer}")
    N, M, K = 100,100,0
    answer = 73074801
    v = resolve(N, M, K)
    print(f"{v}={answer}")
    #N, M, K = 60522,114575,7559
    #answer = 479519525
    #v = resolve(N, M, K)
    #print(f"{v}={answer}")



def main():
    #test()
    N, M, K = map(int, input().split())
    v = resolve(N, M, K)
    print(v)


def resolve(N, M, K):
    result = 0
    m1pow = mod_pow(M-1, mod)
    modC = cahched_modC(N-1, mod)
    for k in range(K+1):
        b = m1pow(N-1-k)
        c = modC(N-1, k, mod)
        v =  (b % mod) * (c % mod)
        #print(f"k={k} v={v}")
        result += v
        result %= mod
    
    result *= M
    result %= mod

    result = int(result)

    return result

        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

counter =0

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

def painting(length,color_num):
    return color_num*(color_num-1)**(length-1)

for k in range(1,K+1):
    counter += combinations_count(N-1,k)*painting(N-k,M)



all = counter + painting(N,M)
print(all%998244353)