Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   red = 0
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
      for i in list(ans):
         if(box[i] == 0):
            ans.remove(i)
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()

Fixed submission:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         if(box[x - 1]==1):
            ans.remove(x-1)
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()

Buggy python submission (verdict: Time Limit Exceeded):
def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   red = 0
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
      for i in list(ans):
         if(box[i] == 0):
            ans.remove(i)
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()

Fixed submission:
'''
Accepted    　:No
difficult   　: 
ペナルティ　  　:5分
実際の回答時間  :分
WAの回数　     :回
合計時間　　  　:分
'''

def myAnswer(N:int,M:int,X:list,Y:list) -> int:
   ans = {0}
   box = [1] * N
   for x,y in zip(X,Y):
      if(x-1 in ans):
         if(box[x - 1]==1):
            ans.remove(x-1)
         ans.add(y-1)
      box[x-1] -= 1
      box[y-1] += 1
   return len(ans)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   X = []
   Y = []
   for _ in range(M):
      x,y=map(int,input().split())
      X.append(x)
      Y.append(y)
   print(myAnswer(N,M,X,Y))
if __name__ == '__main__':
   main()
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1),k+1)

print(ans)

Fixed submission:
from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(gcd(i,j),k)

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt

eps = 1e-8

def eq(a, b):
    return a + eps > b and a - eps < b

a, b, c = list(map(int, input().split()))
elif 2 * sqrt(a * b) < c - a - b - eps:
    print("Yes")
else:
    print("No")

Fixed submission:
arr = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(arr[k - 1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
ans = A[0]
for i in range(1, n):
    ans *= A[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
ans = A[0]
i = 1
if 0 in A:
    print(0)
else:
    while (i < n) and (ans <= 10**18):
        ans *= A[i]
        i += 1
    if (ans <= 10**18) and i == n:
        print(ans)
    else:
        print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
hlis = list(map(int, input().split()))
road = []
for i in range(m):
    a, b = map(int, input().split())
    road.append([a, b])
table = [0]*n
ans = 0
for i in range(n):
    if table[i] == 0:
        rival = []
        for j in road:
            if j[0] == i+1:
                rival.append(j[1]-1)
            elif j[1] == i+1:
                rival.append(j[0]-1)
        if hlis[i] == max([hlis[q] for q in rival]+[hlis[i]]) and [hlis[q] for q in rival].count(hlis[i])== 0:
            table[i] = 1
            ans += 1
            for q in rival:
                table[q] = -1 
        else:
            table[i] = -1
print(ans)

Fixed submission:
n, m = map(int, input().split())
hlis = list(map(int, input().split()))
lis = [1]*n
for i in range(m):
    a, b = map(int, input().split())
    if hlis[a-1] > hlis[b-1]:
        lis[b-1] = -1
    elif hlis[a-1] < hlis[b-1]:
        lis[a-1] = -1
    elif hlis[a-1] == hlis[b-1]:
        lis[a-1] = -1
        lis[b-1] = -1
print(lis.count(1))
Buggy python submission (verdict: Runtime Error):
import sys
n, m, q = map(int, input().split())
alis, blis, clis, dlis = [], [], [], []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    alis.append(a)
    blis.append(b)
    clis.append(c)
    dlis.append(d)
sys.setrecursionlimit(10**9)
Alist = [] 
def dfs(A):
    if len(A)==(n+1):
        Alist.append(A)
        return
    for i in range(A[-1], m+1):
        A.append(i)
        dfs(A)

dfs([1])

ans = 0
for A in Alist:
    score = 0
    for i in range(q):
        if A[blis[i]] - A[alis[i]] == clis[i]:
            score += dlis[i]
    ans = max(ans, score)

print(ans)

Fixed submission:
import sys
n, m, q = map(int, input().split())
alis, blis, clis, dlis = [], [], [], []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    alis.append(a)
    blis.append(b)
    clis.append(c)
    dlis.append(d)
sys.setrecursionlimit(10**9)
Alist = [] 
def dfs(A):
    if len(A)==(n+1):
        Alist.append(A)
        return
    for i in range(A[-1], m+1):
        dfs(A+[i])

dfs([1])

ans = 0
for A in Alist:
    score = 0
    for i in range(q):
        if A[blis[i]] - A[alis[i]] == clis[i]:
            score += dlis[i]
    ans = max(ans, score)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, n = map(int, input().split())
def func(i, j, k):
    return (i*k)//j - i*(k//j)
ans = 0
for i in range(1, min(b+1, n+1)):
    if func(a, b, i) > ans:
        ans = func(a, b, i)
print(ans)

Fixed submission:
a, b, n = map(int, input().split())
def func(i, j, k):
    return (i*k)//j - i*(k//j)
m = min(n, b-1)
r = (a*min(n, b-1)) // b
while ((a*m) // b) == r:
    m -= 1
print(func(a, b, m+1))
Buggy python submission (verdict: Time Limit Exceeded):
import math
K = int(input())
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            n = math.gcd(i, math.gcd(j, k))
            ans += n
print(ans)

Fixed submission:
import math
from functools import reduce
K = int(input())
ans = 0
for i in range(1, K-1):
    for j in range(i+1, K):
        for k in range(j+1, K+1):
            n = math.gcd(i, math.gcd(j,k))
            ans += 6*n
for i in range(1, K+1):
    for j in range(i+1, K+1):
        n = math.gcd(i,j)
        ans += 6*n
print(ans+sum(list(i for i in range(K+1))))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
ans = len(r)*len(g)*len(b)
def func(a,b,c):
    ans = 0
    for i in a:
        for k in [num1 for num1 in c if num1 > i+1]:
            if (k + i) / 2 in b:
                    ans -= 1
    return ans
print(ans + func(r,g,b) + func(r,b,g) + func(g,r,b) + func(g,b,r) + func(b,g,r) + func(b,r,g))

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

Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
ans = len(r)*len(g)*len(b)
def func(a,b,c):
    ans = 0
    for i in a:
        for k in [num1 for num1 in b if num1 > i+1]:
            if (k + i) // 2 in j:
                    ans -= 1
    return ans
print(ans + func(r,g,b) + func(r,b,g) + func(g,r,b) + func(g,b,r) + func(b,g,r) + func(b,r,g))

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

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)

def func(a,b,c):
    ans = 0
    for i in a:
        for j in [num1 for num1 in b if num1 >i]:
            for k in [num2 for num2 in c if num2 > j]:
                if j-i != k-j:
                    ans += 1
    return ans
print(func(r,g,b) + func(r,b,g) + func(g,r,b) + func(g,b,r) + func(b,g,r) + func(b,r,g))

Fixed submission:
n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n-2):
    for j in range(i+1, n-1):
        if 2*j - i >= n:
            break
        elif s[i] != s[j] and s[j] != s[(2*j-i)] and s[(2*j-i)] != s[i]:
            ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
def func(x):
    return abs(x-k)
ans = n
while min(func(n), n) != n:
    ans = func(n)
    n = func(n)
print(ans)

Fixed submission:
n, k = map(int, input().split())
a, b = divmod(n, k)
print(min(abs(n - k*(a+1)), b))

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
lis = []
while lis.count(abs(n-k)) == 0:
    lis.append(abs(n-k))
    n = abs(n-k)
print(min(lis))

Fixed submission:
n, k = map(int, input().split())
a, b = divmod(n, k)
print(min(abs(n - k*(a+1)), b))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
for i in range(q):
    q_i = input()
    if q_i == '1':
        s = ''.join(list(s)[::-1])
    else:
        a, f, c = q_i.split()
        if f == '1':
            s = c+s
        else:
            s = s+c
print(s)
    

Fixed submission:
from collections import deque

s = input()
q = int(input())
queries = [input().split() for _ in range(q)]

judge = True
S = deque()
for string in s:
    S.append(string)

for query in queries:
    if query[0] == '1':
        judge = not judge
    else:
        if judge:
            if query[1] == '1':
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == '1':
                S.append(query[2])
            else:
                S.appendleft(query[2])
ans = ''.join(S)
if not judge:
    print(ans[::-1])
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = [input() for _ in range(n)]
s = set(lis)
a = []
for i in s:
    a.append([lis.count(i), i])
M = max(a, key=lambda i : i[0])
anslis = [i[1] for i in a if i[0]==M[0]]
anslis.sort()
for i in anslis:
    print(i)

Fixed submission:
n = int(input())
dic = {}
for _ in range(n):
    s = input()
    if s not in dic:
        dic[s] = 1
    else:
        dic[s] += 1
m = max(dic.values())
anslis = []
for k, v in dic.items():
    if v == m:
        anslis.append(k)
print('\n'.join(sorted(anslis)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = [input() for _ in range(n)]
s = set(lis)
a = []
for i in s:
    a.append([lis.count(i), i])
slis = sorted(a, key=lambda i : i[1])
M = max(slis, key=lambda i : i[0])
func = lambda i:i[1] if i[0] == M else None
anslis = [i[1] for i in slis if i[0]==M[0]]
for i in anslis:
    print(i)

Fixed submission:
n = int(input())
dic = {}
for _ in range(n):
    s = input()
    if s not in dic:
        dic[s] = 1
    else:
        dic[s] += 1
m = max(dic.values())
anslis = []
for k, v in dic.items():
    if v == m:
        anslis.append(k)
print('\n'.join(sorted(anslis)))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
plis = list(map(int, input().split()))
plis = list(map(lambda p : (1+p)/2, plis))
ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(plis[i:i+k]))
print(ans)

Fixed submission:
n, k = map(int, input().split())
plis = list(map(int, input().split()))
plis = list(map(lambda p : (1+p)/2, plis))
slis = [plis[0]]
for i in range(1, n):
    slis.append(slis[-1] + plis[i])
ans = slis[k-1]
for i in range(1, n-k):
    ans = max(ans, slis[i+k] - slis[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = list(map(int, input().split()))
ans = 1
for i in range(1, n):
    if min(lis[:(i+1)]) == lis[i]:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
lis = list(map(int, input().split()))
m = float('inf')
ans = 0
for i in range(n):
    m = min(m, lis[i])
    if min(m, lis[i]) == lis[i]:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lis = list(map(int, input().split()))
ans = 0
for i in range(n):
    s = 0
    for j in range(i):
        if lis[i] <= lis[j]:
            s += 1
    if s == i:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
lis = list(map(int, input().split()))
m = float('inf')
ans = 0
for i in range(n):
    m = min(m, lis[i])
    if min(m, lis[i]) == lis[i]:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
lis = [list(input().split()) for _ in range(m)]
d = {}
ac, wa = 0, 0
for i in lis:
    if i[0] not in d:
        if i[1] == 'AC':
            ac += 1
            d[i[0]] = 'AC'
        else:
            d[i[0]] = 1
    else:
        if i[1] == 'AC':
            if d[i[0]] != 'AC':
                ac += 1
                wa += d[i[0]]
                d[i[0]] = 'AC'
        else:
            d[i[0]] += 1
print(ac, wa)

Fixed submission:
n, m = map(int, input().split())
lis = [list(input().split()) for _ in range(m)]
d = {}
ac, wa = 0, 0
for i in lis:
    if i[0] not in d:
        if i[1] == 'AC':
            ac += 1
            d[i[0]] = 'AC'
        else:
            d[i[0]] = 1
    else:
        if i[1] == 'AC':
            if d[i[0]] != 'AC':
                ac += 1
                wa += d[i[0]]
                d[i[0]] = 'AC'
        else:
            if d[i[0]] != 'AC':
                d[i[0]] += 1
print(ac, wa)
Buggy python submission (verdict: Runtime Error):
import itertools
n = int(input())
plis = list(map(int, input().split()))
qlis = list(map(int, input().split()))
lis = list(itertools.permutations(range(1, n+1)))
n = 1
for i in lis:
    if list(i) == plis:
        a = n
        n += 1
    elif list(i) == qlis:
        b = n
        n += 1
    else:
        n += 1
print(abs(a-b))

Fixed submission:
import itertools
n = int(input())
plis = list(map(int, input().split()))
qlis = list(map(int, input().split()))
lis = list(itertools.permutations(range(1, n+1)))
n = 1
for i in lis:
    if list(i) == plis:
        a = n
    if list(i) == qlis:
        b = n
    n += 1
print(abs(a-b))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
r, s, p = map(int, input().split())
d = {'r':r, 's':s, 'p':p}
t = input()
def janken(x):
    if x == 'r':
        return 'p'
    elif x == 's':
        return 'r'
    else:
        return 's'
l = ['']*k
for i in range(n):
    l[i%k] += t[i]
ans = 0
for i in l:
    dp = d(i[0]) + ['-1']*(len(i)-1)
    ans += d[janken(i[0])]
    for j in range(1, len(i)):
        if i[j] != i[j-1]:
            ans += d[janken(i[j])]
            dp[j] = d(i[j])
        else:
            dp[j] = d(i[j])
print(ans)

Fixed submission:
n, k = map(int, input().split())
r, s, p = map(int, input().split())
d = {'r':r, 's':s, 'p':p}
t = input()
def janken(x):
    if x == 'r':
        return 'p'
    elif x == 's':
        return 'r'
    else:
        return 's'
l = ['']*k
for i in range(n):
    l[i%k] += t[i]
ans = 0
for i in l:
    pre = i[0]
    ans += d[janken(i[0])]
    for j in range(1, len(i)):
        if i[j] != pre:
            ans += d[janken(i[j])]
            pre = i[j]
        else:
            pre = ''
print(ans)
Buggy python submission (verdict: Runtime Error):
import itertools
import math
n = int(input())
lis1 = []
for i in range(n):
    lis1.append(list(map(int, input().split())))
S = 0
for i in list(itertools.permutations(range(n))):
    for j in range(n-1):
        S += math.sqrt((lis1[i[j]][0]-lis1[i[j+1]][0])**2 + (lis1[i[j]][1]-lis1[i[j+1]][1])**2)
for i in range(1, n+1):
    S = S / i
print(S)

Fixed submission:
n = int(input())
ans = float('inf')
for i in range(1, int(n**(1/2))+1):
    a, b = divmod(n, i)
    if b == 0:
        ans = min(ans, a+i-2)
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools
import math
n = int(input())
lis1 = []
for i in range(n):
    lis1.append(list(map(int, input().split())))
S = 0
for i in list(itertools.permutations(range(n))):
#     print(i, type(i))
    for j in range(n-1):
#         print(lis1[i[j]][0], lis1[i[j+1]][0])
        S += math.sqrt((lis1[i[j]][0]-lis1[i[j+1]][0])**2 + (lis1[i[j]][1]-lis1[i[j+1]][1])**2)
for i in range(1, n+1):
    S = S / i
print(S)

Fixed submission:
n = int(input())
ans = float('inf')
for i in range(1, int(n**(1/2))+1):
    a, b = divmod(n, i)
    if b == 0:
        ans = min(ans, a+i-2)
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
lis = []
for i in range(n):
    lis.append(list(map(int, input().split())))
s = 0
for i in range(n):
    for j in range(i,n):
        s += ((lis[i][0] - lis[j][0])**2 + (lis[i][1] - lis[j][1])**2)**(1/2)
print(s*2/n)

Fixed submission:
n = int(input())
ans = float('inf')
for i in range(1, int(n**(1/2))+1):
    a, b = divmod(n, i)
    if b == 0:
        ans = min(ans, a+i-2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
llis = list(map(int, input().split()))
lis = sorted(llis, reverse=True)
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += max(bisect_left_reverse(lis, lis[i]-lis[j]) - j - 1, 0)
print(ans)

Fixed submission:
import bisect
n = int(input())
lis = sorted(list(map(int, input().split())))
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += max(bisect.bisect_left(lis, lis[j]+lis[i]) - j - 1, 0)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())
l = list(map(int, input().split()))
p = list(itertools.combinations(l,3))
def triangle(a, b, c):
    if a < b + c and b < c + a and c < a + b:
        return True
    else:
        return False
ans = 0
for i in p:
    if triangle(i[0], i[1], i[2]):
        ans += 1
print(ans)

Fixed submission:
import bisect
n = int(input())
lis = sorted(list(map(int, input().split())))
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += max(bisect.bisect_left(lis, lis[j]+lis[i]) - j - 1, 0)
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
danger = list(int(input()) for _ in range(m))
danger = [0] + danger + [n]
def fibo(n):
    memo = [-1]*(n+1)
    def _fibo(n):
        if memo[n] != -1:
            return memo[n]
        else:
            if n <= 1:
                memo[n] = n
                return memo[n]
            else:
                memo[n] = _fibo(n-1) + _fibo(n-2)
                return memo[n]
    return _fibo(n)
ans = 1
for j in range(m+1):
    if danger[j+1] - danger[j] ==1:
        ans *= 0
    else:
        ans *= fibo(danger[j+1] - danger[j] )
print(ans)

Fixed submission:
n, m = map(int, input().split())
alis = list(int(input()) for _ in range(m))
dp = [-1]*(n+1)
mod = 10**9 + 7
for i in alis:
    dp[i] = 0
dp[0] = 1
dp[1] = 1 if 1 not in alis else 0
for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n])

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
danger = list(int(input()) for _ in range(m))
danger = [0] + danger + [n]
def fibo(n):
    memo = [-1]*(n+1)
    def _fibo(n):
        if memo[n] != -1:
            return memo[n]
        else:
            if n <= 1:
                memo[n] = n
                return memo[n]
            else:
                memo[n] = _fibo(n-1) + _fibo(n-2)
                return memo[n]
    return _fibo(n)
ans = 1
for j in range(m+1):
    ans *= fibo(danger[j+1] - danger[j] )
print(ans)

Fixed submission:
n, m = map(int, input().split())
alis = list(int(input()) for _ in range(m))
dp = [-1]*(n+1)
mod = 10**9 + 7
for i in alis:
    dp[i] = 0
dp[0] = 1
dp[1] = 1 if 1 not in alis else 0
for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n])