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

from collections import deque


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)


graph2 = [[] for i in range(n)]
q = deque()
q.append([s - 1, 0])
visited = [float("inf")] * n
visited[0] = 0

while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 != 0:
            q.append([i, times + 1])
        if (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append([i, times+1])

if visited[t-1] == float("inf"):
    print(-1)
else:
    print(visited[t-1]//3)
    

### FIXED CODE ###

import sys
from collections import deque


input = sys.stdin.readline
n, m = map(int, input().split())
info = tuple(map(int, input().split()) for i in range(m))
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)

q = deque()
q.append((s - 1, 0))
INF = 10 ** 10
visited = [10 ** 10] * n
visited_1 = [10 ** 10] * n
visited_2 = [10 ** 10] * n
visited[s - 1] = 0
while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 == 1 and times + 1 < visited_1[i]:
            visited_1[i] = times + 1
            q.append((i, times + 1))

        elif (times + 1) % 3 == 2 and times + 1 < visited_2[i]:
            visited_2[i] = times + 1
            q.append((i, times + 1))
            
        elif (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times + 1))

if visited[t - 1] == 10 ** 10:
    print(-1)
else:
    print(visited[t-1]//3)
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def eratosthenes(lim):
  is_p=[2]*lim

  is_p[0]=0
  is_p[1]=1

  for i in range(2,lim):
    if 1==1:
#    if is_p[i]==2:
#      cnt=2
      for j in range(i*2,lim,i):
#        cnt+=1
#        is_p[j] = cnt
        is_p[j] += 1

  return is_p

lim=n+1
is_p=eratosthenes(lim)

#print(is_p)

ans=0
for i in range(1,n+1):
  ans+=i*is_p[i]
print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

def eratosthenes(lim):
  is_p=[2]*lim

  is_p[0]=0
  is_p[1]=1

  for i in range(2,lim):
    if 1==1:
#    if is_p[i]==2:
#      cnt=2
      for j in range(i*2,lim,i):
#        cnt+=1
#        is_p[j] = cnt
        is_p[j] += 1

  return is_p

lim=n+1
is_p=eratosthenes(lim)

#print(is_p)

ans=0
for i in range(1,n+1):
  ans+=i*is_p[i]
print(ans)
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
kk=k
ans=0
while k>=1:
    k-=1
    if a>=1:
        a-=1
        ans+=1
    elif b>=1:
        b-=1
    elif c>=1:
        c-=1
        ans-=1
print(ans)


### FIXED CODE ###

a,b,c,k=map(int,input().split())
ans=0
if k<a:
    ans+=k
elif k<a+b:
    ans+=a
elif k<=a+b+c:
    ans=ans+a-(k-a-b)
print(ans)
### BUGGY CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sumABs = [A + B for A, B in product(As, Bs)]
sumABs.sort(reverse=True)

sumABCs = [sumAB + C for sumAB, C in product(sumABs[:K], Cs)]
sumABCs.sort(reverse=True)

print('\n'.join(map(str, sumABCs[:K])))


### FIXED CODE ###

from heapq import heapify, heappush, heappop, heappushpop

X, Y, Z, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))

sum12s = []
for A in As:
    for B in Bs:
        sum12s.append(A+B)
sum12s.sort(reverse=True)

PQ = [Cs[0]+sum12 for sum12 in sum12s[:K]]
heapify(PQ)
for C in Cs[1:]:
    for sum12 in sum12s[:K]:
        heappush(PQ, C+sum12)
    for _ in range(K, len(PQ)):
        heappop(PQ)

anss = []
for _ in range(K):
    anss.append(heappop(PQ))
print('\n'.join(map(str, anss[::-1])))
### BUGGY CODE ###

from functools import lru_cache


@lru_cache(maxsize=2**17, typed=int)
def comb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p


def main():
    n, k = map(int, input().split())
    a = sorted(int(i) for i in input().split())
    mod = 10**9 + 7
    f = 0
    for i in range(n - k + 1):
        f = (f + a[k + i - 1] * comb(k - 1 + i, k - 1, mod) % mod) % mod
        f = (f - a[i] * comb(n - 1 - i, k - 1, mod) % mod) % mod
    print(f)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = sorted(int(i) for i in input().split())
    mod = 10**9 + 7
    comb = [1] * (n - k + 1)
    for i in range(n - k):
        comb[i + 1] = (comb[i] * (k + i) * pow(i + 1, mod - 2, mod)) % mod
    f = 0
    for i in range(n - k + 1):
        f = (f + a[k + i - 1] * comb[i] % mod) % mod
        f = (f - a[i] * comb[-1 - i] % mod) % mod
    print(f)


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

import sys
for line in sys.stdin.readlines():
  n = int(line)
  count_ = 0
  for i in range(n):
    count = 0
    for j in range(i+1):
      if (i+1) % (j+1) == 0:
        count += 1
    if count == 2:
      count_ += 1
  print(count_)

### FIXED CODE ###

lst = [1 for i in range(10 ** 6 + 1)]
lst[0] = lst[1] = 0
for i in range(10 ** 6 + 1):
  if lst[i] == 1:
    for j in range(i * 2, 10 ** 6 + 1, i):
      lst[j] = 0
while 0 == 0:
  try:
    n = int(input())
    c = 0
    for i in range(n + 1):
      c += lst[i]
    print(c)
  except EOFError:
    break
### BUGGY CODE ###

m = int(input())
def calc(m):
    for h in range(1, 3500):
        for n in range(1, 3500):
            for w in range(1, 3500):
                if 4 * h * n * w == m * (w * n + w * h  + h * n):
                    return h, n, w
print('{0[0]} {0[1]} {0[2]}'.format(calc(m)))

### FIXED CODE ###

N = int(input())
def calc(N):
    for h in range(1, 3500):
        for n in range(1, 3500):
            if 4 * h * n - N * n - N * h > 0 and (N * h * n) % (4 * h * n - N * n - N * h) == 0:
                w = (N * h * n) / (4 * h * n - N * n - N * h)
                return h, n, int(w)
print('{0[0]} {0[1]} {0[2]}'.format(calc(N)))
### BUGGY CODE ###

n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append((b-1, i))
  adj[b-1].append((a-1, i))
max_degree = 0
for i in range(n):
  degree = len(adj[i])
  if degree > max_degree:
    root = i
    max_degree = degree
color = [[] for _ in range(n)]
edge = [0] * (n - 1)
queue = [root]
parent = [root] * n
while queue:
  vertex = queue.pop()
  c = 1
  for v, i in adj[vertex]:
    if parent[vertex] == v:
      continue
    while c in color[v] or c in color[vertex]:
      c += 1
    color[v].append(c)
    color[vertex].append(c)
    edge[i] = c
    queue.append(v)
    parent[v] = vertex
    c += 1
print(max_degree)
for c in edge:
  print(c)

### FIXED CODE ###

n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append((b-1, i))
  adj[b-1].append((a-1, i))
max_degree = 0
for i in range(n):
  degree = len(adj[i])
  if degree > max_degree:
    root = i
    max_degree = degree
color = [[] for _ in range(n)]
edge = [0] * (n - 1)
queue = [root]
parent = [root] * n
while queue:
  vertex = queue.pop()
  c = 1
  for v, i in adj[vertex]:
    if parent[vertex] == v:
      continue
    while c in color[v] or c in color[vertex]:
      c += 1
    color[v].append(c)
    color[vertex].append(c)
    edge[i] = c
    queue.append(v)
    parent[v] = vertex
    c += 1
print(max_degree)
for c in edge:
  print(c)
### BUGGY CODE ###

num = int(input())
result = 0
for x in range(num):
  result = result + x
print(result)

### FIXED CODE ###

num = int(input())
result = num * (num - 1) // 2
##  初項0, 公差1, 項数numの等差数列の和= num(2a + (num - 1)d)/2
print(int(result))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import itertools
n=int(input())
a=list(map(int,input().split()))
a.sort()
#print(a)
c=[i for i in range(1,a[-1]+1)]

ans=0
for i in range(n-1):
    l=len(list(itertools.combinations(c,a[i])))
    if l>=ans:
        ans=l
        z=a[i]

print(a[-1],z)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
a.sort()
#print(a)
if n%2==0:
    c=a[-1]//2
else:
    c=a[-1]//2+0.5
#print(c)
b=[]
for i in range(n):
    b.append(abs(c-a[i]))
#print(b)
c=min(b)
for i in range(n):
    if b[i]==c:
        print(a[-1],a[i])
        break
### BUGGY CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    for i in range(N-1,-1,-1):
        mod = (mod+10**(N-1-i)*int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(ans)


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    for i in range(N-1,-1,-1):
        mod = (mod+pow(10,(N-1-i),P)*int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

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

L1,R1 = map(int,input().split())
through = set(range(L1,R1+1))
for i in range(M-1):
    L,R = map(int,input().split())
    through = through & set(range(L,R+1))
print(len(through))

### FIXED CODE ###

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

through_list = []
for i in range(M):
    L,R = map(int,input().split())
    through_list.append([L,R])
through_list.sort()
ans_range = through_list[0]
for i in range(M-1):
    ans_range = [max(ans_range[0],through_list[i+1][0]),min(ans_range[1],through_list[i+1][1])]
ans = ans_range[1]-ans_range[0]+1 
ans = max(0,ans)
print(ans)
### BUGGY CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())


### FIXED CODE ###

from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())
### BUGGY CODE ###

n,m = map(int,input().split()) #nがカードの数、mがBの数
a = list(map(int, input().split()))
b = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
  a.extend([b[i][1]]*b[i][0])
a.sort(reverse=True)
ans = 0
for i in range(n):
  ans += a[i]
print(ans)

### FIXED CODE ###

import numpy as np

n,m = map(int,input().split()) #nがカードの数、mがBの数
a = list(map(int, input().split())) #数のカウント
b = [1 for i in range(n)] #枚数カウント

for i in range(m):
  x, y = map(int, input().split())
  b.append(x)
  a.append(y)
c = np.array(a) #カードの数字
d = np.array(b) #カードの枚数
e = np.argsort(-c) #インデックスをカードの数字の大きい順にソート
#print(c,d,e)
ans = 0
N = 0 #取った枚数のカウント
i = 0
while N < n:
  j = e[i]
  if N + d[j] <= n:
    ans += c[j]*d[j]
    N += d[j]
    i += 1
  else:
    ans += c[j]*(n-N)
    N = n
    i += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter

l = Counter(A).most_common()
l = [b for a, b in l]

maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    l = [b for a, b in l]
    while l[K] > 0:
        for i in range(K+1):
            l[i] -= 1
        l.sort(reverse = True)
        maximum_operation[K] += 1

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0

while ans <= len(s)//2:
    for i in range(1, len(s)//2+1):
        if s[:i] in s[i:]:
            if s[:i+1] in s[i+1:]:
                continue
            else:
                ans = max(ans, len(s[:i]))
    s = s[1:]
    if len(s) == 1:
        break

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ans = 0

while ans <= len(s)//2:
    prev_s = ''
    for i in range(ans+1, len(s)//2+1):
        if s[:i] in s[i:]:
            prev_s = s[:i]
        else:
            ans = max(ans, len(prev_s))
            break
    else:
        ans = max(ans, len(prev_s))
    s = s[1:]
    if len(s) == 1:
        break

print(ans)
### BUGGY CODE ###

def solve(a,i,sa,sb):
	if 2*sa >= all: return 2*sa-all
	if 2*sb >= all: return 2*sb-all
	return min(solve(a,i+1,sa+a[i],sb),solve(a,i+1,sa,sb+a[i]))
	
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	print solve(a,0,a[0],0)

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

def main():
    from functools import reduce

    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    def lcm(a, b):
        return a * b // gcd(a, b)

    mod = 10 ** 9 + 7

    n = int(input())
    *a, = map(int, input().split())

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + L * pow(x, mod - 2, mod)) % mod
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from functools import reduce

    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    def lcm(a, b):
        return a * b // gcd(a, b)

    mod = 10 ** 9 + 7

    n = int(input())
    *a, = map(int, input().split())

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + pow(x, mod - 2, mod)) % mod
    ret = ret * L % mod
    print(ret)


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

n,*l = map(int, open(0).read().split())
 
ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] < l[j]+l[k]:
                if l[j] < l[i]+l[k]:
                    if l[k] < l[i]+l[j]:
                        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = sorted(map(int, input().split()))
 
ans = 0
for i in range(n):
    for j in range(i+1, n):
        big = l[i]+l[j]
    
        ch_max = n
        ch_min = j+1
        
        while ch_min < ch_max:
            ch_i = (ch_min + ch_max) // 2
            if l[ch_i] < big:
                ch_min = ch_i + 1
            else:
                ch_max = ch_i
                
        big_i = ch_max
        
        ans += big_i - (j + 1)
                
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
c = []
for i in range(M):
	c.append(list(map(int, input().split())))

for i in range(M):
	if c[i][0] == 1:
		for j in range(M):
			if c[j][0] == c[i][1]:
				if c[j][1] == N:
					print('POSSIBLE')
					exit()

print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
c = []
for i in range(M):
	c.append(list(map(int, input().split())))
d = []
e = []


for i in range(M):
	if c[i][0] == 1:
		d.append(c[i][1])

for i in range(M):
	if c[i][1] == N:
		e.append(c[i][0])

l = list(set(d) & set(e))

if l == []:
	print('IMPOSSIBLE')
else:
	print('POSSIBLE')
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))

### FIXED CODE ###

n, m = map(int,input().split())
a = set([int(input()) for i in range(m)])

p,q=(0,1)
#累積和っぽい考え
for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))
### BUGGY CODE ###

from itertools import combinations

N = int(raw_input())
L = map(int, raw_input().split())


def number_of_triangles():
    if N < 3:
        return 0
    return sum(1 for a, b, c in combinations(L, 3) if a < b + c and b < c + a and c < a + b)

print number_of_triangles()


### FIXED CODE ###

from bisect import bisect_left

N = int(raw_input())
L = map(int, raw_input().split())

L.sort()
result = 0
for i in xrange(N-2):
    a = L[i]
    for j in xrange(i+1, N-1):
        b = L[j]
        k = bisect_left(L, a + b, j + 1)
        result += k - (j + 1)
print result
### BUGGY CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
d = []
heapify(d)
heappush(d,(0,sh,sw))
ans = float('inf')
while len(d)>0:
  cnt,h,w = heappop(d)
  if visited[h][w]<=cnt:
    continue
  if cnt>ans:
    break
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        heappush(d,(cnt,h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        heappush(d,(cnt+1,h2,w2))
ans = ans if ans<float('inf') else -1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)