Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from itertools import permutations, tee

    INF = 1 << 30

    N, M, R = map(int, input().split())
    *r, = (int(x) - 1 for x in input().split())

    d = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(
                    d[i][j],
                    d[i][k] + d[k][j]
                )

    ans = INF
    for perm in permutations(r):
        perm_iter = iter(perm)
        frm_iter, to_iter = tee(perm_iter, 2)
        next(to_iter)
        t = 0
        for frm, to in zip(frm_iter, to_iter):
            t += d[frm][to]
        ans = min(ans, t)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from itertools import permutations

inf = float('inf')
n, m, r = map(int, input().split())  # 町数、道数、訪問地数
t = tuple(int(x) - 1 for x in input().split())  # 訪問地
g = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = inf
for p in permutations(t):
    ans = min(ans, sum(g[a][b] for a, b in zip(p, p[1:])))
print(ans)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1
    if (c == 0 or c == w - 1) and (not flg):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(' '.join(map(str, aa)))


Fixed submission:
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1

    if (w == 1) or ((c == 0 or c == w - 1) and (not flg)):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(*aa)

Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1
    if (c == 0 or c == w - 1) and (not flg):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(*aa)


Fixed submission:
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = [[None] * w for _ in range(h)]

cur = 1
way = 1
r, c = 0, 0
flg = True
while cur <= n:
    ans[r][c] = cur
    a[cur] -= 1
    if a[cur] == 0:
        cur += 1

    if (w == 1) or ((c == 0 or c == w - 1) and (not flg)):
        r += 1
        way *= -1
        flg = True
    else:
        c += way
        flg = False
    # print(r, c)

for aa in ans:
    print(*aa)
Buggy python submission (verdict: Time Limit Exceeded):
# 解説
# https://img.atcoder.jp/agc018/editorial.pdf

def solve():
    import sys

    sys.setrecursionlimit(10 ** 7)

    def simulate(use: set):
        if not use:
            return n
        cnt = [0] * m
        for player in a:
            for sport in player:
                if sport in use:
                    cnt[sport] += 1
                    break
        max_ = max(cnt)
        ret = max_
        for j, c in enumerate(cnt):
            if c == max_:
                ret = min(ret, simulate(use - {j}))
        return ret

    n, m = map(int, input().split())
    a = [tuple(int(x) - 1 for x in input().split()) for _ in range(n)]
    use = set(range(m))
    return simulate(use)


print(solve())

# まず、すべてのスポーツを実施すると仮定して、どのスポーツに何人の人が参加するか調べます。
# ここで、最も参加人数の多いスポーツがスポーツ P で、その参加人数が Q 人だとします。
# 当り前ですが、この段階で、参加人数の最大値が Q の解が得られています。
# よって、あと考えるべきは、参加人数の最大値が Q 未満の解です。
# そして、そのような解において、スポーツ P は必ず実施されません。
# なので、Q 未満の解を求めるには、スポーツ P を候補から外した上で、
# もう一度同じ問題を解きなおせばよいです。
# これを再帰的に行っていけば、最終的な解を求めることができます。
# 再帰するごとに候補の数が減るので、再帰は合計 M 回呼ばれます。
# 誰がどのスポーツを選ぶのか愚直にシミュレーションすると O(NM) かかるので、
# 全体で O(NM2) でこの問題は解けました。
# なお、シミュレーションを工夫すると、全体で O(NM) でこの問題を解くこともできます。


Fixed submission:
# https://atcoder.jp/contests/agc018/submissions/2152627
# 写経

from collections import deque
from operator import itemgetter


def solve(n, m, prefers):
    def sub(prefers, canceled):
        ret = [0] * m
        for pref in prefers:
            while canceled[pref[0]]:
                pref.popleft()
            ret[pref[0]] += 1
        return max(enumerate(ret), key=itemgetter(1))

    canceled = [False] * m
    ret = n
    for _ in range(m):
        s, c = sub(prefers, canceled)
        canceled[s] = True
        ret = min(ret, c)
    return ret


if __name__ == '__main__':
    n, m = map(int, input().split())
    prefers = [deque(int(x) - 1 for x in input().split()) for _ in range(n)]
    print(solve(n, m, prefers))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a, b = [], []
for _ in range(n):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

ans = 0
i = n - 1
while i >= 0:
    r = a[i] % b[i]
    if r != 0:
        t = b[i] - r
        ans += t
        for j in range(i):
            a[j] += t
    i -= 1

print(ans)

Fixed submission:
n = int(input())

a, b = [], []
for _ in range(n):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

ans = 0
i = n - 1
while i >= 0:
    a[i] += ans
    r = a[i] % b[i]
    if r != 0:
        ans += b[i] - r
    i -= 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    K, S = map(int, input().split())

    memo = [[-1] * (S + 1) for _ in range(4)]

    def dfs(cur, s=0):
        if ~memo[cur][s]:
            return memo[cur][s]

        if cur == 3:
            ret = int(s == S)
            memo[cur][s] = ret
            return ret

        ret = 0
        for r in range(min(K, S - s) + 1):
            ret += dfs(cur + 1, s + r)
        memo[cur][s] = ret
        return ret

    ans = dfs(0)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
k, s = map(int, input().split())
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y)
        if (0 <= z) and (z <= k):
            cnt += 1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    K, S = map(int, input().split())

    def dfs(cur, s=0):
        if cur == 3:
            return int(s == S)

        ret = 0
        for r in range(min(K, S - s) + 1):
            ret += dfs(cur + 1, s + r)
        return ret

    ans = dfs(0)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
k, s = map(int, input().split())
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y)
        if (0 <= z) and (z <= k):
            cnt += 1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if (x + y + z) == s:
                cnt += 1
print(cnt)

Fixed submission:
k, s = map(int, input().split())
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y)
        if (0 <= z) and (z <= k):
            cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
x, y = map(int, input().split())

cnt = 0
t = x
while True:
    if t * y > 0:
        if t > 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t *= (-1)
                cnt += 1
        elif t < 0:
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) > abs(y):
                t += 1
                cnt += 1
    elif t * y < 0:
        if t > 0:
            if abs(t) >= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) < abs(y):
                t += 1
                cnt += 1
        elif t < 0:
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) > abs(y):
                t += 1
                cnt += 1
    else:
        #t * y == 0 
        if t == 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t += 1
                cnt += 1
        elif y == 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t *= (-1)
                cnt += 1
    if t == y:
        break
print(cnt)    

Fixed submission:
x, y = map(int, input().split())

cnt = 0
t = x
while True:
    if t > 0:
        if y >= 0:
            if t < y:
                cnt += y - t
                break
            elif t == y:
                break
            else:
                #t > y
                cnt += 1
                t *= (-1)               
        else:
            #y < 0
            #t > y
            if abs(t) >= abs(y):
                t *= (-1)
                cnt += 1
            else:
                #abs(t) < abs(y)
                cnt += (-1) * y - t
                t = (-1) * y
    elif t == 0:
        if y > 0:
            #t < y
            cnt += y - t
            break
        elif y == 0:
            #t == y
            break
        else:
            #y < 0
            #y < t
            #abs(t) < abs(y)
            cnt += (-1) * y - t
            t = (-1) * y
    else:
        #t < 0
        if y >= 0:
            #t < y
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            else:
                #abs(t) > abs(y)
                cnt += (-1) * y - t
                t = (-1) * y
        else:
            #y < 0
            if t < y:
                cnt += y - t
                break
            elif t == y:
                break
            else:
                #t > y
                cnt += 1
                t *= (-1)
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
def inpl(): return input().split()

n = int(input())
a = sorted(list(map(int, inpl())))

p = 10 ** 9 + 7

ans = 1
i = (n - 1) % 2
j = 0
while (i + j) < n:
    cnt = a.count(i + j)
    if (j % 2 == 0):
        if cnt != 2:
            if not((cnt == 1) and (((i + j) == 0) or ((i + j) == (n - 1)))):
                ans = 0
                break
        else:
            if ((i + j) == 0):
                ans = 0
                break
            else:
                ans *= cnt
                if ans > p:
                    ans %= p
    else:
        if cnt != 0:
            ans = 0
            break
    j += 1
print(ans)

Fixed submission:
def inpl(): return input().split()

n = int(input())
a = sorted(list(map(int, inpl())))
p = 10 ** 9 + 7

if a[0] == 0:
    st = 1
    next_value = 2
else:
    st = 0
    next_value = 1

ans = 1
found = False
for i in range(st, n):    
    if (next_value == a[i]):
        if found:
            next_value += 2
            found = False
            ans *= 2
            if ans > p:
                ans %= p
        else:
            found = True
    else:
        ans = 0
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import re

s = input()
flg = True
while flg:
    flg = False
    for rp in ['dream', 'dreamer', 'erase', 'eraser']:
        aft = re.sub(rp+'$', '', s)
        ##print(s,rp,aft, flg)
        if s != aft:
            s = aft
            flg = True
if s == '':
    print('YES')
else:
    print('NO')


Fixed submission:
s = input()
l = ['dream', 'dreamer', 'erase', 'eraser']
pos = 0
flg = True
can = False
while flg:
    flg = False
    for i in range(len(l)):
        st = len(l[i])+pos
        if st<=len(s):
            if s[st*(-1):len(s)-pos] == l[i]:
                pos += len(l[i])
                if pos == len(s):
                    can = True
                    break
                flg = True
if can == True:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
from string import ascii_lowercase

s = input()
k = int(input())

b = ord('a')

ret = ''
for c in s[:-1]:
    if c == 'a':
        ret += 'a'
        continue
    need = 26 - (ord(c) - b)
    if k >= need:
        k -= need
        ret += 'a'
    else:
        ret += c

k %= 26

c = s[-1]
ret += chr((ord(c) - b + k) % 26 + b)

print(ret)


Fixed submission:
s = input()
k = int(input())

num = [26 - i for i in range(26)]
num[0] = 10 ** 9 + 10

a_ = ord('a')

ans = ''
for c in s:
    x = ord(c) - a_
    if num[x] <= k:
        ans += 'a'
        k -= num[x]
    else:
        ans += c
k %= 26
if k > 0:
    c = ans[-1]
    ans = ans[:-1] + chr(a_ + ((ord(c) - a_ + k) % 26))
print(ans)
Buggy python submission (verdict: Runtime Error):
def ary3(x, y, z, v): return [[[v for _  in range(z)] for _ in range(y)] for _ in range(x)]

n, a = map(int, input().split())
x = list(map(int, input().split()))
m = max(x)
dp = ary3(n + 1, n + 1, m * n + 1, 0)#(選べる枚数（範囲）0 ~ n, 選んだ枚数0 ~ n, 合計0 ~ n * max(x)) = パターン数

for i in range(n + 1):
    dp[i][0][0] = 1

for i in range(1, n + 1):
    for j in range(1, i + 1):
        for s in range(m * n + 1):
            if s + x[i - 1] < m * n + 1:
                dp[i][j][s + x[i-1]] += dp[i - 1][j - 1][s]
            dp[i][j][s] += dp[i - 1][j][s]

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]

print(ans)


Fixed submission:
def na(): return map(int, input().split())
n, a = na()
x = list(na())
xa = list(map(lambda f: f-a, x))
'''
dp[i][点数] = パターン数
i番目まで使用したときの点数になるパターン数
'''
dp = [dict() for _ in range(n)]
if xa[0] == 0:
    dp[0][0] = 2
else:
    dp[0][0] = 1
    dp[0][xa[0]] = 1
for i in range(1, n):
    #xa[i]を採用する / 採用しないで2つに分岐
    #すべて採用しないと点数0になるので、最後に点数0になったパターン数から1引く
    for k, v in dp[i-1].items():#k:得点, v:パターン数
        score = xa[i] + k
        dp[i][score] = dp[i].get(score, 0) + v#xa[i]を採用
        dp[i][k] = dp[i].get(k, 0) + v#xa[i]を不採用
print(dp[n-1][0] - 1)

Buggy python submission (verdict: Time Limit Exceeded):
#部分点解法
def inpl(): return input().split()
n, a = map(int, inpl())
x = list(map(int, inpl()))
x_minus_a = list(map(lambda x: x - a, x))

cnt = 0
for i in range(1, 2 ** n):
    s = 0
    for j in range(n):
        if (2 ** j) & i != 0:
           s += x_minus_a[j] 
    if s == 0:
        cnt += 1
print(cnt)

Fixed submission:
def na(): return map(int, input().split())
n, a = na()
x = list(na())
xa = list(map(lambda f: f-a, x))
'''
dp[i][点数] = パターン数
i番目まで使用したときの点数になるパターン数
'''
dp = [dict() for _ in range(n)]
if xa[0] == 0:
    dp[0][0] = 2
else:
    dp[0][0] = 1
    dp[0][xa[0]] = 1
for i in range(1, n):
    #xa[i]を採用する / 採用しないで2つに分岐
    #すべて採用しないと点数0になるので、最後に点数0になったパターン数から1引く
    for k, v in dp[i-1].items():#k:得点, v:パターン数
        score = xa[i] + k
        dp[i][score] = dp[i].get(score, 0) + v#xa[i]を採用
        dp[i][k] = dp[i].get(k, 0) + v#xa[i]を不採用
print(dp[n-1][0] - 1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k != 1:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

for i in range(n):
	if x[i] == "0":
		targ = k+1
		print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
	else:
		targ = k-1
		print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)

Fixed submission:
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k >= 2:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)
else:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(0)

Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

for i in range(n):
	if x[i] == "0":
		targ = k+1
		print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
	else:
		targ = k-1
		print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)

Fixed submission:
n = int(input())
x = input()
k = x.count("1")
cnt = 0
s = int(x, 2)
if k >= 2:
	k1 = s % (k-1)
k2 = s % (k+1)
while s != 0:
	targ = bin(s).count("1")
	s = s % targ
	cnt += 1

def ev(n):
	cnt = 0
	while n != 0:
		m = bin(n).count("1")
		n = n % m
		cnt += 1
	return cnt

if k != 1:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(ev((k1-pow(2, n-i-1, targ)) % targ)+1)
else:
	for i in range(n):
		if x[i] == "0":
			targ = k+1
			print(ev((k2+pow(2, n-i-1, targ)) % targ)+1)
		else:
			targ = k-1
			print(0)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()
mod = 10**9 + 7
"""
組み合わせ大好きなのにFとけなかったくやしいいいいいいいいいいいいいいいい
"""

def cmb(n, r, mod):
	if (r < 0) or (n < r):
		return 0
	r = min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%mod

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

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

ans = 0
for i in range(k+1):
	ans = (ans + cmb(len(s)-1+k-i, len(s)-1, mod)*pow(25, k-i, mod)*pow(26, i, mod)) % mod
print(ans)

Fixed submission:
k = int(input())
s = input()
mod = 10**9 + 7
"""
組み合わせ大好きなのにFとけなかったくやしいいいいいいいいいいいいいいいい
"""

def cmb(n, r, mod):
	if (r < 0) or (n < r):
		return 0
	r = min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%mod

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

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

ans = 0
for i in range(k+1):
	ans = (ans + cmb(len(s)-1+k-i, len(s)-1, mod)*pow(25, k-i, mod)*pow(26, i, mod)) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np

p = 998244353

a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for k in range(c+1)]
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])

Fixed submission:

p = 998244353

a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for k in range(c+1)]
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])

Buggy python submission (verdict: Runtime Error):
import numpy as np

p = 998244353

a,b,c,d = map(int,input().split())
dp = np.zeros((c+1, d+1), dtype=np.int64)
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])

Fixed submission:

p = 998244353

a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for k in range(c+1)]
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for _ in range(n)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	b = [0 for _ in range(n)]
	alln = 0
	for i in range(n):
		if a[i] == n:
			alln += 1
		for j in range(max(i-a[i], 0), min(i+a[i]+1, n)):
			b[j] += 1
	if alln == n:
		break
	a = b[:]
print(*b)

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
imos = [0 for _ in range(n+1)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	imos = [0 for _ in range(n+1)]
	for i in range(n):
		imos[max(i-a[i], 0)] += 1
		imos[min(i+a[i]+1, n)] -= 1
	cnt = 0
	alln = 0
	for i in range(n):
		cnt += imos[i]
		a[i] = cnt
		if a[i] == n:
			alln += 1
	if alln == n:
		break
print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
	ans *= i
if ans <= 10**18:
	print(ans)
else:
	print(-1)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
ans=1

if 0 in a:
	print(0)
	exit()

for i in a:
	ans *= i
	if ans > 10**18:
		print(-1)
		exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
t=list(input())
ans = 0
for i in range(len(t)):
	if i != 0 and i != len(t)-1:
		if t[i] == "?":
			if t[i-1] == "P":
				t[i] = "D"
			elif t[i+1] == "D" or t[i+1] == "?":
				t[i] = "P"
			else:
				t[i] = "D"
	elif i==0:
		if t[i] == "?":
			if t[i+1] == "D" or t[i+1] == "?":
				t[i] = "P"
			else:
				t[i] = "D"
	else:
		if t[i] == "?":
			t[i] = "D"
print("".join(t))

Fixed submission:
t=list(input())
ans = 0
if len(t) != 1:
	for i in range(len(t)):
		if i != 0 and i != len(t)-1:
			if t[i] == "?":
				if t[i-1] == "P":
					t[i] = "D"
				elif t[i+1] == "D" or t[i+1] == "?":
					t[i] = "P"
				else:
					t[i] = "D"
		elif i==0:
			if t[i] == "?":
				if t[i+1] == "D" or t[i+1] == "?":
					t[i] = "P"
				else:
					t[i] = "D"
		else:
			if t[i] == "?":
				t[i] = "D"
else:
	if t[0] == "?":
		t[0] = "D"
print("".join(t))

Buggy python submission (verdict: Runtime Error):
t=list(input())
ans = 0
for i in range(len(t)):
	if i != 0 and i != len(t)-1:
		if t[i] == "?":
			if t[i-1] == "P":
				t[i] = "D"
			elif t[i+1] == "D" or "?":
				t[i] = "P"
			else:
				t[i] = "D"
	elif i==0:
		if t[i] == "?":
			if t[i+1] == "D" or "?":
				t[i] = "P"
			else:
				t[i] = "D"
	else:
		if t[i] == "?":
			t[i] = "D"
print("".join(t))

Fixed submission:
t=list(input())
ans = 0
if len(t) != 1:
	for i in range(len(t)):
		if i != 0 and i != len(t)-1:
			if t[i] == "?":
				if t[i-1] == "P":
					t[i] = "D"
				elif t[i+1] == "D" or t[i+1] == "?":
					t[i] = "P"
				else:
					t[i] = "D"
		elif i==0:
			if t[i] == "?":
				if t[i+1] == "D" or t[i+1] == "?":
					t[i] = "P"
				else:
					t[i] = "D"
		else:
			if t[i] == "?":
				t[i] = "D"
else:
	if t[0] == "?":
		t[0] = "D"
print("".join(t))