Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

H, W = map(int, input().split())
s = [""] * H
for i in range(H):
  s[i] = input()

res = H*W
induce = ["r"]*(H-1) + ["c"]*(W-1)
M = len(induce)
perm_iter = itertools.permutations(induce)
for i, perm in enumerate(perm_iter):
  route = ""
  r, c = 0, 0
  route += s[0][0]
  for j in range(M):
    if perm[j] == "r":
      r += 1
    elif perm[j] == "c":
      c += 1
    route += s[r][c]
  
  cnt = route.split(".")
  cnt = len(cnt) - cnt.count("")
  if cnt < res:
    res = cnt
  
print(res)  


Fixed submission:
H, W = map(int, input().split())
s = [""] * H
for h in range(H):
  s[h] = input()

INF = float('inf')
dp = [[[INF, s[h][w]] for w in range(W)] for h in range(H)]

def update_dp_1(c, dp):
  if dp[1] == ".":
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0]+1, "#"]
  else:  # dp[1] == "#"
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0], "#"]
  return res

def update_dp_2(c, dp_a, dp_b):
  a = update_dp_1(c, dp_a)
  b = update_dp_1(c, dp_b)
  if a[0] < b[0]:
    return a
  else:
    return b

if s[0][0] == ".":
  dp[0][0] = [0, "."]
else:  #  == "#"
  dp[0][0] = [1, "#"]

for h in range(H):
  if h != 0:
    dp[h][0] = update_dp_1(dp[h][0][1], dp[h-1][0])
  for w in range(1, W):
    if h == 0:
      dp[h][w] = update_dp_1(dp[h][w][1], dp[h][w-1])
    else:
      dp[h][w] = update_dp_2(dp[h][w][1], dp[h-1][w], dp[h][w-1])

print(dp[H-1][W-1][0])
Buggy python submission (verdict: Runtime Error):
import math

al = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

N = int(input())
S = [[""] * math.factorial(i+1) for i in range(N-1)]

S[0][0] = al[0]
for i in range(1, N-1):
  prev_S = S[i-1]
  al_use = al[:i+1]
  S[i] = [s + a for s in prev_S for a in al_use]

prev_S = S[N-2]
al_use = al[:N]
for s in prev_S:
  for a in al_use:
    print(s + a)


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline


def dfs(N):
    alphabet = "abcdefghij"
    stack = deque(["a"])
    while stack:
        s = stack.pop()
        if len(s) == N:
            print(s)
            continue
        suffixes = []
        for al in alphabet:
            suffixes.append(al)
            if al not in s:
                break
        for suffix in reversed(suffixes):
            stack.append("".join((s, suffix)))


def main():
    N = int(input())

    dfs(N)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B = [int(i) for i in input().strip().split()]
res = 0
cnt = 0
AorB = "A"
while True:
  if AorB == "A":
    if cnt + A < N:
      res += A
      cnt += A
      AorB = "B"
    else:
      res += (N - cnt)
      break
  else:
    cnt += B
    AorB = "A"
    if cnt >= N:
      break

print(res)


Fixed submission:
N, A, B = [int(i) for i in input().strip().split()]
q, r = divmod(N, A+B)
if r <= A:
  print(A*q + r)
else:
  print(A*q + A)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()
    Q = int(input())
    query = [None] * Q
    for i in range(Q):
        query[i] = input().split()

    ans = S
    is_reversed = False
    for q in query:
        if int(q[0]) == 1:
            is_reversed = not is_reversed
        else:
            F, C = int(q[1]), q[2]
            if F == 1:
                if is_reversed:
                    ans = "".join([ans, C])
                else:
                    ans = "".join([C, ans])
            else:
                if is_reversed:
                    ans = "".join([C, ans])
                else:
                    ans = "".join([ans, C])

    if is_reversed:
        ans = ans[::-1]

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
S = input().strip()
Q = int(input())
is_reverse = False
A = ""
B = ""
for i in range(Q):
  query = [j for j in input().strip().split()]
  T = int(query[0])
  if T == 1:
    is_reverse = not is_reverse
  else:
    F, C = int(query[1]), query[2]
    if F == 1:
      if not is_reverse:
        A = C + A
      else:
        B = B + C
    else:
      if not is_reverse:
        B = B + C
      else:
        A = C + A

res = A + S + B
if not is_reverse:
  print(res)
else:
  print(res[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
S = input().strip()
Q = int(input())
for i in range(Q):
  query = [j for j in input().strip().split()]
  T = int(query[0])
  if T == 1:
    S = S[::-1]
  else:
    F, C = int(query[1]), query[2]
    if F == 1:
      S = C + S
    else:
      S = S + C
print(S)


Fixed submission:
S = input().strip()
Q = int(input())
is_reverse = False
A = ""
B = ""
for i in range(Q):
  query = [j for j in input().strip().split()]
  T = int(query[0])
  if T == 1:
    is_reverse = not is_reverse
  else:
    F, C = int(query[1]), query[2]
    if F == 1:
      if not is_reverse:
        A = C + A
      else:
        B = B + C
    else:
      if not is_reverse:
        B = B + C
      else:
        A = C + A

res = A + S + B
if not is_reverse:
  print(res)
else:
  print(res[::-1])
Buggy python submission (verdict: Runtime Error):
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(M):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]] != c[j]:
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)


Fixed submission:
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(M):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]-1] != str(c[j]):
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(N):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]] != c[j]:
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)


Fixed submission:
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(M):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]-1] != str(c[j]):
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(N):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(N):
    if S[s[j]] != c[j]:
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)


Fixed submission:
N, M = [int(i) for i in input().split()]
s = [0] * M
c = [0] * M
for i in range(M):
  s[i], c[i] = map(int, input().split())

ans = 1000
for i in range(1000):
  S = str(i)
  if len(S) != N:
    continue
  
  is_ok = True
  for j in range(M):
    if S[s[j]-1] != str(c[j]):
      is_ok = False
      
  if is_ok:
    ans = min(ans, i)

if ans == 1000:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(N)
ans = "x" * N
print(ans)

Fixed submission:
import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()

    N = len(S)
    ans = "x" * N

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

E = [0] * N
for i in range(N):
  E[i] = (1+p[i])/2

ans = 0
for i in range(N-K+1):
  e = 0
  for j in range(i, i+K):
    e += E[j]
  if ans < e:
    ans = e
    
print(ans)


Fixed submission:
N, K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

E = [0] * N
for i in range(N):
  E[i] = (1+p[i])/2

e = sum(E[:K])
ans = e
for i in range(1, N-K+1):
  e = e - E[i-1] + E[i+K-1]
  if ans < e:
    ans = e
    
print(ans)
Buggy python submission (verdict: Runtime Error):
import string

AL = string.lowercase

C = input()
idx = AL.find(C)
idy = (idx + 1) % 26
print(AL[idy])


Fixed submission:
import string

AL = string.ascii_lowercase

C = input()
idx = AL.find(C)
idy = (idx + 1) % 26
print(AL[idy])
Buggy python submission (verdict: Time Limit Exceeded):
import re

N = int(input())
S = input()

res = 0
fmt = "[0-9]*{}[0-9]*{}[0-9]*{}[0-9]*"
for i in range(1000):
  s = "{:03}".format(i)
  if re.search(fmt.format(s[0], s[1], s[2]), S):
    res += 1

print(res)


Fixed submission:
import re

N = int(input())
S = input()

res = 0
fmt = "[0-9]*{}[0-9]*{}[0-9]*{}[0-9]*"
for i in range(10):
  idx_1 = S.find(str(i))
  if (idx_1 == -1) or (idx_1 > N-3):
    continue
  for j in range(10):
    idx_2 = S[idx_1+1:].find(str(j))
    if (idx_2 == -1) or (idx_2 > N-2):
      continue
    for k in range(10):
      idx_3 = S[idx_1+1+idx_2+1:].find(str(k))
      if idx_3 != -1:
        res += 1

print(res)
Buggy python submission (verdict: Runtime Error):
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
ind = daw.index(S)
print(7 - idx)


Fixed submission:
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
idx = daw.index(S)
print(7 - idx)

Buggy python submission (verdict: Runtime Error):
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
ind = daw.find(S)
print(7 - idx)


Fixed submission:
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
idx = daw.index(S)
print(7 - idx)

Buggy python submission (verdict: Runtime Error):
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
ind = S.find(daw)
print(7 - idx)


Fixed submission:
daw = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
idx = daw.index(S)
print(7 - idx)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7

def make_fac_tables_mod_p(n, p):
  fac = [0] * (n+1)
  fac_inv = [0] * (n+1)
  mod_inv = [0] * (n+1)
  fac[0] = fac[1] = 1
  fac_inv[0] = fac_inv[1] = 1
  mod_inv[1] = 1
  for i in range(2, n+1):
    fac[i] = (fac[i-1] * i) % p
    mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
    fac_inv[i] = fac_inv[i-1] * mod_inv[i] % p
  return fac, fac_inv

def nCk_mod_p(fac, fac_inv, n, k, p):
  return ((fac[n] * fac_inv[n-k]) % p) * fac_inv[k] % p

X, Y = map(int, input().split())

ans = 0
q, r = divmod(X+Y, 3)
if r == 0:
  n = q
  k = X - q
  fac, fac_inv = make_fac_tables_mod_p(n, MOD)
  ans = nCk_mod_p(fac, fac_inv, n, k, MOD)

print(ans)


Fixed submission:
MOD = 10**9 + 7

def make_fac_tables_mod_p(n, p):
  fac = [0] * (n+1)
  fac_inv = [0] * (n+1)
  mod_inv = [0] * (n+1)
  fac[0] = fac[1] = 1
  fac_inv[0] = fac_inv[1] = 1
  mod_inv[1] = 1
  for i in range(2, n+1):
    fac[i] = (fac[i-1] * i) % p
    mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
    fac_inv[i] = fac_inv[i-1] * mod_inv[i] % p
  return fac, fac_inv

def nCk_mod_p(fac, fac_inv, n, k, p):
  return ((fac[n] * fac_inv[n-k]) % p) * fac_inv[k] % p

X, Y = map(int, input().split())

ans = 0
q, r = divmod(X+Y, 3)
if r == 0 and (q <= X <= 2*q) and (q <= Y <= 2*q):
  n = q
  k = X - q
  fac, fac_inv = make_fac_tables_mod_p(n, MOD)
  ans = nCk_mod_p(fac, fac_inv, n, k, MOD)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
from functools import reduce
from operator import mul


def trial_division(n):
  factors = []
  f = 2
  while f**2 <= n:
    if n % f == 0:
      n //= f
      factors.append(f)
    else:
      f += 1
  if n != 1:
    factors.append(n)
  return factors

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  res = N
  cumsum = reduce(mul, factors)
  for i in range(len(factors)//2):
    for comb in itertools.combinations(factors, i+1):
      a = reduce(mul, comb)
      b = cumsum // a
      if a+b-2 < res:
        res = a+b-2
  print(res)


Fixed submission:
N = int(input())

ans = N**2
for i in range(1, int(N**(1/2))+1):
  if N % i == 0:
    j = N // i
    ans = min(ans, (i-1)+(j-1))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def binary_search(K, A, F):
    ng = -1
    ok = 10 ** 18
    while ok - ng > 1:
        mid = (ok + ng) // 2
        need_k = sum(max(0, a - mid // f) for a, f in zip(A, F))
        if need_k <= K:
            ok = mid
        else:
            ng = mid
    return ok


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

    A.sort()
    F.sort(reverse=True)

    ans = binary_search(K, A, F)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8[:],i8[:])", cache=True)
def binary_search(K, A, F):
    """Meguru type binary search"""
    ng = -1
    ok = 10 ** 12

    def is_ok(A, F, K, x):
        count = 0
        for a, f in zip(A, F):
            count += max(0, a - x // f)
        return count <= K

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(A, F, K, mid):
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
    F = np.array(input().split(), dtype=np.int64)

    A.sort()
    F[::-1].sort()

    ans = binary_search(K, A, F)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split()]

res = [""] * N
for i in range(N):
  res[A[i]-1] = i+1

print(" ".join(res))


Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]

res = [""] * N
for i in range(N):
  res[A[i]-1] = str(i+1)

print(" ".join(res))
Buggy python submission (verdict: Runtime Error):
N = int(input())
B = [int(i) for i in input().split()]

res = 0
for i in range(N-1):
  res += min(B[i], B[i+1])
res += B[-1]

print(res)


Fixed submission:
N = int(input())
B = [int(i) for i in input().split()]

res = B[0]
for i in range(N-2):
  res += min(B[i], B[i+1])
res += B[-1]

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == "?":
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            d = int(D)
            for j in range(Q):
                dp[i + 1][(10 * j + d) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

    ans = dp[N][5]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        base = pow(10, N - 1 - i, Q)
        D = S[i]
        if D == "?":
            for d in range(10):
                n = d * base
                for j in range(Q):
                    next_j = (j + n) % Q
                    dp[i + 1][next_j] += dp[i][j]
                    dp[i + 1][next_j] %= P
        else:
            n = int(D) * base
            for j in range(Q):
                next_j = (j + n) % Q
                dp[i + 1][(j + n) % Q] += dp[i][j]
                dp[i + 1][(j + n) % Q] %= P

    ans = dp[N][5]
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        base = pow(10, N - 1 - i, Q)
        D = S[i]
        if D == "?":
            for d in range(10):
                n = d * base
                for j in range(Q):
                    next_j = (j + n) % Q
                    dp[i + 1][next_j] += dp[i][j]
                    dp[i + 1][next_j] %= P
        else:
            n = int(D) * base
            for j in range(Q):
                next_j = (j + n) % Q
                dp[i + 1][(j + n) % Q] += dp[i][j]
                dp[i + 1][(j + n) % Q] %= P

    ans = dp[N][5]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


def main():
    S = input().rstrip()

    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        base = pow(10, N - 1 - i, Q)
        D = S[i]
        if D == "?":
            for d in range(10):
                n = d * base
                for j in range(Q):
                    next_j = (j + n) % Q
                    dp[i + 1][next_j] += dp[i][j]
                    dp[i + 1][next_j] %= P
        else:
            n = int(D) * base
            for j in range(Q):
                next_j = (j + n) % Q
                dp[i + 1][(j + n) % Q] += dp[i][j]
                dp[i + 1][(j + n) % Q] %= P

    ans = dp[N][5]
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 2019

L, R = [int(i) for i in input().strip().split()]

res = R*R
for i in range(L, R):
  for j in range(i+1, R+1):
    _, r = divmod(i*j, MOD)
    if r < res:
      res = r
print(res)


Fixed submission:
MOD = 2019

L, R = [int(i) for i in input().strip().split()]

if (L // MOD) != (R // MOD):
  print(0)
else:
  res = R*R
  for i in range(L, R):
    for j in range(i+1, R+1):
      _, r = divmod(i*j, MOD)
      if r < res:
        res = r
  print(res)
Buggy python submission (verdict: Runtime Error):
S = input()
S = sorted(S)
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else
  print("No")


Fixed submission:
S = input()
S = sorted(S)
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
S = input()
S.sort()
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else
  print("No")


Fixed submission:
S = input()
S = sorted(S)
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
S = [i for i in input().strip().split()]
S.sort()
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else
  print("No")


Fixed submission:
S = input()
S = sorted(S)
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict
from itertools import combinations

input = sys.stdin.readline


def main():
    N = int(input())
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())

    vector = defaultdict(int)
    for a, b in combinations(range(N), 2):
        dx = x[a] - x[b]
        dy = y[a] - y[b]
        if dx == 0:
            vector[(0, abs(dy))] += 1
        elif dx > 0:
            vector[(dx, dy)] += 1
        else:
            vector[(-dx, -dy)] += 1

    ans = N - max(vector.values())
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import defaultdict
from itertools import combinations

input = sys.stdin.readline


def main():
    N = int(input())
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())

    if N == 1:
        print(1)
        sys.exit()

    vector = defaultdict(int)
    for a, b in combinations(range(N), 2):
        dx = x[a] - x[b]
        dy = y[a] - y[b]
        if dx == 0:
            vector[(0, abs(dy))] += 1
        elif dx > 0:
            vector[(dx, dy)] += 1
        else:
            vector[(-dx, -dy)] += 1

    ans = N - max(vector.values())
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    A = [0] * M
    for i in range(M):
        A[i] = int(input())

    is_ok = True
    for i in range(M - 1):
        if A[i] + 1 == A[i + 1]:
            is_ok = False
    if not is_ok:
        print(0)
        exit()

    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True

    dp = [0] * (N + 1)
    dp[0] = 1
    dp[1] = 1 if A[0] != 1 else 0

    for i in range(2, N + 1):
        if broken[i]:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % P
    
    ans = dp[N]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
MOD = 10**9 + 7

N, M = [int(i) for i in input().strip().split()]
dirty_step_idxs = [0] * M
for i in range(M):
  dirty_step_idx = int(input())
  dirty_step_idxs[i] = dirty_step_idx

def fibonacci(n):
  # 0, 1, 1, 2, 3, 5, 8, ...
  a, b = 0, 1
  for i in range(n-1):
    a, b = b, a + b
  return a
  
if M == 0:
  res = fibonacci(N + 2)
else:
  res = 1
  now_step_idx = 0
  for i in range(M):
    n_step = dirty_step_idxs[i] - now_step_idx - 1
    if n_step == -1:
      res = 0
      break
    res *= fibonacci(n_step + 2)
    now_step_idx = dirty_step_idxs[i] + 1
  rest_steps = N - now_step_idx
  res *= fibonacci(rest_steps + 2) 
    
print(res % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(N, a, i, b, procedure):
    if i == 0:
        return procedure

    for j in range(1, i+1):
        if a[j-1] == j:
            l = a[:]
            del l[j-1]
            p = procedure[:]
            p.append(j)
            ret = dfs(N, l, i-1, b, p)
            if ret is not None:
                return ret


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

    res = dfs(N, b, N, b, [])
    if res is None:
        print(-1)
    else:
        print(*res[::-1], sep="\n")


if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA


def dfs(N, a, i, procedure):
    if i == 0:
        return procedure

    for j in reversed(range(1, i+1)):
        if a[j-1] == j:
            l = a[:]
            del l[j-1]
            p = procedure[:]
            p.append(j)
            ret = dfs(N, l, i-1, p)
            if ret is not None:
                return ret
            break


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

    res = dfs(N, b, N, [])
    if res is None:
        print(-1)
    else:
        print(*res[::-1], sep="\n")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import Counter
from itertools import product

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    S = input().rstrip()

    c = Counter(S)
    values = list(c.values())
    ans = -1
    for comb in product(range(2), repeat=len(values)):
        res = 1
        for i, c in enumerate(comb):
            if c == 1:
                res = (res * values[i]) % P
        ans = (ans + res) % P

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import Counter

input = sys.stdin.readline
P = 10**9 + 7


def main():
    N = int(input())
    S = input().rstrip()

    # Editorial AC
    c = Counter(S)
    ans = 1
    for v in c.values():
        ans = (ans * (v + 1)) % P
    ans = (ans - 1) % P

    print(ans)


if __name__ == "__main__":
    main()