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:
MOD = 998244353

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

def comb(n, r, mod):
    if r > n-r:
        r = n - r
    
    res_X = 1
    for i in range(n-r+1, n+1):
        res_X = (res_X * i)%mod
    
    res_Y = 1
    for i in range(1, r+1):
        res_Y = (res_Y * i)%mod
    
    return (res_X * pow(res_Y, mod-2, mod))%mod

if N==1:
    print(M)
else:
    ans = 0
    mm_1 = M
    if K < (N-1):
        for _ in range(N-K-2):
            mm_1 = (mm_1 * (M-1))%MOD


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

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# dpっぽい
# なんかサンプル3で謎のエラーなるが

from sys import setrecursionlimit
setrecursionlimit(10**8)

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

dp = {}


def rec(i, pre_color, used_k):
    if (i, pre_color, used_k) in dp:
        return dp[i, pre_color, used_k]
    if used_k < 0:
        return 0
    if i == n:
        return 1
    ret = 0
    for j in range(m):
        if j == pre_color:
            ret += rec(i + 1, j, used_k - 1)
        else:
            ret += rec(i + 1, j, used_k)
    ret %= 998244353
    dp[(i, pre_color, used_k)] = ret
    return ret


# 100 100 0
# 60522 114575 7559
print(rec(0, -1, k))

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def prepare(n, mod=998244353):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv

    return factorials, invs


def cmb(n, r):
    mod = 998244353
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


# 実装を行う関数
def resolve(test_def_name=""):
    n, m, k = map(int, input().split())

    # 全組み合わせ数(重複順列)
    # all_pattern = pow(m, n, 998244353)

    # 使用方法サンプル(10 N 3= 10個の要素から3つを選ぶ場合の組み合わせ数)
    fns, invs = prepare(100000000)

    # さらに6 N 5= 6個の要素から5つを選ぶ場合の組み合わせ数 ->このように、大量のパターンが欲しいときはこっちを使う。
    # aa = (fns[6] * invs[5] * invs[6 - 5]) % 998244353  # ans=120

    # 許容される組み合わせを加算していく
    ans = 0
    for i in range(k + 1):
        # ans += (m * pow(m - 1, m - i - 1, 998244353) * cmb(n - 1, i)) % 998244353
        # ans = (fns[n-1] * invs[k] * invs[n-1 - k]) % 998244353
        ans += m * pow(m - 1, n - i - 1, 998244353) * (fns[n - 1] * invs[i] * invs[n - 1 - i])
        ans = ans % 998244353

    print(ans)

    # ans = (m * pow(m - 1, m - k - 1, 998244353) * cmb(n - 1, k)) % 998244353

    # カウント外の組み合わせ数
    # kpl1 = k + 1
    # ng_pattern = m * pow((m - 1), n - (k + 1), 998244353)
    # ng_pattern = ng_pattern % 998244353
    # ans = all_pattern - ng_pattern


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2 1"""
        output = """6"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """100 100 0"""
        output = """73074801"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """60522 114575 7559"""
        output = """479519525"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """4 10 0"""
        output = """7290"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """4 10 1"""
        output = """9720"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """4 10 2"""
        output = """9990"""
        self.assertIO(test_input, output)

    def test_1original_4(self):
        test_input = """4 10 3"""
        output = """10000"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

for k in range(K+1):
    C = factorial(N-1) // factorial(k) // factorial(N-1-k)
    R += M * C * ((M-1)**(N-1-k))

R = R % 998244353
print(R)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

for k in range(K+1):
    C = list(combinations(range(N-1), k))
    R += M * len(C) * ((M-1)**(N-1-k))

R = R % 998244353
print(R)

Submission status: Time Limit Exceeded

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

def comb(n,k,mod):
    nCk = 1

    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
for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += (a*b)%mod
ans *= m
print(ans%mod)

Submission status: Time Limit Exceeded

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

def comb(n,k,mod):
    nCk = 1

    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
for i in range(k+1):
    a = pow(m-1, n-i-1, mod)
    b = comb(n-1,i,mod)
    ans += a*b
ans *= m
print(ans%mod)

Submission status: Time Limit Exceeded

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

mod=998244353

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

def mod_comb_count(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

ans=0

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

Submission status: Time Limit Exceeded

Solution code:
# from math import factorial
from sys import exit
n,m,k = map(int, input().split())
if m == 1:
    if k == n-1:
        print(1)
    else:
        print(0)
    exit()
MOD = 998244353

ans = tmp = (m * (m-1) ** (n-1))
ans %= MOD

for i in range(k):
    tmp *= (n-1-i)
    tmp //= (m-1) * (i+1)
    ans += tmp
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

b = str(bin(mod-2))[2:]
blis = []
for _ in range(len(b)):
  if b[-_-1] == '1':
    blis.append(_)

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    n = len(b)
    li = []
    for _ in range(n):
      li.append(a%mod)
      a = a*a
    for item in blis:
      res = res * li[item] %mod
    return res
      

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

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*modinv(k+1)
  c %= mod
  ncombi.append(c)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

Submission status: Time Limit Exceeded

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

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

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c * (N-1-k)//(k+1)
  ncombi.append(c%mod)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())

    c = [0]*(K+1)
    def comb(k):
        if k == 0:
            ans = 1
        else:
            ans = c[k-1]*(N-k)//k
        c[k] = ans
        return ans

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

    print(ans%998244353)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())
    MOD = 998244353
    
    c = [0]*(K+1)
    def comb(k):
        if k == 0:
            ans = 1
        else:
            ans = c[k-1]*(N-k)//k
        c[k] = ans
        return ans

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

p = MOD
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

# 事前計算した項を掛け合わせ
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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


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


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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n, m, K = map(int, input().split())
    class Combination:
        """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""

        def __init__(self, n, MOD):
            self.fact = [1]
            for i in range(1, n + 1):
                self.fact.append(self.fact[-1] * i % MOD)
            self.inv_fact = [0] * (n + 1)
            self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
            for i in reversed(range(n)):
                self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
            self.MOD = MOD

        def factorial(self, k):
            """k!を求める O(1)"""
            return self.fact[k]

        def inverse_factorial(self, k):
            """k!の逆元を求める O(1)"""
            return self.inv_fact[k]

        def permutation(self, k, r):
            """kPrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

        def combination(self, k, r):
            """kCrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

        def combination2(self, k, r):
            """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
            if k < r:
                return 0
            res = 1
            for l in range(r):
                res *= (k - l)
                res %= self.MOD
            return (res * self.inv_fact[r]) % self.MOD
    MOD = 998244353
    comb = Combination(10 ** 6, MOD)

    ans = 0
    df=m*pow(m-1,n-1-K,MOD)

    now = df
    for i in range(K, -1, -1):
        now = comb.combination(n-1, i)
        ans += now*df
        ans %= MOD
        df *= (m-1)

    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n, m, K = map(int, input().split())
    class Combination:
        """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""

        def __init__(self, n, MOD):
            self.fact = [1]
            for i in range(1, n + 1):
                self.fact.append(self.fact[-1] * i % MOD)
            self.inv_fact = [0] * (n + 1)
            self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
            for i in reversed(range(n)):
                self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
            self.MOD = MOD

        def factorial(self, k):
            """k!を求める O(1)"""
            return self.fact[k]

        def inverse_factorial(self, k):
            """k!の逆元を求める O(1)"""
            return self.inv_fact[k]

        def permutation(self, k, r):
            """kPrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

        def combination(self, k, r):
            """kCrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

        def combination2(self, k, r):
            """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
            if k < r:
                return 0
            res = 1
            for l in range(r):
                res *= (k - l)
                res %= self.MOD
            return (res * self.inv_fact[r]) % self.MOD
    MOD = 998244353
    comb = Combination(10 ** 6, MOD)

    ans = 0
    df=m*pow(m-1,n-1-K)

    now = df
    for i in range(K, -1, -1):
        now = comb.combination(n-1, i)
        ans += now*df
        ans %= MOD
        df *= (m-1)

    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n, m, K = map(int, input().split())
    class Combination:
        """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""

        def __init__(self, n, MOD):
            self.fact = [1]
            for i in range(1, n + 1):
                self.fact.append(self.fact[-1] * i % MOD)
            self.inv_fact = [0] * (n + 1)
            self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
            for i in reversed(range(n)):
                self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
            self.MOD = MOD

        def factorial(self, k):
            """k!を求める O(1)"""
            return self.fact[k]

        def inverse_factorial(self, k):
            """k!の逆元を求める O(1)"""
            return self.inv_fact[k]

        def permutation(self, k, r):
            """kPrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

        def combination(self, k, r):
            """kCrを求める O(1)"""
            if k < r:
                return 0
            return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

        def combination2(self, k, r):
            """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
            if k < r:
                return 0
            res = 1
            for l in range(r):
                res *= (k - l)
                res %= self.MOD
            return (res * self.inv_fact[r]) % self.MOD
    MOD = 998244353
    comb = Combination(10 ** 6, MOD)

    ans = 0
    col = m
    now = col
    for i in range(n-1, -1, -1):
        if i>K:
            col*=(m-1)
            col%=MOD
            continue
        now = comb.combination(n-1, i)
        ans += now*col
        ans %= MOD
        col *= (m-1)

    print(ans)

resolve()

Submission status: Time Limit Exceeded

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

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0]*(K+2)
invmodk[1]=1
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk[k]=invmodk[mod%k]*(mod-mod//k)%mod

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

Submission status: Time Limit Exceeded

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

mod=998244353

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb

invmodk=[0,1]
invmodm=pow(M-1,mod-2,mod)
for k in range(2,K+1):
    invmodk.append(invmodk[mod%k]*(mod-mod//k)%mod)

for k in range(1,K+1):
    pw=(pw*invmodm)%mod
    comb*=(N-k)*invmodk[k]
    ans=(ans+pw*comb)%mod

print(ans)

Submission status: Time Limit Exceeded

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

mod=998244353

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

comb=1
pw=(M*pow(M-1,N-1,mod))%mod
ans=pw*comb
invmodm=invmod(M-1)

for k in range(1,K+1):
    pw*=invmodm
    comb*=(N-k)*invmod(k)
    ans=(ans+pw*comb)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 998244353
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def combMod(n, r, p):
    numer = 1
    denom = 1
    for i in range(1, r+1):
        numer = numer * (n-r+i) % p
        denom = denom * i % p
    return numer * pow(denom, p-2, p) % p

def resolve():
    N, M, K = LI()

    ans = 0

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

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

ans = 0
NCi = 1#nからi選ぶ組み合わせ
for i in range(0,K+1,1):
    ans = (ans + M * pow(M-1,N-1-i,MOD)*NCi)%MOD
    NCi = NCi*(N-1-i)*pow((i+1),MOD-2,MOD)

print(ans)

Submission status: Time Limit Exceeded

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

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

def power_func(a,n,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

out = 0
p = 998244353
for i in range(K+1):
    out += M*comb(N-1,i,p)*power_func(M-1,N-1-i,p)
    out = out % p
print(out)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    if m == 0:
        return 1
    if m == 1 or n == 1 or n == 0:
        return n
    v = modpow(n, m // 2)
    v = v * v % MOD
    if m % 2 == 1:
        v = v * n % MOD
    return v


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    n, m, k = map(int, input().split())
    print(solve(n, m, k))

    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def comb(a, b):
        numerator = 1
        denominator = 1
        if a-b < 0:
            return None
        b = min(a-b, b)
        for i in range(a-b+1, a+1):
            numerator *= i
        for i in range(1, b+1):
            denominator *= i
        return numerator//denominator


    n, m, k = map(int, input().split())
    MAX = 998244353
    ans = 0
    pattern = lambda x: (comb(n-1, x)*m*(((m-1)**(n-1-x))%MAX))%MAX
    for i in range(k+1):
        ans += pattern(i)
        ans %= MAX
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

c = comb(N-1, K, exact=True)
exp = ((M-1) ** (N-1-K)) % mod

answer = (M * c * exp) % mod

for t in range(1, K+1):
    c = ((c * (K - t + 1)) // (N-1-K+t))
    exp = (exp*(M-1)) % mod
    answer += (M * c * exp) % mod
    answer = answer % mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, K = list(map(int, input().split()))
mod = 998244353
d = np.zeros(K+2)
d[1] = M
for _ in range(N-1):
    d[1:] = (d[:-1] + d[1:] * (M-1)) % mod
print(int(sum(d) % mod))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

mod = 998244353

d = np.zeros(K+1)
d[0] = M

for _ in range(N-1):
    d[1:] = (d[:-1] + d[1:] * (M-1)) % mod
    d[0] = (d[0] * (M-1))  % mod

print(int(sum(d) % mod))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    global factrial
    global factrial_inv
    factrial = [-1 for i in range(lim+1)]
    factrial_inv = [-1 for i in range(lim+1)]

    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if not(factrial[0] in locals()):
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m, k = [int(_) for _ in input().split()]
ans = 0
for i in range(k+1):
    ans += m*comb(n-1, i)*mod_pow(m-1, n-1 - i)
    ans %= MOD
    # print(ans)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

MOD = 998244353  # type: int

def combination(n: int, r:int, mod=MOD):
    n1 = n+1
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


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

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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

def choose(n, k):
    if 0 <= k and k <= n:
        ntok = 1
        ktok = 1
        for t in range(1, min(k, n - k) + 1):
            ntok *= n % mod
            ktok *= t % mod
            n -= 1
        return ntok // ktok
    else:
        return 0

sum = 0
for i in range(k+1):
    sum = (sum + (m * choose(n-1,i) * ((m-1) ** (n-1-i)))) % mod

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
mod = 998244353
def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % mod
 
def combination(n, r, mod):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * powerDX(denom, mod-2, mod) % mod
 
ans = 0
for i in range(0, k+1):
  ans += m*combination(n-1, i, mod)*powerDX(m-1, n-i-1, mod)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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


def ncr(a, b):
    if b == 0:
        return 1
    else:
        num = reduce(lambda x, y: x * y % modi, range(a, a-b, -1))
        den = reduce(lambda x, y: x * y % modi, range(1, b+1))
        return num * pow(den, modi - 2, modi) % modi


res = 0
for i in range(k + 1):
    res += m % modi * pow(m - 1, n - i - 1, modi) * ncr(n - 1, i)
    res %= modi
print(res)

Submission status: Time Limit Exceeded

Solution code:
# N個のブロック、M色、K組
N,M,K = map(int,input().split())
MOD = 998244353

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

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

print(res)