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: Runtime Error

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self.fact(n))
        return self._factorial_inv[n]
    
    def _make_inv(self, n, r=1):
        if n >= self.mod:
            n = self.mod - 1
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        self._factorial_inv[n] = self.modinv(self.fact(n))
        for i in range(n-1, r, -1):
            self._factorial_inv[i] = _factorial_inv[i+1]*n % self.mod
            
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod
    
    def comb_(self, n, r):
        '''
        nCr % mod
        when r is not large and n is too large
        '''
        c = 1
        for i in range(1, r+1):
            c *= (n-i+1) * self.fact_inv(i)
            c %= self.mod
        return c

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

n, m, k = map(int, input().split())
mod = 998244353
f = Factorial(mod)
f._make_inv(n-1)
comb = f.comb
s = 0
for i in range(k+1, n):
    t = comb(n-1, i)*m % mod
    t = t*pow(m-1, n-1-i, mod) % mod
    s = (s+t) % mod
ans = (pow(m, n, mod)-s) % mod
print(ans)

Submission status: Runtime Error

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1
    
    def __call__(self, n):
        return self.fact(n)
    
    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make_inv(n)
        return self._factorial_inv[n]
    
    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self.fact_inv(n-r)*self.fact_inv(r) % self.mod
        return self(n)*t % self.mod
    
    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self.fact_inv(n-1)*self.fact_inv(r) % self.mod
        return self(n+r-1)*t % self.mod
    
    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0
    
    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1
    
    def _make_inv(self, n):
        if n >= self.mod:
            n = self.mod
        self.make(n)
        if self._size_inv < n+1:
            for i in range(self._size_inv, n+1):
                self._factorial_inv.append(self.modinv(self._factorial[i]))
            self._size_inv = n+1

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

Submission status: Runtime Error

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

n,m,k=map(int,input().split())
mod=998244353
fac=[1]*n
finv=[1]*n
inv=[0]*n
inv[1]=1
for i in range(2,n):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

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: Runtime Error

Solution code:
def comb(n, k, mod=10 ** 9 + 7):
    denominator = 1
    numerator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    for i in range(n - k + 1, n + 1):
        numerator = numerator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

mod = 998244353
ans = 0
for k in range(K+1):
  c = math.factorial(n-1) / (math.factorial(k) * math.factorial(n-1-k))
  ans += m * c * pow(m-1,n-1-k,mod) % mod

print(int(ans))

Submission status: Runtime Error

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

mod = 998244353
ans = 0
for k in range(K+1):
  c = math.factorial(n-1) / (math.factorial(k) * math.factorial(n-1-k))
  ans += m * c * 1**k * (m-1)**(n-1-k)

print(int(ans%mod))

Submission status: Runtime Error

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        ans = self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
        if n >= r:
            return ans
        else:
            return 0
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n,mod)
    ans = 0
    mex = [0]*(k+1)
    mex[0] = pow(m-1,n-k-1,mod)
    for i in range(1,k+1):
        mod[i] = mex[i-1]*(m-1)%mod
    mex = mex[::-1]
    for i in range(k+1):
        ans += c.combination(n-1, i)*mex[i]
        ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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


def solve(now, pairs, colors):
  if now == N:
    ans.append(m[colors])
    return 0
  elif pairs == K:
    colors += N - now
    ans.append(m[colors])
    return 0
  else:
    solve(now+1, pairs+1, colors)
    solve(now+1, pairs, colors+1)


solve(1, 0, 1)


#print(ans)
a = 0
for _ in range(len(ans)):
  a += ans[_]
  a %= mod
print(a)

Submission status: Runtime Error

Solution code:
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**8)

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

Submission status: Runtime Error

Solution code:
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**7)

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

Submission status: Runtime Error

Solution code:
# E - Colorful Blocks
import sys
sys.setrecursionlimit(10**7)
MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD)
ans = 0
tmp = pow(M-1,N-1,MOD)
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
# E - Colorful Blocks
MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD)
ans = 0
tmp = pow(M-1,N-1,MOD)
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    if i==K:
        break
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
# E - Colorful Blocks
MOD = 998244353
N,M,K = map(int,input().split())
inv_M = pow(M-1,-1,MOD)
ans = 0
tmp = pow(M-1,N-1,MOD)
comb = 1
for i in range(K+1):
    ans = (ans+M*comb*tmp)%MOD
    tmp = (tmp*inv_M)%MOD
    comb = (comb*(N-1-i)*pow(i+1,-1,MOD))%MOD
print(ans)

Submission status: Runtime Error

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

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

    for i in range(1,N):
        dp[0][i] = (dp[0][i-1] * (M-1)) % MOD

        for k in range(1, K+1):
            dp[k][i] = (dp[k][i-1] * (M-1) + dp[k-1][i-1]) % MOD
        
    res = 0
    for k in range(K+1):
        res += dp[k][-1]
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 30 09:18:42 2020

@author: Aruto Hosaka
"""
from math import factorial

def comb(n,k,p):
  """power_funcを用いて(nCk) mod 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):
  """a^b mod 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


A = list(map(int, input().split()))
mod = 998244353
N = A[0]
M = A[1]
K = A[2]

s = (M*(M-1)**(N-1))
D = (M*(M-1)**(N-1))%mod
for k in range(1,K+1):
    s = s*(N-k)//k//(M-1)
    D += s%mod

print(D%mod)

Submission status: Runtime Error

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+1)
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: Runtime Error

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n, k = rl()
    A = rl()
    # leaps = [A]
    # leap_size = 2
    # while leap_size <= k:
        # new_leap = []
        # for i in range(n):
    curr = 1
    seen = {1:0}

    for i in range(1, k + 1):
        curr = A[curr - 1]
        if i == k:
            print (curr)
            return
        elif curr in seen:
            break
        seen[curr] = i

    cycle_len = i - seen[curr]
    # print (cycle_len)

    while 1:
        if i % cycle_len == k % cycle_len:
            print (curr)
            return
        i += 1
        curr = A[curr - 1]






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
def kaijou(a):
    result = 1
    for i in range(1,a+1):
        result *= i
    return result
def combination(n,i):
    return (kaijou(n)/kaijou(i))/kaijou(n-i)
s = 0
for i in range(0,k+1):
    s += m * (m-1)**(n-1-i) * combination(n-1,i)
print(int(s % 998244353))

Submission status: Runtime Error

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())
    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: Runtime Error

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())
    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: Runtime Error

Solution code:
def main():
    def kaizyo(x):
        ans = 1
        for i in range(2, x+1):
            ans *= i
        return ans

    n, m, k = map(int, input().split())
    MAX = 998244353
    ans = 0
    kaizyos = [None]*n
    ki = 1
    kaizyos[0] = ki
    for i in range(1, n):
        ki *= i
        ki %= MAX
        kaizyos[i] = ki
    def comb(a, b):
        return kaizyos[a]//(kaizyos[b]*kaizyos[a-b])
    ruizyos = [None]*(k+1)
    ruizyo = 1
    for i in range(n-1-k):
        ruizyo *= m-1
        ruizyo %= MAX
    ruizyos[0] = ruizyo
    for i in range(n-k, n):
        ruizyo *= m-1
        ruizyo
        ruizyos[i-n-k+1] = ruizyo
    pattern = lambda x: (comb(n-1, x)*m*ruizyos[x])%MAX
    for i in range(k+1):
        ans += pattern(i)
        ans %= MAX
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装
    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく
        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            self.inverses.append(
                self.mod - self.inverses[self.mod % i] *
                (self.mod // i) % self.mod
            )
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する
        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < n:
            raise ValueError
        if k == 0:
            return 1

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


MOD = 998244353

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

ans = 0
comb = ModCombination(mod=MOD, n_max=N)
for k in range(0, K + 1):
    ans += (M * comb.mod_combination(N - 1, k)) % MOD * mod_pow(M - 1, N - 1 - k, MOD)
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
mod=998244353
cntb=1
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-i−1)*pow(i+1,mod-2,mod))%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
n, m, k = [int(t) for t in open(0).read().split()]
mod = 998244353


def solve(n):
    if n <= k + 1:
        return pow(m, n, mod)
    elif n == k + 2:
        return (pow(m, n, mod) + mod - m) % mod
    else:
        return (m * solve(n - 1) - (m - 1) * solve(n - k - 2)) % mod


print(solve(n))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
for i in range(n):
  s.append(input())
for i in range(5*10**2):
  count=0
  for j in range(min(10**3,n)):
    b=random.randrange(0,max(len(s[j])-99,1))
    for k in range(b,min(len(s[j]),100+b)):
      if s[j][k]=="(":
              count+=1
      elif s[j][k]==")":
              count-=1
      else:raise Exception
  try:
    dic[count]+=1
  except:
    dic[count]=1
#print(dic)
try:
  if dic[0]>10:
    print("Yes")
  else:
    print("No")
except:print("No")

Submission status: Runtime Error

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

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c
if N == 1:
    print(M)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)

Submission status: Runtime Error

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

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c

func = combination_mod(N-1,m)
ans = 0
for k in range(K+1):
    ans_temp = M
    ans_temp = (ans_temp * func.calc(k)) % m
    ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
    ans += ans_temp
    ans = ans % m
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    N = I()
    zero = 0
    plus_Ai_Bi = defaultdict(int)
    minus_Bj_Aj = defaultdict(int)
    zero_cnt = 0
    used = set()

    for i in range(N):
        a, b = MI()

        if a == 0 and b == 0:
            zero_cnt += 1
            continue

        gcdab = gcd(abs(a), abs(b))
        a = a // gcdab
        b = b // gcdab
        n = 1

        if a > 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a > 0 and b < 0:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a < 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        else:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(b, -a)] += 1

    ans = 1

    for pair, cnt1 in plus_Ai_Bi.items():
        a, b = pair
        if pair in used:
            continue

        if pair in minus_Bj_Aj:
            cnt2 = minus_Bj_Aj[pair]
            group1 = pow(2, cnt1, MOD) - 1
            group2 = pow(2, cnt2, MOD) - 1
            ans *= group1 + group2 + 1
            ans %= MOD

            # avoid double count
            if a > 0:
                used.add((-b, a))
            else:
                used.add((b, -a))
        else:
            ans *= pow(2, cnt1, MOD)
            ans %= MOD

    print((ans - 1 + zero_cnt) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class Cmb:
    def __init__(self, N, mod=998244353):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,m,k = map(int,input().split())
mod = 998244353
ans = 0
c = Cmb()
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)*c(n-1, x)%mod
        ans %= mod
print(ans%mod)

Submission status: Runtime Error

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

CONV = 1
KAIJ = (M - 1) ** (N - 1)
ans = 0

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

Submission status: Runtime Error

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

def nck(q, r):
    a = (factorial(q)) / (factorial(r)) / (factorial(q - r))
    return a%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: Runtime Error

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+1):
        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: Runtime Error

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

#すべての色の塗り方の数
count=math.pow(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: Runtime Error

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

#すべての色の塗り方の数
count=math.pow(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=count % 998244353
print(ans)

Submission status: Runtime Error

Solution code:
## coding: UTF-8

#ダブリングを利用した実装

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

#2**59 < 10**18< 2**60より2**60まで格納する
l = [0] * (N*61)

for j in range(N):
    l[j] = A[j]


for i in range(1,61):
#for i in range(1, 4):
    for j in range(N):
        p = l[(i-1)*N+j] #一段上を参照(2**(i-1)回移動した時の移動先)
        q = l[(i-1)*N+(p-1)] #pから2**(i-1)回移動した時の移動先を参照　＝　2**i 回移動した時の移動先
        l[i*N+(j)] = q
    #print(l)
#print(l)

bin_str = format(K, 'b')
#print(bin_str)
s = bin_str[::-1]
#print(s)
now = 1 #start地点
for i in range(len(s)):
    if(s[i] == '1'):
        now = l[(i)*N + (now-1)]
        #print(now)

        '''
        next_index = i*N + l[i*N + (now-1)]-1
        nex = l[next_index]
        now = nex
        print(now)
        '''
print(now)