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

import sys
import random
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
degorigin = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  degorigin[a] += 1
  degorigin[b] += 1
if n == 2:
  print("Second")
  exit()
stackorigin = []
root = 0
candidate = []
for i in range(1,n+1)[::-1]:
  if degorigin[i] == 1:
    stackorigin.append(i)
  else:
    candidate.append(i)
flg = 0
for _ in range(18):
  if flg:
    break
  stack = stackorigin[:]
  deg = degorigin[:]
  root = candidate[random.randint(0,len(candidate)-1)]
  deg[root] += 1
  dp = [[] for i in range(n+1)]
  parity = [-1]*(n+1)
  while stack:
    x = stack.pop()
    if dp[x]:
      if dp[x].count(0) >= 2:
        flg = 1
        break
      elif dp[x].count(2):
        parity[x] = 2
      elif dp[x].count(1) and dp[x].count(0):
        parity[x] = 2
      elif dp[x].count(1):
        parity[x] = 0
      elif dp[x].count(0):
        parity[x] = 1
    else:
      parity[x] = 0
    for y in graph[x]:
      if deg[y] >= 2:
        dp[y].append(parity[x])
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
if flg:
  print("First")
else:
  print("Second")

### FIXED CODE ###


import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
if n == 2:
  print("Second")
  exit()
stack = []
root = 0
for i in range(1,n+1)[::-1]:
  if deg[i] == 1:
    stack.append(i)
  else:
    root = i
flg = 0
deg[root] += 1
dp = [[] for i in range(n+1)]
dist = [-1]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    if dp[x].count(0)>=2:
      flg = 1
    if dp[x].count(0):
      dist[x] = 1
    else:
      dist[x] = 0
  else:
    dist[x] = 0
  for y in graph[x]:
    if deg[y] >= 2:
      dp[y].append(dist[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg or dist[root]==0:
  print("First")
else:
  print("Second")
### BUGGY CODE ###



from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact





N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1


print(count)


### FIXED CODE ###



from functools import *
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())




N = int(input())
A = []
for i in range(N):
    A.append(II())


if A[0] >0:
    print(-1)
    sys.exit()

for i in range(1, N):
    if A[i]-A[i-1] > 1:
        print(-1)
        sys.exit()

count = 0
x = [0]*N

for i in range(0,N-1):
    if A[i]+1==A[i+1]:
        count+=1
    else:
        count+=A[i+1]

""" for i in reversed(range(N)):
    if A[i] != x[i]:
        for j in range(i-A[i], i):
            x[j+1] = x[j]+1
            count += 1

 """
print(count)
### BUGGY CODE ###

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

for i in range(M//N, 0, -1):
  if M % i == 0:
    ans = i
    break
    
print(ans)

### FIXED CODE ###

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

for i in range(M//N, 0, -1):
  if M % i == 0:
    ans = i
    break
    
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
l = deque()
for _ in range(n):
    ss = input().split()
    order, string = ss[0], ss[1]
    if order == "insert":
        l.append(string)
    else:
        print('yes' if string in l else 'no')

### FIXED CODE ###

n = int(input())
l = {}
for _ in range(n):
    ss = input().split()
    order, string = ss[0], ss[1]
    if order == "insert":
        l[string] = 1
    else:
        print('yes' if string in l else 'no')
### BUGGY CODE ###

import itertools
n, x, y = map(int, input().split())

lst = [0 for _ in range(1, n)]
for _ in itertools.combinations([_ for _ in range(1, n+1)], 2):
    i, j = _[0], _[1] 
    ans = min(abs(i-j), abs(x-j)+1+abs(y-i),abs(x-i)+1+abs(y-j))
    lst[ans-1] += 1
    
for _ in lst:
    print(_)


### FIXED CODE ###

import itertools
n, x, y = map(int, input().split())

lst = [0 for _ in range(1, n)]
for _ in itertools.combinations([_ for _ in range(1, n+1)], 2):
    i, j = _[0], _[1] 
    ans = min(abs(i-j), abs(x-j)+1+abs(y-i),abs(x-i)+1+abs(y-j))
    lst[ans-1] += 1
    
for _ in lst:
    print(_)
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
d = 2 ** (H - 1)
mcut = 1008
for i in range(d):
  L = [0 for _ in range(H)]
  for j in range(1, H):
    L[j] = L[j-1] + i % 2
    i //= 2
  C = [0 for _ in range(L[H-1]+1)]
  cutp, cutq = True, True
  cut = L[H-1]
  for m in range(W):
    for l in range(H):
      C[L[l]] += int(S[l][m])
    if cutq:
      cutq = False
      if max(C) > K:
        cutp = False
        break
    else:
      if max(C) > K:
        cut += 1
        C = [0 for _ in range(L[H-1]+1)]
        for l in range(H):
          C[L[l]] += int(S[l][m])
    if cutp == False:
      break
  if cutp:
    if cut < mcut:
      mcut = cut
print(mcut)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
d = 2 ** (H - 1)
mcut = 1008
for i in range(d):
  L = [0 for _ in range(H)]
  for j in range(1, H):
    L[j] = L[j-1] + i % 2
    i //= 2
  C = [0 for _ in range(L[H-1]+1)]
  cutp, cutq = True, True
  cut = L[H-1]
  for m in range(W):
    for l in range(H):
      C[L[l]] += int(S[l][m])
    if cutq:
      cutq = False
      if max(C) > K:
        cutp = False
        break
    else:
      if max(C) > K:
        cut += 1
        C = [0 for _ in range(L[H-1]+1)]
        for l in range(H):
          C[L[l]] += int(S[l][m])
    if cutp == False:
      break
  if cutp:
    if cut < mcut:
      mcut = cut
print(mcut)
### BUGGY CODE ###

import itertools

n = int(input())
a = list(map(int,input().split()))
c = itertools.combinations(a, 2)
ini = 0
for v in c:
    ini += v[0]*v[1]
print(ini%(10**9+7))

### FIXED CODE ###

import itertools

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
ini = []
for i in range(n):
    s -= a[i]
    tmp = a[i]*s
    ini.append(tmp)
print(sum(ini)%(10**9+7))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

#print(an)
for i in range(k):
    b = [0] * n
    for j in range(n):
        lb = max(j - a[j], 0)
        ub = min(j + a[j], n - 1)

        b[lb] += 1
        if ub + 1 < n:
            b[ub + 1] -= 1
    #print(b)
    for j in range(1, n):
        b[j] += b[j - 1]

    #print('k =', i + 1)
    #print(b)
    if all(a == n for a in b):
        #print('done!')
        break
    a = b

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


### FIXED CODE ###

import numpy as np
from numba import njit

@njit('i8,i8,i8[::1]', cache=True)
def fn(n, k, a):
    for _ in range(k):
        b = np.zeros(n, dtype=np.int64)
        for i in range(n):
            lb = max(i - a[i], 0)
            ub = min(i + a[i], n - 1)

            b[lb] += 1
            if ub + 1 < n:
                b[ub + 1] -= 1

        a = b.cumsum()
        if np.all(a == n):
            return a
    return a

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = np.array(a, dtype=np.int64)

b = fn(n, k, a)
print(' '.join(b.astype(str)))
### BUGGY CODE ###

def solve():
    from operator import itemgetter
 
    turns = tuple(map(int, input().split()))[1]
    cardsList = sorted(list(map(int, input().split())))
 
    turnsList = [tuple(map(int, input().split())) for _ in range(turns)]
    for chances, num in sorted(turnsList, key=itemgetter(1), reverse=True):
        for i in range(chances):
            if num > cardsList[i]:
                cardsList[i] = num
            elif i == 0:
                return print(sum(cardsList))
            else:
                break
        cardsList.sort()
    print(sum(cardsList))
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter

def solve():
    cardsNum, turnsNum = tuple(map(int, input().split()))
    cards = sorted([int(x) for x in input().split()])
    turns = sorted([tuple(int(x) for x in input().split()) for _ in range(turnsNum)], key=itemgetter(1), reverse=True)
    
    largeCount = 0
    largeCards = [0,] * cardsNum
    for chances, num in turns:
        for _ in range(chances):
            if (largeCount < cardsNum):
                largeCards[largeCount] = num
                largeCount += 1
            else:
                break
        if (largeCount >= cardsNum):
            break 
    
    for i in range(cardsNum):
        if (largeCards[i] > cards[i]):
            cards[i] = largeCards[i]
        else:
            break
    print(sum(cards))
solve()
### BUGGY CODE ###

n = int(input())
count = 0
for i in range(n):
    count += i
print(count)

### FIXED CODE ###

n = int(input())
print(n * (n - 1) // 2)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
S = input()
for q in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count("AC"))

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().rstrip()

N, Q = map(int, input().split())
S = input()
li = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == 'AC':
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(li[r-1] - li[l-1])
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.sets = [set([i]) for i in range(n)]

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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
        self.sets[x] |= self.sets[y]

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


def main():
    N, M, K = list(map(int, input().split()))
    U = UnionFind(N)
    FR = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1].add(b - 1)
        FR[b - 1].add(a - 1)
    #BL = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        FR[c - 1].add(d - 1)
        FR[d - 1].add(c - 1)
    print(' '.join(str(len(U.sets[U.find(i)] - FR[i]) - 1) for i in range(N)))

main()


### FIXED CODE ###

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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 main():
    N, M, K = list(map(int, input().split()))
    U = UnionFind(N)
    FR = [0] * N
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1] += 1
        FR[b - 1] += 1
    r = [0] * N
    LS = {}
    for i in range(N):
        t = U.find(i)
        if t not in LS:
            LS[t] = set()
        LS[t].add(i)
        r[i] = -U.parents[t] - 1 - FR[i]
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c - 1, d - 1
        if d in LS[U.find(c)]:
            r[c] -= 1
            r[d] -= 1
    print(' '.join(str(i) for i in r))

main()
### BUGGY CODE ###

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

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

for i in range(1, N+1):
    w, v = map(int, input().split())
    for w_k in range(1, W+1):
        if w_k >= w:
            dp[i][w_k] = max(dp[i-1][w_k-w] + v, dp[i-1][w_k])
        else:
            dp[i][w_k] = dp[i-1][w_k]

print(max(dp[N]))


### FIXED CODE ###

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

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

for i in range(1, N+1):
    w, v = map(int, input().split())
    for w_k in range(1, W+1):
        if w_k >= w:
            dp[i][w_k] = max(dp[i-1][w_k-w] + v, dp[i-1][w_k])
        else:
            dp[i][w_k] = dp[i-1][w_k]

print(max(dp[N]))
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]
for i in range(len(ansListab)):
  for j in range(z):
    ansList.append(ansListab[i]+c[j])

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a= list(map(int, input().split()))
b= list(map(int, input().split()))
c= list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### BUGGY CODE ###

from operator import mul
from functools import reduce
from bisect import*
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,*a=map(int,open(0).read().split())
a.sort()
b=a.pop()
#print(a)
if n>10:
    x=bisect_left(a,b//2)
    if x>=n-1:
        print(b,a.pop())
    else:
        z=[cmb(b,a[i])for i in range(x-2,x+1)]
        y=max(z)
        print(b,a[x+z.index(y)-1])
elif n==2:
    print(b,*a)
else:
    z=[cmb(b,a[i])for i in range(n-1)]
    y=a[z.index(max(z))]
    print(b,y)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
b=a.pop()
dif=float("inf")
ans=0
for i in range(n-1):
    if abs(a[i]-b/2)<dif:
        ans=a[i]
        dif=abs(a[i]-b/2)
print(b,ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    l = [0] * (n + 1)
    for j in range(n):
        l[max(0, j - a[j])] += 1
        l[min(n, j + a[j] + 1)] -= 1
    for j in range(n - 1):
        l[j + 1] += l[j]
    a = l
    if set(a) == set([n]):
        break
print(*a[:n])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    l = [0] * (n + 1)
    for j in range(n):
        l[max(0, j - a[j])] += 1
        l[min(n, j + a[j] + 1)] -= 1
    for j in range(n - 1):
        l[j + 1] += l[j]
    a = l
    if a.count(n) == n:
        break
print(*a[:n])
### BUGGY CODE ###

m = 10000
g = 5000
s = 1000
n, y = map(int, input().split())
if y > n * m or y < n * s:
    print("-1 -1 -1")
    exit()
if y / n == 10000:
    print(n, "0 0")
    exit()
elif y / n == 5000:
    print("0", n, "0")
    exit()
elif y / n == 1000:
    print("0 0", n)
    exit()
if y / n > 5000:
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1):
                if i * s + j * g + h * m == y and i + j + h == n:
                    print(h, j, i)
                    exit()
    for i in range(n):
        for j in range(n-i+1):
            for h in range(n-j+1):
                if i*m+j*g+h*s==y and i+j+h == n:
                    print(i, j, h)
                    exit()
    else:
        print("-1 -1 -1")
else:
    for i in range(n):
        for j in range(n-i+1):
            for h in range(n-j+1):
                if i*m+j*g+h*s==y and i+j+h == n:
                    print(i, j, h)
                    exit()
    for i in range(n):
        for j in range(n - i+1):
            for h in range(n - j+1):
                if i * s + j * g + h * m == y and i + j + h == n:
                    print(h, j, i)
                    exit()
    else:
        print("-1 -1 -1")

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")
### BUGGY CODE ###

import math

k = int(input())

sum = 0
i, j = 0, 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            i = math.gcd(a, b)
            j = math.gcd(i, c)
            sum += j

print(sum)

### FIXED CODE ###

from math import gcd

k = int(input())

sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += gcd(gcd(a, b), c)

print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    map = [[0 for _ in range(W)] for _ in range(H)]
    que = []
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.pop(0)
        # 左
        if xw - 1 >= 0:
            if Sn[xh][xw] != Sn[xh][xw-1] and map[xh][xw-1] == 0:
                que.append((xh, xw-1))
                map[xh][xw-1] = Sn[xh][xw-1]
        # 上
        if xh - 1 >= 0:
            if Sn[xh][xw] != Sn[xh-1][xw] and map[xh-1][xw] == 0:
                que.append((xh-1, xw))
                map[xh-1][xw] = Sn[xh-1][xw]
        # 右
        if xw + 1 < W:
            if Sn[xh][xw] != Sn[xh][xw+1] and map[xh][xw+1] == 0:
                que.append((xh, xw+1))
                map[xh][xw+1] = Sn[xh][xw+1]
        # 下
        if xh + 1 < H:
            if Sn[xh][xw] != Sn[xh+1][xw] and map[xh+1][xw] == 0:
                que.append((xh+1, xw))
                map[xh+1][xw] = Sn[xh+1][xw]

    cnt = 0
    for i in range(H):
        for j in range(W):
            if map[i][j] == ".":
                cnt += 1
    return cnt

cnt = 0
for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#":
            cnt += func(i,j)

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    move = [(0,-1),(-1,0),(0,1),(1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if Sn[xh][xw] == "#":
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
            
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw < W:
                if Sn[xh][xw] != Sn[xh + mh][xw + mw] and visited[xh + mh][xw + mw] == 0:
                    que.append((xh + mh, xw + mw))

    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            b_cnt, w_cnt = func(i, j)
            cnt += b_cnt*w_cnt
            
print(cnt)
### BUGGY CODE ###

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

adj_mat = [[False] * N for i in range(N)]
friends_list = [1] * N 

for i in range(M):
    a, b = map(int, input().split())
    a -= 1;
    b -= 1;

    if (not adj_mat[a][b]):
        friends_list[a] += 1
    if (not adj_mat[b][a]):
        friends_list[b] += 1

    adj_mat[a][b] = True
    adj_mat[b][a] = True

max_friends = 0
for f_num in friends_list:
    max_friends = max(f_num, max_friends)

print(max_friends)


### FIXED CODE ###

class UFTree:
    def __init__(self, N):
        self.nodes = [Node(i) for i in range(N)]
        self.N = N

    def find_max_child_num(self):
        result = 0
        for i in range(self.N):
            result = max(result, self.nodes[i].child_num)
        return result

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        self.child_num = 0
        self.rank = 1

    def get_root(self):
        if self.parent is None:
            return self
        
        return self.parent.get_root()

    def is_in_same_tree(self, another):
        return self.get_root().ID == another.get_root().ID

    def concat(self, another):
        if self.is_in_same_tree(another):
            return

        sr = self.get_root()
        ar = another.get_root()

        if sr.rank > ar.rank:
            parent, child = sr, ar
        else:
            parent, child = ar, sr

        parent.child_num += child.child_num + 1
        parent.rank = max(parent.rank, child.rank + 1)
        child.parent = parent

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

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

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    tree.nodes[a].concat(tree.nodes[b])

# # for debug
# for i in range(N):
#     n = tree.nodes[i]
#     if n.parent is None:
#         print(i + 1, "is root")
#     else:
#         print("parent of", i + 1, "is", n.parent.ID + 1)

print(tree.find_max_child_num() + 1)
### BUGGY CODE ###

S = input()

N = len(S)

ans = [0]*N

for i in range(N) :
    if S[i] == "R" :
        j = S[i:].find("L")
        if j % 2 == 0 :
            ans[i+j] += 1
        else :
            ans[i+j-1] += 1
    else :
        j = S[:i+1][::-1].find("R")
        if j % 2 == 0 :
            ans[i-j] += 1
        else :
            ans[i-j+1] += 1
print(*ans)
            
        


### FIXED CODE ###

S = input()
N = len(S)
ans = [0]*N

cnt = 0
for i in range(N) :
    if S[i] == "R" :
        cnt += 1

    elif cnt % 2 == 0 :
        ans[i] += cnt//2
        ans[i-1] += cnt//2
        cnt = 0
    else :
        ans[i] += cnt//2
        ans[i-1] += cnt//2 + 1
        cnt = 0
cnt = 0
for i in range(N-1,-1,-1) :
    if S[i] == "L" :
        cnt += 1
    
    elif cnt % 2 == 0 :
        ans[i] += cnt//2
        ans[i+1] += cnt//2
        cnt = 0
    else :
        ans[i] += cnt//2
        ans[i+1] += cnt//2 + 1
        cnt = 0
print(*ans)
### BUGGY CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
a = []
for i in range(m):
    a.append(int(input()))

pat = [1]
zero = False
for i in range(1, n + 1):
    if i - 1 in a and i - 2 in a:
        zero = True
        break
    if i in a:
        pat.append(0)
        continue
    cnt = 0
    if i - 1 not in a:
        cnt = (cnt + pat[i - 1]) % mod
    if i - 2 >= 0 and i - 2 not in a:
        cnt = (cnt + pat[i - 2]) % mod
    pat.append(cnt)

if zero:
    print(0)
else:
    print(pat[n])


### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 2)
pat[0] = 1
pat[1] = 1

for i in range(m):
    a = int(input())
    pat[a] = -1

for i in range(2, n + 1):
    if pat[i] < 0:
        continue
    if pat[i - 1] > 0:
        pat[i] = (pat[i] + pat[i - 1]) % mod
    if pat[i - 2] > 0:
        pat[i] = (pat[i] + pat[i - 2]) % mod

print(pat[n])