Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    global ifReached
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
count = 0
unreachable = False
while True:
    n_stack = indicate3(stack,path)
    diffcount = 0
    for position in n_stack:
        if ifReached[position-1] == False:
            ifReached[position-1] = True
            diffcount += 1

    if diffcount == 0:
        print(-1)
        break
        
    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
            if unreachable == True:
                print(-1)
                break
    stack = n_stack


### FIXED CODE ###

n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))
ifReached = [False for _ in range(n)]

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = list(set(next))
    return start

stack = [s]
ifReached[s-1] = True
count = 0
while True:
    n_stack = list(set(indicate3(stack,path)))

    tmp_stack = []
    for position in n_stack:
        if ifReached[position-1] == False:
            tmp_stack.append(position)
            ifReached[position-1] = True

    if len(tmp_stack) == 0:
        print(-1)
        break

    count += 1
    if g in tmp_stack:
        print(count)
        break
    stack = tmp_stack
### BUGGY CODE ###

# coding: utf-8
import math

N = int(input())
A = list(map(int, input().split()))
A_sum = sum(A)

res = [0 for i in range(N)]

for i in range(N):
    res[i] = A_sum - 2 * sum([A[(i+(2*j+1)) % N] for j in range(int((N-1)/2))])

print(' '.join(map(str, res)))

### FIXED CODE ###

# coding: utf-8
import math

N = int(input())
A = list(map(int, input().split()))
A_sum = sum(A)

res = list()
res.append(A_sum - 2 * sum([A[(2*j+1)] for j in range(int((N-1)/2))]))

for i in range(1, N):
    res.append(2*A[i-1] - res[i-1])

print(' '.join(map(str, res)))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]

for i in range(q):
    a = list_score[i]
    b = list_s[a[0]-1:a[1]]
    c = "".join(b)
    print(c.count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
list_s = list(s)
list_score = [ list(map(int,input().split(" "))) for i in range(q)]
list_c = [0]
a = 0
for i in range(n-1):
    if list_s[i] == "A" and list_s[i+1] == "C":
        a += 1
        list_c.append(a)
    else:
        list_c.append(a)

for i in range(q):
    g = list_score[i]
    print(list_c[g[1]-1]-list_c[g[0]-1])
### BUGGY CODE ###

N = int(input())
sara = []
t_s = 0
a_s = 0
for i in range(N):
    A, B = map(int, input().split())
    sara.append([A, B])
while True:
    if len(sara) == 0:
        break
    sara.sort(key=lambda x:(x[0],x[1]-x[0]), reverse=True)
    res = sara.pop(0)
    t_s += res[0]
    if len(sara) == 0:
        break
    sara.sort(key=lambda x:(x[1],x[0]-x[1]), reverse=True)
    res = sara.pop(0)
    a_s += res[1]
print(t_s - a_s)

### FIXED CODE ###

N = int(input())
sara = []
t_s = 0
a_s = 0
for i in range(N):
    A, B = map(int, input().split())
    sara.append([A, B])
sara.sort(key=lambda x:x[0]+x[1], reverse=True)
while True:
    if len(sara) == 0:
        break
    t_s += sara.pop(0)[0]
    if len(sara) == 0:
        break
    a_s += sara.pop(0)[1]
print(t_s - a_s)
### BUGGY CODE ###

from bisect import *
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans=0
for c in C:
    for b in B[:bisect_left(B,c)]:
        ans+=bisect_left(A,b)
print(ans)

### FIXED CODE ###

from bisect import *
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans=0
for b in B:
    ans+=(n-bisect(C,b))*bisect_left(A,b)
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key=lambda x:x[0])
for e in E:
  p = e[0] if e[0] in T[1][2] else e[1]
  if 1 in e:
    p = 1
  c = e[0]+e[1]-p
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

# DP
inf = float("inf")
dp = [inf for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    for k in range(1, K+1):
        if i - k < 0:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
print(dp[-1])

### FIXED CODE ###

# Educational DP Contest B-Frog 2

def frog(N, K, h):
    # initialize
    inf = float('inf')
    dp = [inf] * N
    
    minKN = min(K, N)
    for i in range(minKN):
        if i == 0:
            dp[i] = 0
        else: 
            dp[i] = abs(h[0] - h[i])
            for j in range(minKN):
                if j == i:
                    continue
                elif j < i:
                    dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    # DP
    for i in range(N):
        if i == 0:
            continue
        elif i < K:
            continue
        else:
            dp[i] = min([abs(h[k] - h[i]) + dp[k] for k in range(i-K, i)])
    return dp[N-1]
    
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    print(frog(N, K, h))
### BUGGY CODE ###

n = int(input())
s = input()
seq = list(set(list(s)))
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
ans = []
for a in range(len(genkai_list)):
    for i in range(len(s)):
        if s[i] == genkai_list[a][0]:
            for j in range(i + 1, len(s)):
                if s[j] == genkai_list[a][1]:
                    for k in range(j + 1, len(s)):
                        if s[k] == genkai_list[a][2]:
                            ans.append(a)
                            break # break1
                    else:  # break1されなかった場合
                        continue
            else:
                continue # jのループが全部回った（2文字目で一致しなかった）ら、iを次の文字に
    else:
        continue # iのループが全部回った（1文字目で一致しなかった）ら、aを次の文字に
                
print(len(set(ans)))

### FIXED CODE ###

n = int(input())
s = list(input())
genkai_list = []
for i in range(0,1000):
    if 0 <= i <= 9:
        ap = "00" + str(i)
        genkai_list.append(ap)
    elif 10 <= i <= 99:
        ap = "0" + str(i)
        genkai_list.append(ap)
    else:
        genkai_list.append(str(i))
count = 0
for a in genkai_list:
    try:
        s_ = s[s.index(a[0])+1:]
        s__ = s_[s_.index(a[1])+1:]
        if a[2] in s__:
            count += 1
    except:
        continue
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

    dp = [[0]*(W+1) for _ in range(N+1)]

    for j in range(W+1):
        dp[0][j] = 0

    for i in range(0, N):
        for j in range(W+1):
            if j < w[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])

    print(dp[N][W])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    w = np.zeros(N, dtype=int)
    v = np.zeros(N, dtype=int)
    for i in range(N):
        w[i], v[i] = map(int, input().split())

    dp = np.zeros((N+1, W+1), dtype=np.int64)

    for i in range(0, N):
        dp[i+1][:w[i]] = dp[i][:w[i]]
        dp[i+1][w[i]:] = np.maximum(dp[i][w[i]:], dp[i][:-w[i]] + v[i])

    print(dp[N][W])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

L,R=map(int,input().split())
min=20000
for i in range(L,R): #L～R-1
    for j in range(i+1,R+1): #i+1～R
        a=(i*j)%2019
        if a<min:
            min=a
print(min)

### FIXED CODE ###

L,R=map(int,input().split())
min=20000
newR=L+2019
if newR<R: #Rを小さくする
    R=newR
for i in range(L,R): #L～R-1
    for j in range(i+1,R+1): #i+1～R
        a=(i*j)%2019
        if a<min:
            min=a
print(min)
### BUGGY CODE ###

import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[0]*n for i in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        
        now, p, d = q.popleft()
        if now==p:
            continue
        if visited[now]==1:
            continue
        
        ans[now]=p+1
        dis[now]=d+1
        visited[now]=1
        for i in range(len(edge[now])):
            if visited[edge[now][i]]==0:
                q.append((edge[now][i], now, dis[now]))
                
                visited[edge[now][i]]==1
bfs(0)

flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

### FIXED CODE ###

import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[] for _ in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        visited[now]=1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            if e==now:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=[]
for i in range(100001):
    A_count.append(A.count(i))
for i in range(Q):
    A_sum+=(BC[i][1]-BC[i][0])*A_count[BC[i][0]]
    A_count[BC[i][1]]+=A_count[BC[i][0]]
    A_count[BC[i][0]]=0
    print(A_sum)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
#BC=[]
#for i in range(Q):
#    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=Counter(A)

for i in range(Q):
    B,C=(map(int,input().split()))
    A_sum+=(C-B)*A_count[B]
    A_count[C]+=A_count[B]
    A_count[B]=0
    print(A_sum)
### BUGGY CODE ###

S = str(input())

count = 0
T = ""
while((len(S) >= 1) and ("0" in S) and ("1" in S)):
    if (S[0:2] == "01") or (S[0:2] == "10"):
        count += 2
        S = S[2:]
        T += S
        S = T
        T = ""
    else:
        T += S[0]
        S = S[1:]
print(count)

### FIXED CODE ###

S = str(input())

zero_num = 0
one_num = 0

for i in range(len(S)):
    if S[i] == "0":
        zero_num += 1
    else:
        one_num += 1

print(2*min(zero_num, one_num))
### BUGGY CODE ###

x=int(input())
for i in range(1,int(x**(1/2))+1):
    if x%i:continue

    ar,s=i,x//i
    pre=[]
    if pow(ar,5,5)%5==x%5:pre.append(ar)
    if  pow(s,5,5)%5==x%5:pre.append(s)

    for a in pre:
        d=(x-a**5)//5//a
        if d==0:print(a,0);exit()
        for b in range(1,int(abs(d)**(1/2))+1):
            if d%b:continue
            if a**3+2*b*a**2+2*b**2*a+b**3==d//b:
                print(a+b,b);exit()
            if a**3-2*b*a**2+2*b**2*a-b**3==-(d//b):print(a-b,-b);exit()


### FIXED CODE ###

x=int(input())
for i in range(-120,121):
  for j in range(-120,121):
    if pow(i,5)-pow(j,5)==x:
      print(i,j);exit()
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
ans = 0
x = [True]*n
for i in range(n):
    if (x[i]==False):
        continue
    t = uf.members(i)
    ans = max(ans,len(t))
    for j in t:
        x[j] = False
print(ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
ans = 0
x = uf.parents
for i in range(n):
    if x[i]<0:
        #print(i)
        ans = max(ans,uf.size(i))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    

N,Q = map(int,input().split())


a=[]
b=[]

p=[]
x=[]

#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())
    a.append(a0)
    b.append(b0)
    
    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())
    p.append(p0)
    x.append(x0)
    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    
def input():
    return sys.stdin.readline()[:-1]

N,Q = map(int,input().split())


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")
### BUGGY CODE ###

n , k = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(n-k+1):
  ans = max(ans, sum(p[i:i+k])+k)
print(ans/2)

### FIXED CODE ###

n , k = map(int,input().split())
p = list(map(int,input().split()))
P = []
ans = sum(p[0:k])+k
P.append(ans)
for i in range(1,n-k+1):
  ans =  ans - p[i-1] + p[i+k-1]
  P.append(ans)
  
print(max(P)/2)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]
    for t in range(k+1,N):
      s3=S[t]
      if s1==s2:
        break
      if s3==s1 or s3==s2:
        continue
      elif t-k != k-i:
        ans+=1
print(ans)        

### FIXED CODE ###

N=int(input())
S=input()
ans=0
RGB=[0,0,0]
for i in range(N):
  if S[i]=="R":
    RGB[0]+=1
  if S[i]=="G":
    RGB[1]+=1
  if S[i]=="B":
    RGB[2]+=1
ans=RGB[0]*RGB[1]*RGB[2]    
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]
    t=k+k-i
    if s1==s2:
      continue
    if t<=N-1:
      s3=S[t]
      if s3!=s1 and s3!=s2:
        ans-=1      
print(ans)
### BUGGY CODE ###


def partsolve(As, x):
    """
    :param As:
    :param x:
    :return: Asの積のペアの中で、x未満となるペアの個数
    """
    count = 0
    for i, a in enumerate(As):
        if a >= 0:
            l = 0
            r = len(As) - 1
            if As[r] * a < x:
                count += len(As)
            elif As[l] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        l = m
                    else:
                        r = m
                count += l + 1
            if a * a < x:
                count -= 1
        else:
            # a < 0
            l = 0
            r = len(As) - 1
            if As[l] * a < x:
                count += len(As)
            elif As[r] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        r = m
                    else:
                        l = m
                count += len(As) - r
            if a * a < x:
                count -= 1
    return count // 2

def solve(N, K, As):
    As = sorted(As)
    left = -10**18 - 1
    right = 10**18 + 1
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(As, mid)
        if c < K:
            left = mid
        else:
            right = mid
    return left

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))


### FIXED CODE ###

import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    F[0] = 1
    if 1 not in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 not in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()