Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03464 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

K = int(input())
A = list(map(int,input().split()))

def ceil(a, b):
    return -(-a // b)

def floor(a, b):
    return a // b

def L(i):
    if i == K:
        return 2
    return ceil(L(i+1), A[i]) * A[i]

def R(i):
    if i == K:
        return 2
    return floor(R(i+1), A[i]) * A[i] + A[i] - 1

L0 = L(0); R0 = R(0)
if L0 <= R0:
    print(L0, R0)
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
K = int(input())
A = list(map(int,input().split()))[::-1] + [1]

# 切り上げ
def ceil(a, b):
    return -(-a//b)

# [a, b) に含まれるcの倍数のうち最小,最大のものを返す
def query(a, b, c):
    l = c * ceil(a, c)
    r = c * (ceil(b, c) - 1)
    if l <= r:
        return True, l, r
    else:
        return False, -1, -1

cand = [2,2]
for i in range(K):
    s, m = cand
    cand = []
    fs, ls, rs = query(s, s+A[i], A[i+1])
    fm, lm, rm = query(m, m+A[i], A[i+1])
    if fs:
        cand.append(ls)
    if fm:
        cand.append(rm)
    if len(cand) == 0:
        print(-1)
        exit()

s, m = cand
print(s, m)

Buggy submission (verdict: Runtime Error):
K = int(input())
A = list(map(int,input().split()))[::-1] + [1]

# 切り上げ
def ceil(a, b):
    return -(-a//b)

# [a, b) に含まれるcの倍数のうち最小,最大のものを返す
def query(a, b, c):
    l = c * ceil(a, c)
    r = c * (ceil(b, c) - 1)
    if l <= r:
        return True, l, r
    else:
        return False, -1, -1

cand = [2,2]
for i in range(K):
    if len(cand) == 0:
        print(-1)
        exit()
    s, m = cand
    cand = []
    fs, ls, rs = query(s, s+A[i], A[i+1])
    fm, lm, rm = query(m, s+A[i], A[i+1])
    if fs:
        cand.append(ls)
    if fm:
        cand.append(rm)

if len(cand) == 0:
    print(-1)
else:
    print(cand[0], cand[-1])
Problem p03745 (python)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
state = 0
count = 1
for i in range(1,N):
    note = state
    d = A[i] - A[i-1]
    if d > 0:
        state = 1
    elif d == 0:
        pass
    elif d < 0:
        state = -1
    if (state,note) == (1,-1) or (state,note) == (-1,1):
        count += 1
        state = 0
print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
if N == 1:
    print(1)
    exit()
d = [A[i+1] - A[i] for i in range(N-1)]
def judge(list_hoge = d,count = 1):
    if len(list_hoge) == 1:
        print(count)
        return
    for i in range(1,len(list_hoge)):
        if list_hoge[i] * list_hoge[0] < 0:
            if i == len(list_hoge) - 1:
                print(count + 1)
                return
            else:
                return judge(list_hoge[i+1:],count + 1)
    print(count)
    return
judge()

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
if N <= 2:
    print(1)
    exit()
d = [A[i+1] - A[i] for i in range(N-1)]
def judge(list_hoge = d,count = 1):
    for i in range(1,len(list_hoge)):
        if list_hoge[i] * list_hoge[0] < 0:
            return judge(list_hoge[i+1:],count + 1)
    print(count)
judge()

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
if N == 1:
    print(1)
    exit()
d = [A[i+1] - A[i] for i in range(N-1)]
def judge(list_hoge = d,count = 1):
    for i in range(1,len(list_hoge)):
        if list_hoge[i] * list_hoge[0] < 0:
            return judge(list_hoge[i+1:],count + 1)
    print(count)
judge()

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
d = [A[i+1] - A[i] for i in range(N-1)]
def judge(list_hoge = d,count = 1):
    for i in range(1,len(list_hoge)):
        if list_hoge[i] * list_hoge[0] < 0:
            return judge(list_hoge[i+1:],count + 1)
    print(count)
judge()

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
if N == 1 or len(list(set(A))) == 1:
    print(1)
    exit()
def rec(list1,t):
    for i in range(1,len(list1)):
        if list1[i] - list1[i-1] > 0:
            note = "not decrease"
            break
        elif list1[i] - list1[i-1] < 0:
            note = "not increase"
            break
    for i in range(1,len(list1)):
        if note == "not decrease" and  list1[i] - list1[i-1] < 0:
            return rec(list1[i:],t+1)
        elif note == "not increase" and list1[i] - list1[i-1] > 0:
            return rec(list1[i:],t+1)
    return t
ans = rec(A,1)
print(ans)
Problem p03805 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*N for i in range(N)]
visited = [False]*N
visited[0] = True
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-1:
        global ans
        ans += 1
        return
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            visited[i] = True
            dfs(i,depth+1)
            visited[i] = False

dfs()
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
visited[0] = True
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-1:
        global ans
        ans += 1
        return
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            visited[i] = True
            dfs(i,depth+1)
            visited[i] = False

dfs()
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p=0, depth=0):
    if depth == N-2:
        global ans
        ans += 1
        return
    visited[p] = True
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            dfs(i,depth+1)

dfs()
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
note = [[0]*M for i in range(N)]
visited = [False]*N
ans = 0
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    note[a][b] = 1
    note[b][a] = 1

def dfs(p = 0):
    True_count = 0
    False_count = 0
    for f in visited:
        if f is True:
            True_count += 1
        elif f is False:
            False_count += 1
    if True_count == N-1 and False_count == 1:
        global ans 
        ans += 1
        return
    visited[p] = True
    for i in range(N):
        if note[p][i] == 1 and visited[i] is False:
            dfs(i)

dfs()
print(ans)
Problem p03835 (python)

Fixed submission:
K,S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - (i+j) <= K:
            count += 1
print(count)

Buggy submission (verdict: Runtime Error):
K,S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - (i+j) <= K:
            count += 1
print(count)
Problem p02836 (python)

Fixed submission:
treat = input()

acc = 0
hugs = 0

for i in range(len(treat) // 2):
	if treat[acc] == treat[len(treat) - 1 - acc]:
		acc = acc + 1
	else:
		hugs = hugs + 1
		acc = acc + 1

print(hugs)

Buggy submission (verdict: Runtime Error):
treat = input()

acc = 0
hugs = 0

for i in len(treat):
	if treat[acc] = treat[len(treat) - acc]:
		acc = acc + 1
	else:
		hugs = hugs + 1
		acc = acc + 1

print(hugs)

Buggy submission (verdict: Runtime Error):
treat = input()

acc = 0
hugs = 0

for i in len(treat):
	if treat[acc] = treat[len(treat) - acc]:
		acc = acc + 1
	else:
		hugs = hugs + 1
		acc = acc + 1
Problem p02835 (python)

Fixed submission:

if __name__ == '__main__':
    a1, a2, a3 = map(int, input().split(' '))
    if (a1 + a2 + a3) >=22:
        print("bust")
    else:
        print("win")

Buggy submission (verdict: Runtime Error):
a1, a2, a3 = map(int, input().split(' '))
    if (a1 + a2 + a3) >=22:
        print("bust")
    else:
        print("win")
Problem p02933 (python)

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

if a >= 3200:
    print(s)
else:
    print('red')

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
to = [[] for _ in range(N)]

def dfs(v, p = -1):
    for u in to[v]:
        ans[u] += ans[v]
        dfs(u, v)

for _ in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)

ans = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

dfs(0)
for i in range(N):
    print(ans[i], end=' ')

Buggy submission (verdict: Runtime Error):
class Node:
    def __init__(self, parent, num):
        self.parent = parent
        self.num = num
        self.score = 0

    def add_score(self, score):
        self.score += score

class Tree:
    @classmethod
    def calc_sum(cls, node):
        if node.parent:
            return node.score + cls.calc_sum(node.parent)
        else:
            return node.score

N, Q = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(1, N):
    A[i], B[i] = map(int, input().split())

P = [0] * (Q+1)
X = [0] * (Q+1)
for i in range(1, Q+1):
    P[i], X[i] = map(int, input().split())

nodes = [0] * (N+1)
nodes[1] = Node(None, 1)

for i in range(1, N):
    nodes[B[i]] = Node(nodes[A[i]], B[i])

for i in range(1, Q+1):
    nodes[P[i]].add_score(X[i])

for i in range(1, N+1):
    sum_score = Tree.calc_sum(nodes[i])
    print(sum_score, end=' ')
Problem p02948 (python)

Fixed submission:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq

N, M = map(int, input().split())
jobs = []
for _ in rangek(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs.append([day, value])

ans = 0
hq = []
for day in range(1, M+1):
    for job in list(jobs):
        if day == job[0]:
            heapq.heappush(hq, - job[1])
            jobs.remove(job)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(N)]

def schedule(reward, day, jobs):
    if day > M or not jobs:
        return reward
    else:
        results = []
        for job in jobs:
            if day + job[0] - 1 > M:
                jobs.remove(job)

        if not jobs:
            return reward

        for job in jobs:
            copied_jobs = list(jobs)
            copied_jobs.remove(job)
            result = schedule(reward + job[1], day + 1, copied_jobs)
            results.append(result)
        return max(results)

print(schedule(0, 1, jobs))
Problem p02954 (python)

Fixed submission:
s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

s = input()
n = len(s)

ans = [0 for _ in range(n)]
cnt = 0
for i in range(n):
    if s[i] == 'R':
        cnt += 1
    else:
        ans[i] += cnt // 2
        ans[i-1] += (cnt + 1) // 2
        cnt = 0
s_inv = ''.join(reversed(s))
for i in range(n):
    if s_inv[i] == 'L':
        cnt += 1
    else:
        ans[n-i-1] += cnt // 2
        ans[n-i] += (cnt + 1) // 2
        cnt = 0
print(' '.join(map(str, ans)))
Problem p02990 (python)

Fixed submission:
from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

def cmb(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom % MOD
N, K = map(int, input().split())

for i in range(1, K + 1):
    print(cmb(K - 1, i - 1) * cmb(N - K + 1, i) % MOD)

Buggy submission (verdict: Runtime Error):
from math import factorial

N, K = map(int, input().split())
mod = 10 ** 9 + 7

for i in range(1, K+1):
    ans = factorial(N - K + 1)
    ans //= factorial(N - K + 1 - i)
    ans //= factorial(i)
    ans *= factorial(K - 1)
    ans //= factorial(K - i)
    ans //= factorial(i - 1)
    print(ans % mod)

Buggy submission (verdict: Runtime Error):
from math import factorial

N, K = map(int, input().split())
mod = 10 ** 9 + 7

for i in range(1, K+1):
    ans = factorial(N - K + 1)
    ans *= factorial(K - 1)
    ans //= factorial(N - K + 1 - i)
    ans //= factorial(i)
    ans //= factorial(K - i)
    ans //= factorial(i - 1)
    print(ans % mod)

Buggy submission (verdict: Runtime Error):
from math import factorial

N, K = map(int, input().split())
mod = 10 ** 9 + 7

for i in range(1, K+1):
    ans = factorial(N - K + 1) * factorial(K - 1) / factorial(N - K + 1 - i) / factorial(i) / factorial(K - i) / factorial(i - 1) % mod
    print(int(ans))
Problem p02819 (python)

Fixed submission:
def is_prime(x, i):
  if i*i > x:
    return True
  elif x % i == 0:
    return False
  else:
    return is_prime(x, i+1)
  
def gen_prime(x):
  if is_prime(x, 2):
    return x
  else:
    return gen_prime(x+1)
    
if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10240)
  x = int(input())
  print(gen_prime(x))

Buggy submission (verdict: Runtime Error):
def is_prime(x, i):
  if i*i > x:
    return True
  elif x % i == 0:
    return False
  else:
    is_prime(x, i+1)
  
def gen_prime(x):
  if is_prime(x, 2):
    return x
  else:
    gen_prime(x+1)
    
if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10240)
  x = int(input())
  print(gen_prime(x))

Buggy submission (verdict: Runtime Error):
def is_prime(x, i):
  if i*i > x:
    return True
  elif x % i == 0:
    return False
  else:
    is_prime(x, i+1)
  
def gen_prime(x):
  if is_prime(x, 2):
    return x
  else:
    gen_prime(x+1)
    
if __name__ == "__main__":
  x = int(input())
  print(gen_prime(x))
Problem p02860 (python)

Fixed submission:
n = int(input())
s = input()
if n%2 != 0 or n == 1:
  print("No")
elif s[:int(n/2)] == s[int(n/2):]:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
if n%2 != 0 or n == 1:
  prtin("No")
elif s[:int(n/2)] == s[int(n/2):]:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
if n%2 != 0.0:
  prtin("No")
elif s[:int(n/2)] == s[int(n/2):]:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
if n%2 != 0:
  prtin("No")
elif s[:int(n/2)] == s[int(n/2):]:
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
if n%2 != 0:
  prtin("No")
elif s[int(:n/2)] == s[int(n/2):]:
  print("Yes")
else:
  print("No")
Problem p03315 (python)

Fixed submission:
S = input()
count = 0
for i in S:
    if i == '+':
        count += 1
    elif i == '-':
        count -= 1
print(count)

Buggy submission (verdict: Runtime Error):
import math

def process_smaller_index(K, min_index):
    if min_index == 0:
        return 0
    else:
        return math.ceil(min_index / K)

def process_larger_index(last_index, K, min_index):
    if min_index == last_index:
        return 0
    else:
        return math.ceil((last_index - min_index) / K)

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
min_index = A.index(1)
print(process_smaller_index(K - 1, min_index) + process_larger_index(len(A)-1, K - 1, min_index))
Problem p02829 (python)

Fixed submission:
a = input()
b = input()
choices = '123'
for c in choices:
  if((c != a) and (c != b)):
    print(c)

Buggy submission (verdict: Runtime Error):
a = int(input())
b = int(input())
nums = [1, 2, 3]

for n in nums:
  if((a != n) and (b != n):
     print(n)

Buggy submission (verdict: Runtime Error):
a = input()
b = input()
choices = '123'
for c in choises:
  if((c != a) and (c != b)):
    print(c)
Problem p02831 (python)

Fixed submission:
a, b = map(int, input().split())
def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
print(a * b // gcd(a, b))

Buggy submission (verdict: Runtime Error):
import math
a, b = map(int, input().split())
print(a * b // math.gcd(a, b))

Buggy submission (verdict: Runtime Error):
from math import gcd
a, b = map(int, input().split())
print(a * b // gcd(a, b))

Buggy submission (verdict: Runtime Error):
from math import gcd
a, b = map(int, input().split())
print(a * b // gcd(a, b))
Problem p02879 (python)

Fixed submission:
a, b = map(int, input().split())
if (a < 10) and (b < 10):
    print(a * b)
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
a, b = map(int, input().split())
if (a < 10) && (b < 10):
    print(a * b)
else:
    print(-1)
Problem p02916 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = 0
for i in range(n):
    sum += b[a[i]-1]
    if((i < n-1) and (a[i] < n) and (a[i+1] == a[i] + 1)):
        sum += c[a[i]-1]

print(sum)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = 0
for i in range(N):
    sum += b[a[i]]
    if((i < N-1) and (a[i+1] == (a[i] + 1))):
        sum += c[a[i]]

print(sum)
Problem p02819 (python)

Fixed submission:
def prime(n):
    for i in range(2, n):
        if n%i == 0: break
    else: return True
    return False

n = int(input())
while not prime(n): n += 1
else: print(n)

Buggy submission (verdict: Runtime Error):
from sympy import nextprime
print(nextprime(int(input())-1))
Problem p02819 (python)

Fixed submission:
from functools import lru_cache
 
@lru_cache(maxsize=100000)
def n_th_prime(n):
    if n == 0:
        return 2
    primes = [n_th_prime(k) for k in range(n)]
    k = 1
    x = primes[-1] + 1
    while True:
        for p in primes[:k]:
            if x % p == 0:
                x += 1
                break
        else:
            if x > p**2:
                k += 1
            else:
                return x

x = int(input())

k = 0
p = 2
while True:
    for i in range(k):
        p = n_th_prime(i)
        if x % p == 0:
            x += 1
            break
    else:
        if x > p**2:
            k += 1
        else:
            print(x)
            break

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
 
@lru_cache(maxsize=1e6)
def n_th_prime(n):
    if n == 0:
        return 2
    while True:
        for i in range(n):
            if x % n_th_prime(i) == 0:
                break
        else: return(x)
        x += 1

x = int(input())

k=0
while True:
    a = n_th_prime(k)
    if x > a:
        k += 1
    else:
        print(a)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

@lru_cache(maxsize=1e6)
def n_th_prime(n):
    if n == 0:
        return 2
    while True:
        for i in range(n):
            if x % n_th_prime(i) == 0:
                break
        else: return(x)
        x += 1
Problem p02820 (python)

Fixed submission:
n,k = (int(w) for w in input().split()[:2])
r,s,p = (int(w) for w in input().split()[:3])
t = input()

h = {'r': 'p', 's': 'r', 'p': 's'}
score = {'r': r, 's': s, 'p': p, 'e': 0}

z = [h[c] for c in t]
for i in range(k, n):
    if z[i]==z[i-k]: z[i] = 'e'

x = sum(score[v] for v in z)

print(x)

Buggy submission (verdict: Runtime Error):
n,k = (int(w) for w in input().split()[:2])
r,s,p = (int(w) for w in input().split()[:3])
t = input()

h = {'r': 'p', 's': 'r', 'p': 's'}
score = {'r': r, 's': s 'p': p}

x = sum(score[h[t[i]]] for i in range(k))

x += sum(score[h[c]] for c,cp in zip(t[k:], t) if c!=cp)

print(x)
Problem p02829 (python)

Fixed submission:
a = int(input())
b = int(input())
print(6-a-b)

Buggy submission (verdict: Runtime Error):
A = int(input())
B = int(input())
#A,Bは1,2,3のいずれか
#AとBは異なる
print(6-a-b)
Problem p02819 (python)

Fixed submission:
def nextprime(x):
    if pow(2, x-1, x) != 1:
        return nextprime(x+1)
    for i in range(2, x):
        if x % i == 0:
            return nextprime(x+1)
    return x


x = int(input())

if x == 2:
    print("2")
else:
    print(nextprime(x))

Buggy submission (verdict: Runtime Error):
def nextprime(x):
    if pow(2, x-1, x) != 1:
        return nextprime(x+1)
    for i in range(2, i*i):
        if x % i == 0:
            return nextprime(x+1)
    return x


x = int(input())

if x == 2:
    print("2")
else:
    print(nextprime(x))
Problem p03013 (python)

Fixed submission:
N, M = map(int,input().split(' '))
a = set([int(input()) for i in range(M)])
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
  if i in a:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[N])

Buggy submission (verdict: Runtime Error):
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))

Buggy submission (verdict: Runtime Error):
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

Buggy submission (verdict: Runtime Error):
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n <= 1 :
    return 1
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

Buggy submission (verdict: Runtime Error):
N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0:
    return 1
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  if n == 1:
    return 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))