Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
ANS = [-1]*(n+1)
P = []
L = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())

    if a == 1:
        ANS[b] = 1
        P.append(b)
    elif b == 1:
        ANS[a] = 1
        P.append(a)
    else:    
        L[a].append(b)
        L[b].append(a)

# print(L, ANS, P)

i = 0
while len(P) < n-1:
    for j in range(1, n+1):
        if P[i] in L[j] and ANS[j] == -1:
            P.append(j)
            L[j].remove(P[i])
            ANS[j] = P[i]
            # print(i, P[i], j, L, ANS, P)
    i += 1

print('Yes')
for i in range(2, n+1):
    print(ANS[i])


Fixed submission:
s = input()
if s[-1] == '3':
    print('bon')
elif s[-1]=='0' or s[-1]=='1' or s[-1]=='6' or s[-1]=='8':
    print('pon')
else:
    print('hon')
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
ANS = [-1]*(n+1)
P = []
L = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())

    if a == 1:
        ANS[b] = 1
        P.append(b)
    elif b == 1:
        ANS[a] = 1
        P.append(a)
    else:    
        L[a].append(b)
        L[b].append(a)

# print(L, ANS, P)

i = 0
while len(P) < n-1:
    for j in range(1, n+1):
        if P[i] in L[j] and ANS[j] == -1:
            P.append(j)
            L[j].remove(P[i])
            ANS[j] = P[i]
            # print(i, P[i], j, L, ANS, P)
    i += 1

print('Yes')
for i in range(2, n+1):
    print(ANS[i])


Fixed submission:
from collections import deque
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

# 幅優先探索
d = deque([0])
D = [-1] * n
D[0] = 0
while len(d) > 0 :
    t = d.popleft()
    for i in L[t]:
        if D[i] == -1:
            D[i] = t
            d.append(i)
            # print(d, D)

print('Yes')
for i in range(1, n):
    print(D[i]+1)
Buggy python submission (verdict: Runtime Error):
n, k  = map(int, input().split())
A = list(map(int, input().split()))

# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))
# print(A)

# 通ったことのある場所を持っておく
ROUTE = [0]
t = A[0]
while not (t in ROUTE):
    ROUTE.append(t)
    t = A[t]


x=ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x
# print(ROUTE, length)

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)


# 再び町1に戻ってくるまでの経路を調べる
# ROUTE = [0]
# t = A[0] # 現在地
# while t != 0:
#     ROUTE.append(t)
#     t = A[t]
# # print(ROUTE)

# length = len(ROUTE)
# print(ROUTE[k % length]+1)

Fixed submission:
s = input()
t = input()
if s == t[:-1]:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n, k  = map(int, input().split())
A = list(map(int, input().split()))

# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))
# print(A)

# 通ったことのある場所を持っておく
ROUTE = [0]
t = A[0]
while not (t in ROUTE):
    ROUTE.append(t)
    t = A[t]


x=ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x
# print(ROUTE, length)

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)


# 再び町1に戻ってくるまでの経路を調べる
# ROUTE = [0]
# t = A[0] # 現在地
# while t != 0:
#     ROUTE.append(t)
#     t = A[t]
# # print(ROUTE)

# length = len(ROUTE)
# print(ROUTE[k % length]+1)

Fixed submission:
n, k  = map(int, input().split())
A = list(map(int, input().split()))
# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))

# 通ったことのある場所を持っておく
R = [0]*n
R[0] = 1
ROUTE = [0]
t = A[0]
while R[t] == 0:
    ROUTE.append(t)
    R[t] = 1
    t = A[t]

x = ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)

Buggy python submission (verdict: Time Limit Exceeded):
n, k  = map(int, input().split())
A = list(map(int, input().split()))

# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))
# print(A)

# 通ったことのある場所を持っておく
ROUTE = [0]
t = A[0]
while not (t in ROUTE):
    ROUTE.append(t)
    t = A[t]


x=ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x
# print(ROUTE, length)

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)


# 再び町1に戻ってくるまでの経路を調べる
# ROUTE = [0]
# t = A[0] # 現在地
# while t != 0:
#     ROUTE.append(t)
#     t = A[t]
# # print(ROUTE)

# length = len(ROUTE)
# print(ROUTE[k % length]+1)

Fixed submission:
n, k  = map(int, input().split())
A = list(map(int, input().split()))
# リストを扱いやすいように変形
def subtraction(x):
    return x - 1
A = list(map(subtraction, A))

# 通ったことのある場所を持っておく
R = [0]*n
R[0] = 1
ROUTE = [0]
t = A[0]
while R[t] == 0:
    ROUTE.append(t)
    R[t] = 1
    t = A[t]

x = ROUTE.index(t) # ループのスタート地点
length = len(ROUTE) - x

if k < x:
    print(ROUTE[k]+1)
else:
    k = k - x
    s = k % length
    print(ROUTE[x + s]+1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

B = []
for j in range(n):
    B.append(j - A[j])

count = 0

for i in range(n):
    b = i + A[i]
    count += B[(i+1):].count(b)

print(count)

Fixed submission:
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))

B = []
for j in range(n):
    B.append(j - A[j])

C = []
for i in range(n):
    C.append(i + A[i])

d = defaultdict(int)

for j in C:
    d[j] += 1

count = 0
for k in B:
    count += d[k]

print(count)

# 時間超過
# count = 0
# for i in range(n):
#     b = i + A[i]
#     count += B[(i+1):].count(b)
# print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

B = []
for j in range(n):
    B.append(j - A[j])

count = 0

for i in range(n):
    b = i + A[i]
    count += B[(i+1):].count(b)

print(count)

Fixed submission:
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))

B = []
for j in range(n):
    B.append(j - A[j])

C = []
for i in range(n):
    C.append(i + A[i])

d = defaultdict(int)

for j in C:
    d[j] += 1

count = 0
for k in B:
    count += d[k]

print(count)

# 時間超過
# count = 0
# for i in range(n):
#     b = i + A[i]
#     count += B[(i+1):].count(b)
# print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
a, b, n = map(int, input().split())

if n < b:
    ans = a * n // b  
    print(ans)
    sys.exit()  
elif n == b:
    ans = a * (b-1) // b
    print(ans)
    sys.exit()

# n == 1のときは0 問題なし
r = n // b
ans = 0
for i in range(1, r + 1):
    t = i * b - 1
    ans_t = a * t // b - (a * (i - 1))
    ans = max(ans, ans_t) 
    # print(i, t, ans)

t = r * b - 1
ans_t = a * t // b - (a * (r - 1))
ans = max(ans, ans_t) 

ans_t = a * n // b - (a * (n // b))
ans = max(ans, ans_t) 

print(ans)

Fixed submission:
import sys
a, b, n = map(int, input().split())

if n < b:
    ans = a * n // b  
    print(ans)
    sys.exit()  
elif n == b:
    ans = a * (b-1) // b
    print(ans)
    sys.exit()

# n == 1のときは0 問題なし
r = n // b
ans = 0
# for i in range(1, r + 1):
#     t = i * b - 1
#     ans_t = a * t // b - (a * (i - 1))
#     ans = max(ans, ans_t) 
    # print(i, t, ans)

t = r * b - 1
ans_t = a * t // b - (a * (r - 1))
ans = max(ans, ans_t) 

ans_t = a * n // b - (a * (n // b))
ans = max(ans, ans_t) 

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
a, b, n = map(int, input().split())

r = n // b
ans = 0

for i in range(1, r + 1):
    t = i * b - 1
    ans_t = a * t // b - (a * (i - 1))
    ans = max(ans, ans_t) 
    # print(i, t, ans)

ans_t = a * n // b - (a * (n // b))
ans = max(ans, ans_t) 

print(ans)

Fixed submission:
import sys
a, b, n = map(int, input().split())

if n < b:
    ans = a * n // b  
    print(ans)
    sys.exit()  
elif n == b:
    ans = a * (b-1) // b
    print(ans)
    sys.exit()

# n == 1のときは0 問題なし
r = n // b
ans = 0
# for i in range(1, r + 1):
#     t = i * b - 1
#     ans_t = a * t // b - (a * (i - 1))
#     ans = max(ans, ans_t) 
    # print(i, t, ans)

t = r * b - 1
ans_t = a * t // b - (a * (r - 1))
ans = max(ans, ans_t) 

ans_t = a * n // b - (a * (n // b))
ans = max(ans, ans_t) 

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d *= 10

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Fixed submission:
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
for i in range(n):
    t = int(string[i])*(10**i)+S[i]
    t = t % 2019
    S.append(t)

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Fixed submission:
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import math
# 整数の入力
n = int(input())
s = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            gcd = math.gcd(math.gcd(i, j),k)
            s += gcd
print(s)

Fixed submission:
# -*- coding: utf-8 -*-
import math
# 整数の入力
n = int(input())
s = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        for k in range(j, n + 1):
            gcd = math.gcd(math.gcd(i, j),k)
            if i == j and j == k:
                s += gcd
            elif i == j or j == k or k ==i:
                s += gcd * 3
            else:
                s += gcd * 6
# for i in range(1, n + 1):
#     for j in range(1, n + 1):
#         for k in range(1, n + 1):
#             gcd = math.gcd(math.gcd(i, j),k)
#             s += gcd
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
# 整数の入力
n = int(input())
# 文字列の入力
s = input()
# 数え上げ
count = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            if s[i] != 'R' and s[j] != 'R':
                C = 'R'
            elif s[i] != 'G' and s[j] != 'G':
                C = 'G'
            else:
                C = 'B'
            count += s.count(C, j+1, 2*j - i)
            count += s.count(C, 2*j - i + 1)
print(count)

Fixed submission:
n = int(input())
s = input()
count = s.count("R")*s.count("G")*s.count("B")
for i in range(n-2):
    for j in range(i+1, (i+n+1)//2):
        if s[j] != s[i] and s[j] != s[2*j-i] and s[i] != s[2*j-i]:
            count -= 1
        # print(i, j, 2*j-i, count)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
# 整数の入力
n = int(input())
# 文字列の入力
s = input()
# 数え上げ
count = 0
# for i in range(n):
#     for j in range(i+1, n):
#         for k in range(j+1, n):
#             if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
#                 count +=1
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            for k in range(j+1, n):
                if s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                    count +=1
print(count)

Fixed submission:
n = int(input())
s = input()
count = s.count("R")*s.count("G")*s.count("B")
for i in range(n-2):
    for j in range(i+1, (i+n+1)//2):
        if s[j] != s[i] and s[j] != s[2*j-i] and s[i] != s[2*j-i]:
            count -= 1
        # print(i, j, 2*j-i, count)
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
# 整数の入力
n = int(input())
# 文字列の入力
s = input()
# 数え上げ
count = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                count +=1
print(count)

Fixed submission:
n = int(input())
s = input()
count = s.count("R")*s.count("G")*s.count("B")
for i in range(n-2):
    for j in range(i+1, (i+n+1)//2):
        if s[j] != s[i] and s[j] != s[2*j-i] and s[i] != s[2*j-i]:
            count -= 1
        # print(i, j, 2*j-i, count)
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n, g = map(int, input().split())
L = []
for i in range(n):
    t = list(map(int, input().split()))
    # 得点の情報を追加
    t.append((i+1)*100)
    L.append(t)

ans = 100 * n
for v in itertools.permutations(L):
    # print(v)
    score = 0
    count = 0
    k = 0
    p = v[k][0]
    while score < g:
        score += v[k][2]
        p -= 1
        count += 1
        if p == 0:
            score += v[k][1]
            k += 1
            if k < n:
                p = v[k][0]
        # print(v,count,score,k,p)
    ans = min(ans, count)
print(ans)

# ミス
# P = []
# G = []
# for i in range(n):
#     s, t = map(int, input().split())
#     P.insert(0, s)
#     G.insert(0, t//100)
# score = 0
# k = 0
# count = 0
# while score < g:
#     count += 1
#     if 1 in P:
#         j = P.index(1)
#         score += n-j + G[j]
#         P[j] = 0
#         if j == k:
#             k += 1
#     else:
#         score += n-k
#         P[k] -= 1
#     print(P,G,score,count,k)
# print(count)

Fixed submission:
import itertools
n, g = map(int, input().split())
L = []
for i in range(n):
    t = list(map(int, input().split()))
    # 配点
    t.append((i+1)*100)
    # この配点の問題を全部解いた時の得点
    t.append((i+1)*100*t[0]+t[1])
    L.append(t)
# print(L)

ans = g//100
# https://img.atcoder.jp/abc104/editorial.pdf bit全探索
for i in range(2**n):
    count = 0
    score = 0
    m = 0
    for j in range(n):
        if (i >> j) & 1:
            score += L[j][3]
            count += L[j][0]
        else:
            m = j
    # print(bin(i), m, score, count)
    if score >= g:
        ans = min(ans, count)
    else: # 解いていない配点の問題の中で一番配点が高いもの
        if (g - score)/L[m][2] <= L[m][0] and (g - score)%L[m][2] == 0:
            count += (g - score)//L[m][2]
        elif (g - score)/L[m][2] + 1 <= L[m][0]:
            count += ((g - score)//L[m][2])+1
        else:
            count = g//100
        ans = min(ans, count)
    # print(bin(i), m, L[m], score, count)
print(ans)

# 全探索したら時間超過
# ans = 100 * n
# for v in itertools.permutations(L):
#     score = 0
#     count = 0
#     k = 0
#     p = v[k][0]
#     while score < g:
#         score += v[k][2]
#         p -= 1
#         count += 1
#         if p == 0:
#             score += v[k][1]
#             k += 1
#             if k < n:
#                 p = v[k][0]
#     ans = min(ans, count)
# print(ans)

# DPっぽく解こうとしたけど失敗
# P = []
# G = []
# for i in range(n):
#     s, t = map(int, input().split())
#     P.insert(0, s)
#     G.insert(0, t//100)
# score = 0
# k = 0
# count = 0
# while score < g:
#     count += 1
#     if 1 in P:
#         j = P.index(1)
#         score += n-j + G[j]
#         P[j] = 0
#         if j == k:
#             k += 1
#     else:
#         score += n-k
#         P[k] -= 1
#     print(P,G,score,count,k)
# print(count)
Buggy python submission (verdict: Runtime Error):
# ACB054C
n, m = map(int, input().split())
L = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

ans = 0
def f(t, history):
    history[t] += 1
    his = history[:]
    global ans
    if sum(his) == n:
        ans += 1
    else:
        
        for i in L[t]:
            if his[i] == 0:
                f(i, his)
            
f(0, [0]*n)
print(ans)


Fixed submission:
# ACB054A
a, b = map(int, input().split())
if a == b:
    print("Draw")
elif a == 1:
    print("Alice")
elif b == 1:
    print("Bob")
elif a > b:
    print("Alice")
else:
    print("Bob")
Buggy python submission (verdict: Runtime Error):
import bisect


h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

ans = ch_max + cw_max
for (y, x) in points:
    index = bisect.bisect_left(ys, y)
    if ys[index] == y and xs[index] == x:
        ans -= 1
        break

print(ans)



Fixed submission:
h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

    
ans = ch_max + cw_max
if len(ys) * len(xs) <= m:
    def _find():
        for x in xs:
            for y in ys:
                if (y, x) not in points:
                    return True
        return False
    if not _find():
        ans -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

ans = 0
for x in xs:
    for y in ys:
        if (y, x) in points:
            ans = max(ans, count_h[y] + count_w[x] - 1)
        else:
            ans = max(ans, count_h[y] + count_w[x])
print(ans)



Fixed submission:
h, w, m = map(int, input().split())

count_h = [0 for i in range(h)]
count_w = [0 for i in range(w)]
points = set()
for i in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    points.add((y, x))
    count_h[y] += 1
    count_w[x] += 1

ch_max, cw_max = max(count_h), max(count_w)
ys = [y for y in range(len(count_h)) if count_h[y] == ch_max]
xs = [x for x in range(len(count_w)) if count_w[x] == cw_max]

    
ans = ch_max + cw_max
if len(ys) * len(xs) <= m:
    def _find():
        for x in xs:
            for y in ys:
                if (y, x) not in points:
                    return True
        return False
    if not _find():
        ans -= 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
As = set(As)
MOD = 1000000007

cache = dict()
def n_steps(n):
    if n not in cache:
        if n in As:
            value = 0
        
        elif n in {0, 1}:
            value = 1

        else:
            value = n_steps(n - 1) + n_steps(n - 2)
            value %= MOD

        cache[n] = value
    return cache[n]


print(n_steps(N))

Fixed submission:
N, M = map(int, input().split())
As = [int(input()) for i in range(M)]
As = set(As)
MOD = 1000000007

cache = dict()
def n_steps(n):
    if n not in cache:
        if n in As:
            value = 0
        
        elif n in {0, 1}:
            value = 1

        else:
            value = n_steps(n - 1) + n_steps(n - 2)
            value %= MOD

        cache[n] = value
    return cache[n]

for i in range(N):
    n_steps(i)
print(n_steps(N))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


H, W = map(int, input().split())
mass = list()
for i in range(H):
    mass.append(input())

values_col = defaultdict(int)
values_row = defaultdict(int)

ind_row = [[0 for i in range(H)] for j in range(W)]
ind_col = [[0 for i in range(H)] for j in range(W)]

ind = 0
for i, m_row in enumerate(mass):
    ind += 1
    for j, chr in enumerate(mass[i]):
        if chr == '#':
            ind += 1
        else:
            values_row[ind] += 1
            ind_row[i][j] = ind

# print('ROW')
# for i in range(H):
#     for j in range(W):
#         print(values_row[ind_row[i][j]], end=' ')
#     print()

ind = 0
for j in range(W):
    ind += 1
    for i in range(H):
        chr = mass[i][j]
        if chr == '#':
            ind += 1
        else:
            values_col[ind] += 1
            ind_col[i][j] = ind

# print('COL')
# for i in range(H):
#     for j in range(W):
#         print(values_col[ind_col[i][j]], end=' ')
#     print()

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, values_row[ind_row[i][j]] + values_col[ind_col[i][j]] - 1)
print(ans)


Fixed submission:
from collections import defaultdict


H, W = map(int, input().split())
mass = list()
for i in range(H):
    mass.append(input())

values_col = defaultdict(int)
values_row = defaultdict(int)

ind_row = [[0 for i in range(W)] for j in range(H)]
ind_col = [[0 for i in range(W)] for j in range(H)]

ind = 0
for i, m_row in enumerate(mass):
    ind += 1
    for j, chr in enumerate(mass[i]):
        if chr == '#':
            ind += 1
        else:
            values_row[ind] += 1
            ind_row[i][j] = ind

# print('ROW')
# for i in range(H):
#     for j in range(W):
#         print(values_row[ind_row[i][j]], end=' ')
#     print()

ind = 0
for j in range(W):
    ind += 1
    for i in range(H):
        chr = mass[i][j]
        if chr == '#':
            ind += 1
        else:
            values_col[ind] += 1
            ind_col[i][j] = ind

# print('COL')
# for i in range(H):
#     for j in range(W):
#         print(values_col[ind_col[i][j]], end=' ')
#     print()

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, values_row[ind_row[i][j]] + values_col[ind_col[i][j]] - 1)
print(ans)