Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)

def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

Fixed submission:
import sys
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)
sys.setrecursionlimit(10**9)
def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)

def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)
    
c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

Fixed submission:
import sys
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)
sys.setrecursionlimit(10**9)
def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    if(t == "1"):
        a_index = int(a)-1
        if(S[a_index]==b):
            continue
        tmp_index = bisect_left(dic[S[a_index]],a_index)
        dic[s[a]].pop(tmp_index)
        insort.left(dic[b],a)
        s[a] = b
    elif(t == "2"):
        a_index = int(a)-1
        b_index = int(b)-1
        cnt = 0
        for li in dic.values():
            if(li and a_index <= li[-1] and li[bisect_left(li,a_index)] <= b_index):
                    cnt += 1
        print(cnt)

Fixed submission:
from bisect import insort_left, bisect_left
N = int(input())
S = list(input())
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    a = int(a)-1
    if(t == "1"):
        if(S[a]==b):
            continue
        tmp_index = bisect_left(dic[S[a]],a)
        dic[S[a]].pop(tmp_index)
        insort_left(dic[b],a)
        S[a] = b
    elif(t == "2"):
        b = int(b)-1
        cnt = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                cnt += 1
        print(cnt)

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    if(t == "1"):
        a_index = int(a)-1
        dic[S[a_index]].remove(a_index)
        dic[b].append(a_index)
    if(t == "2"):
        a_index = int(a)-1
        b_index = int(b)-1
        cnt = 0
        for i in range(26):
            for d in dic[chr(i+ord("a"))]:
                if(a_index<=d<=b_index):
                    cnt += 1
                    break
        print(cnt)

Fixed submission:
from bisect import insort_left, bisect_left
N = int(input())
S = list(input())
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    a = int(a)-1
    if(t == "1"):
        if(S[a]==b):
            continue
        tmp_index = bisect_left(dic[S[a]],a)
        dic[S[a]].pop(tmp_index)
        insort_left(dic[b],a)
        S[a] = b
    elif(t == "2"):
        b = int(b)-1
        cnt = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                cnt += 1
        print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = (2**n-1)%mod
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)

Fixed submission:
n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = pow(2,n,mod)-1
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import math
n,a,b = map(int, input().split())
#include a b
all_case = 2 ** n - 1
a_case = math.factorial(n)*pow((math.factorial(a)*math.factorial(n-a)),((10**9+7)-2),10**9+7)
b_case = math.factorial(n)*pow((math.factorial(b)*math.factorial(n-b)),((10**9+7)-2),10**9+7)
res = int((all_case-a_case-b_case)%(10**9+7))
print(res)

Fixed submission:
n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = pow(2,n,mod)-1
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())
if(A == B && A != C):
    print('Yes')
elif(A == C && A != B):
    print('Yes')
elif(C == B && A != B):
    print('Yes')
else:
    print('No')

Fixed submission:
A,B,C = map(int,input().split())
if(A == B and A != C):
    print('Yes')
elif(A == C and A != B):
    print('Yes')
elif(C == B and A != B):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
for i in SS.keys():
    if(SS[i]== max(SS.values())):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])
    

Fixed submission:
import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
m = max(SS.values())
for i in SS.keys():
    if(SS[i]== m):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])

Buggy python submission (verdict: Runtime Error):
import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
for i in range(len(S_dict)):
    if(SS[S[i]]== max(SS.values())):
        res.append(S[i])
res.sort()
for i in range(len(res)):
    print(res[i])
    

Fixed submission:
import collections
N = int(input())
S = []

res = []
for i in range(N):
    S.append(input())

SS = collections.Counter(S)
m = max(SS.values())
for i in SS.keys():
    if(SS[i]== m):
        res.append(i)
res.sort()
for i in range(len(res)):
    print(res[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
result = "YES"
for i in range(N):
    for j in range(N-i-1):
        if(A[i]== A[i+j+1]):
            result = "NO"
print(result)

Fixed submission:
N = int(input())
A = sorted(list(map(int,input().split())))
result = "YES"
for i in range(N-1):
    if(A[i]== A[i+1]):
        result = "NO"
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
p = list(map(int,input().split()))
sum1 = 0
sumMax = 0
for i in range(N-K+1):
    Sik = sum(p[:i+K])
    Si = sum(p[:i])
    sum1 = Sik-Si
    if(sumMax < sum1):
        sumMax = sum1
result = 0.5*K + 0.5*(sumMax)
print(result)

Fixed submission:
N, K = map(int,input().split())
p = list(map(int,input().split()))
S = [0]
a = 0
sum1 = 0
sumMax = 0
for i in range(N):
    a += p[i]
    S.append(a)
for i in range(N-K+1):
    sum1 = S[i+K] - S[i]
    if(sumMax < sum1):
        sumMax = sum1
result = 0.5*K + 0.5*(sumMax)
print(result)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
p = list(map(int,input().split()))
sum1 = 0
sumMax = 0
for i in range(N-K+1):
    for j in range(K):
        sum1 = sum1 + p[i+j]
    if(sumMax < sum1):
        sumMax = sum1
    sum1 = 0
result = 0.5*K + 0.5*(sumMax)
print(result)

Fixed submission:
N, K = map(int,input().split())
p = list(map(int,input().split()))
S = [0]
a = 0
sum1 = 0
sumMax = 0
for i in range(N):
    a += p[i]
    S.append(a)
for i in range(N-K+1):
    sum1 = S[i+K] - S[i]
    if(sumMax < sum1):
        sumMax = sum1
result = 0.5*K + 0.5*(sumMax)
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
H = sorted(list(map(int,input().split())), reverse = True)
if(N <= K):
    s = 0
else:
    for i in range(K):
        del H[0]
    s = sum(H)
print(s)

Fixed submission:
N,K = map(int,input().split())
H = sorted(list(map(int,input().split())), reverse = True)
if(N <= K):
    s = 0
else:
    del H[0:K]
    s = sum(H)
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
H = sorted(list(map(int,input().split())), reverse = True)
if(N <= K):
    s = 0
else:
    for i in range(K):
        del H[0]
    s = sum(H)
print(s)

Fixed submission:
N,K = map(int,input().split())
H = sorted(list(map(int,input().split())), reverse = True)
if(N <= K):
    s = 0
else:
    del H[0:K]
    s = sum(H)
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int,input().split()))
cnt = 0
for i in range(N):
    part_min = min(P[:i+1])
    if(part_min == P[i]):
        cnt += 1

print(cnt)

Fixed submission:
N = int(input())
P = list(map(int,input().split()))
cnt = 0
min1 = P[0]
for i in range(N):
    if(min1 > P[i]):
        min1 = P[i]
    if(min1 == P[i]):
        cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,K = map(int,input().split())
for i in range(K):
    if(A >= 1):
        A -= 1
    elif(B >= 1):
        B -= 1
print(A, B)

Fixed submission:
A,B,K = map(int,input().split())
if(K <= A):
    A = A-K
elif(K < A+B):
    B = A+B-K
    A = 0
else:
    A = 0
    B = 0
print(A, B)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()
score = 0
for i in range(N):
    if(T[i]=="r"):
        score +=P
    elif(T[i]=="s"):
        score +=R
    elif(T[i]=="p"):
        score +=S
    if(i <= N-K-1):
        if(T[i]==T[i+K]):
            Tl = list(T)
            Tl[i+K] = "0"
            T = "".join(Tl)
print(score)

Fixed submission:
N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = list(input())
score = 0
for i in range(N):
    if(T[i]=="r"):
        score +=P
    elif(T[i]=="s"):
        score +=R
    elif(T[i]=="p"):
        score +=S
    if(i <= N-K-1):
        if(T[i]==T[i+K]):
            T[i+K] = "0"
print(score)
Buggy python submission (verdict: Runtime Error):
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)

Fixed submission:
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
fin = 0
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)

Buggy python submission (verdict: Runtime Error):
from collections import deque
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
print(E)
def bfs(start,N,AB):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N,AB)#takahashi
aoki = bfs(v,N,AB)
print(taka,aoki)
fin = -1
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

Fixed submission:
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
fin = 0
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
num0 = 0
num1 = 0
ans = 0
for i in range(61):
    for j in A:
        if(j%(2**(i+1))>=2**i):
            num1 +=1
        else:
            num0 +=1
    ans += num0*num1*(2**i)
    num0,num1 = 0,0
print(ans%(10**9+7))

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(60):
    x = 1<<i
    o = sum(1 for j in A if j&x)
    ans += x*o*(N-o)
    ans %= 10**9+7
print(ans)
Buggy python submission (verdict: Runtime Error):
A,B = map(int(input()))
if(A >= 10 or B >= 10):
    print(-1)
else:
    print(A*B)

Fixed submission:
A,B = map(int,input().split())
if(A >= 10 or B >= 10):
    print(-1)
else:
    print(A*B)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(list(map(int,input().split())),reverse = False)
cnt = 0
for a in range(0,N-2):
    A = L[a]
    for b in range(a+1,N-1):
        B = L[b]
        low = b+1
        high = N-1
        while(low+1 != high and low != high):
            mid = (low+high)//2
            if(A+B > L[mid]):
                low = mid
            else:
                high = mid
        if(A+B > L[high]):
            cnt += high-b
        elif(A+B > L[low]):
            cnt += low-b
print(cnt)      

Fixed submission:
from bisect import bisect_left
N = int(input())
L = sorted(list(map(int,input().split())),reverse = False)
cnt = 0
for a in range(0,N-2):
    A = L[a]
    for b in range(a+1,N-1):
        B = L[b]
        cnt += bisect_left(L,A+B)-b-1
print(cnt)
Buggy python submission (verdict: Runtime Error):
A,B = map(int,input().split())
if(B == 1):
    print(0)
elif((B-1)%(A-1) == 0):
    print((B-1)//(A-1)
else:
    print(B//A+1)

Fixed submission:
A,B = map(int,input().split())
if(B == 1):
    print(0)
elif((B-1)%(A-1) == 0):
    print((B-1)//(A-1))
else:
    print(B//A+1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]
E = [[] for i in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
    E[ab[i][1]].append(ab[i][0])

d = [0]*(N+1)
visit = [0]*(N+1)
for i in range(Q):
    d[px[i][0]]+=px[i][1]
def bfs(s):
    q = deque([s])
    while q:
        v = q.pop()
        visit[v] = 1
        for j in E[v]:
            if(visit[j] == 1):
                continue
            q.append(j)
            d[j] += d[v]
            
bfs(1)
for i in range(1,N+1):
    print(d[i])

Fixed submission:
from collections import deque
N,Q = map(int,input().split())
E = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)

d = [0]*(N+1)
visit = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    d[p]+=x
def bfs(s):
    q = deque([s])
    while q:
        v = q.pop()
        visit[v] = 1
        for j in E[v]:
            if(visit[j] == 1):
                continue
            q.append(j)
            d[j] += d[v]
            
bfs(1)
for i in range(1,N+1):
    print(d[i])
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
job = {}
for i in range(N):
    A,B = map(int,input().split())
    job.setdefault(A,[]).append(B)
ans = 0
last = min(job.keys())
for i in range(last,M+1):
    option = sorted(job[i])
    if(option != []):
        today = option.pop()
        ans += today
    job.setdefault(i+1,[]).extend(option)
print(ans)

Fixed submission:
import heapq
N,M = map(int,input().split())
AB = sorted([list(map(int,input().split())) for _ in range(N)])

option = []
ans = 0
j = 0
for i in range(1,M+1):
    while j != N and AB[j][0] <= i: 
        heapq.heappush(option,-AB[j][1])
        j += 1
    if len(option) != 0:
        ans -= heapq.heappop(option)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
job = {}
for i in range(N):
    A,B = map(int,input().split())
    job.setdefault(A,[]).append(B)
ans = 0
last = min(job.keys())
for i in range(last,M+1):
    if(job[i] != []):
        today = max(job[i])
        ans += today
        job[i].remove(today)
    job.setdefault(i+1,[]).extend(job[i])
print(ans)

Fixed submission:
import heapq
N,M = map(int,input().split())
AB = sorted([list(map(int,input().split())) for _ in range(N)])

option = []
ans = 0
j = 0
for i in range(1,M+1):
    while j != N and AB[j][0] <= i: 
        heapq.heappush(option,-AB[j][1])
        j += 1
    if len(option) != 0:
        ans -= heapq.heappop(option)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
max1 = max(A)
index = []
A2 = sorted(A)[1]
for i in range(N):
    if(A[i] == max1):
        print(max2)
    else:
        print(max1)

Fixed submission:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
max1 = max(A)
max2 = sorted(A,reverse = True)[1]
for i in range(N):
    if(A[i] == max1):
        print(max2)
    else:
        print(max1)
Buggy python submission (verdict: Runtime Error):
import math
A,B,C,D = map(int,input().split())
C_wareru = B//C-(A-1)//C
D_wareru = B//D-(A-1)//D
def lcm(a,b):
    return ((a*b) // math.gcd(a,b))
CD = lcm(C,D)
CD_wareru = B//CD-(A-1)//CD
print(B-A+1-(C_wareru+D_wareru-CD_wareru))

Fixed submission:
import fractions
A,B,C,D = map(int,input().split())
C_wareru = B//C-(A-1)//C
D_wareru = B//D-(A-1)//D
def lcm(a,b):
    return ((a*b) // fractions.gcd(a,b))
CD = lcm(C,D)
CD_wareru = B//CD-(A-1)//CD
print(B-A+1-(C_wareru+D_wareru-CD_wareru))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(5000)
N,M = map(int,input().split())
def stair(N):
    if(N <0):
        return 0
    if(N == 0):
        return 1
    elif(N == 1):
        return 1
    elif(N == 2):
        return 2
    else:
        return stair(N-1)+stair(N-2)
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    ans = ans*stair(b-a)%mod
    a = b+2
ans = ans*stair(N-a)%mod
print(ans)

Fixed submission:
N,M = map(int,input().split())
steps = [1,1,2]
for i in range(3,N+1):
    steps.append(steps[i-1]+steps[i-2])
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    if(b<a):
        print(0)
        exit()
    else:
        ans = ans*steps[b-a]%mod
    a = b+2
ans = ans*steps[N-a]%mod
print(ans)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
def stair(N):
    if(N <0):
        return 0
    if(N == 0):
        return 1
    elif(N == 1):
        return 1
    elif(N == 2):
        return 2
    else:
        return stair(N-1)+stair(N-2)
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    ans = ans*stair(b-a)%mod
    print(a,b,ans)
    a = b+2
ans = ans*stair(N-a)%mod
print(ans)

Fixed submission:
N,M = map(int,input().split())
steps = [1,1,2]
for i in range(3,N+1):
    steps.append(steps[i-1]+steps[i-2])
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    if(b<a):
        print(0)
        exit()
    else:
        ans = ans*steps[b-a]%mod
    a = b+2
ans = ans*steps[N-a]%mod
print(ans)