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

import bisect


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


N = int(input())
xd_array = [list(map(int, input().split())) for _ in range(N)]

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)

for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = tree.get_maximum(i, max_index)
    tree.update(i, max(max_move, i))

ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    ans_array[i] = (ans_array[i+1] + ans_array[tree.get(i) + 1]) % mod

print(ans_array[0])


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def get_maximum(self, l, r):
        L = l+self.len
        R = r+self.len
        ANS = -1 << 30

        while L < R:
            if L & 1:
                ANS = max(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = max(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


N = int(input())
xd_array = [list(map(int, input().split())) for _ in range(N)]

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = max(i, tree.get_maximum(i, max_index))
    tree.update(i, max_move)
    ans_array[i] = (ans_array[i+1] + ans_array[max_move + 1]) % mod

print(ans_array[0])
### BUGGY CODE ###

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

if(ans > 10**18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit(0)
ans = 1
for i in range(N):
    ans = ans * A[i]
    if(ans > 10**18):
        print(-1)
        exit(0)

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

#!/usr/bin/env python3

X, Y, A, B, C = list(map(int, input().split()))
p_list = list(map(int, input().split()))  # 10 ** 5
q_list = list(map(int, input().split()))
r_list = list(map(int, input().split()))

p_list = sorted(p_list, reverse=True)
q_list = sorted(q_list, reverse=True)
r_list = sorted(r_list, reverse=True)

total = 0
for _ in range(X):
    if r_list and p_list:
        r = r_list[0]
        p = p_list[0]

        if p >= r:
            total += p_list.pop(0)
        else:
            total += r_list.pop(0)
    elif r_list:
        total += r_list.pop()
    elif p_list:
        total += p_list.pop()
    else:
        break

for _ in range(Y):
    if r_list and q_list:
        r = r_list[0]
        q = q_list[0]

        if q >= r:
            total += q_list.pop(0)
        else:
            total += r_list.pop(0)
    elif r_list:
        total += r_list.pop(0)
    elif q_list:
        total += q_list.pop(0)
    else:
        break
ans = total
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

X, Y, A, B, C = list(map(int, input().split()))
p_list = list(map(int, input().split()))  # 10 ** 5
q_list = list(map(int, input().split()))
r_list = list(map(int, input().split()))

p_list = list(sorted(p_list, reverse=True))
q_list = list(sorted(q_list, reverse=True))
# r_list = sorted(r_list, reverse=True)

p_list = p_list[:X]
q_list = q_list[:Y]

all_list = p_list + q_list + r_list
all_list = list(sorted(all_list, reverse=True))
total = sum(all_list[: X + Y])


ans = total
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
for i in range(1,n+1):
  print(a.index(i)+1)
  

  


### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
num_array = [0]*n
for i in range(n):
    num_array[num_list[i]-1] = i+1
for i in range(n):
    print(num_array[i])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
C = []
ans = sum(A)


for i in range(M):
  b, c = map(int, input().split())
  C.extend([c]*b)

C.sort(reverse=True)
if M > N:
  C = C[:N] #Aの数を超える分は不要

if A[0] >= C[0]:
    print(ans)
    exit()

k = len(C)
for i in range(len(C)):  
  if C[i] < A[i]:
    k = i
    break
ans = sum(C[:k]) + sum(A[k:])
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

class unionfind:
	def __init__(self, n):
		self.parent = list(range(n))
	def find(self, i):
		if self.parent[i] != i: self.parent[i] = self.find(self.parent[i])
		return self.parent[i]
	def unite(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if i != j: self.parent[i] = j
	def issame(self, i, j):
		return self.find(i) == self.find(j)
	def groups(self):
		r = range(len(self.parent))
		return [[j for j in r if self.issame(j, i)] for i in r if i == self.parent[i]]
	@staticmethod
	def isconnected(l, u = None):
		nw, nh = len(l), len(l[0])
		rw, rh = range(nw), range(nh)
		if not u: u = unionfind(nw * nh)
		f = -1
		for i in rw:
			for j in rh:
				if not l[i][j]: continue
				if f < 0: f = i + j * nw
				if j > 0 and l[i][j] == l[i][j - 1]: u.unite(i + j * nw, i + j * nw - nw)
				if i > 0 and l[i][j] == l[i - 1][j]: u.unite(i + j * nw, i + j * nw - 1)
		return f >= 0 and all([u.issame(f, i + j * nw) for i in rw for j in rh if l[i][j]])
	@staticmethod
	def isconnectedlist(nw, nh, lst):
		l = [[False] * nw for j in range(nh)]
		for i, j in lst: l[i][j] = True
		return unionfind.isconnected(l)
 
def culc(x):
    return int(x * (x-1) //2)
 
N , M = map(int, input().split())
ans_lst = []
lst = []
for i in range(M):
    A , B = map( int , input().split())
    lst.append([A , B] )
cu = unionfind(N)
maxroute = culc(N)
for ls  in  reversed(lst):
    temp = maxroute
    for subg in cu.groups():
        temp -= culc(len(subg))
    ans_lst.append(temp)
    cu.unite(ls[0]-1 , ls[1]-1)
 
for y in reversed(ans_lst):
    print(y)

### FIXED CODE ###

#学習用
def root(x):
    # xが根であれば
    if x == p[x]:
        # xを返す
        return x
    # xが根でなければp[x]の根をp[x]に設定する
    p[x] = y = root(p[x])
    # p[x]の根を返却する
    return y
def unite(x, y):
    # xとyの根を取得する
    px = root(x); py = root(y)
    # xとyの根が同じならば
    if px == py:
        # 根が同じならば、0を返す
        return 0
    # yの根がxの根より大きければ、
    if px < py:
        # yの根の位置のp[]を、xの根にする
        p[py] = px
        # xの根の位置のサイズszを、yの根の位置のサイズだけ加算する
        sz[px] += sz[py]
    else:
    # yの根がxの根より小さければ
        # xの根の位置のp[]を、yの根を指すようにする
        p[px] = py
        sz[py] += sz[px]
    # 根が異なっていた＝結合した場合は、1を返却する
    return 1

N , M = map(int, input().split())
*p , = range(N)
sz = [1] * N
E = []
for i in range(M):
    a , b = map(int, input().split())
    E.append((a-1, b-1))

ans = [None] * M
E.reverse()
res = 0
ans[-1] = "%d\n" % (N*(N-1)//2)

for i , (a,b) in enumerate(E[:-1]):
    sa = sz[root(a)]; sb = sz[root(b)]
    if unite(a , b):
        sc = sz[root(a)]
        res += sc*(sc-1)//2 - sa*(sa-1)//2 - sb*(sb-1)//2
    ans[-2-i] = "%d\n" % (N*(N-1)//2 -res)
open(1, 'w').writelines(ans)
### BUGGY CODE ###

def prime_eratosthenes(n):
    prime_list = []
    num_list=[]
    for i in range(2, n+1):
        if i not in num_list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                num_list.append(j)
    return prime_list

ls = prime_eratosthenes(100000)
ls2 = [i+1 for i in range(100000)]
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    for j in range(l-1, r):
        if (ls2[j] in ls) and (ls2[j+1]//2 in ls):
            ans += 1
    print(ans)

### FIXED CODE ###

q = int(input())
    
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

ls = [0]

for i in range(1,100000):
    if is_prime(i) and is_prime((i+1)//2):
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
        
for i in range(q):
    l,r = map(int,input().split())
    if l == r:
        if is_prime(l) and is_prime((l+1)//2):
            print(1)
        else:
          print(ls[r]-ls[l-1])  
    else:
        print(ls[r]-ls[l-1])
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

dic = {}
for ai in a:
    if ai not in dic:
        dic[ai] = 0
    dic[ai] += 1

ans = 0

for ai in a:
    cnt = 0
    f = 1
    for i in range(1, int(ai**0.5)+1):
        if ai % i == 0:
            d = i
            if d in dic:
                cnt += dic[d]
            if d == ai:
                cnt -= 1
            if cnt > 0:
                f = 0
                break
            if i != ai // i:
                d = ai // i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break

    ans += f

print(ans)
    

            




### FIXED CODE ###

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

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

N = int(input())
S = list(input())
Q = int(input())
set_dic = {}

for i, s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

anslist = []

for _ in range(Q):
    query1, query2, query3 = input().split()
    if query1 == "1":
        i = int(query2)
        c = query3
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query2)
        r = int(query3)
        ansset = set()
        ans = 0
        for eachset in set_dic.values():
            for i in range(l, r + 1):
                if i in eachset:
                    ans += 1
                    break
        anslist.append(ans)

for i in anslist:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic:
            set_dic[s] = [i+1]
        else:
            bisect.insort_left(set_dic[s], i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            cap = S[i-1]
            if cap == c:
                continue
            set_dic[cap].remove(i)
            if c not in set_dic:
                set_dic[c] = [i]
            else:
                bisect.insort_left(set_dic[c], i)
            S[i-1] = c
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachlist in set_dic.values():
                li = bisect.bisect_left(eachlist, l)
                ri = bisect.bisect_right(eachlist, r)
                if li != ri:
                    ans += 1
            anslist.append(ans)

    for i in anslist:
        print(i)

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

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

i = 0
while i < len(A):
    a = A[i]
    if i < len(A)-1:
        if A[i+1] == a:
            while a in A:
                A.remove(a)
            continue
    j = i + 1
    while j < len(A):
        if A[j] % a == 0:
            A.pop(j)
        else:
            j += 1
    i += 1
print(len(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

for i in range(len(A)-1):
    a = A[i]
    if B[a] == True:
        if A[i] == A[i+1]:
            B[a] = False
        for x in range(2*a, len(B), a):
            B[x] = False

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

import sys
import math
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
p = [0]*(ma + 1)

for i in a:
  p[i] += 1

pairwise = True
for i in range(2, ma+1):
  cnt = 0
  for j in range(i, ma+1, i):
    cnt += p[j]
  if cnt > 1:
    pairwise = False
    
if pairwise:
  print("pairwise coprime")
else:
  temp = a[0]
  for i in a:
    temp = math.gcd(temp, i)
  if temp == 1:
    print("setwise coprime")
  else:
    print("not coprime")

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
p = [0]*(ma + 1)

for i in a:
  p[i] += 1

pairwise = True
for i in range(2, ma+1):
  cnt = 0
  for j in range(i, ma+1, i):
    cnt += p[j]
  if cnt > 1:
    pairwise = False
    break
    
if pairwise:
  print("pairwise coprime")
else:
  temp = a[0]
  for i in a:
    temp = math.gcd(temp, i)
  if temp == 1:
    print("setwise coprime")
  else:
    print("not coprime")
### BUGGY CODE ###

from collections import deque
N,H=map(int,input().split())
a=deque([]);b=deque([])
for _ in range(N):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)
bb=deque([])
ma=max(a)
bc=0
for _ in range(N):
    bi=max(b)
    b.remove(bi)
    if bi>ma:
        bb.append(bi)
        bc+=bi
    if bc>=H:
        print(len(bb))
        exit()
ans=(H-sum(bb))//ma+len(bb)
if (H-sum(bb))%ma==0:
    print(ans)
else:
    print(ans+1)

### FIXED CODE ###

N,H=map(int,input().split())
S=[[int(x) for x in input().split()] for _ in range(N)]
A,B=zip(*S)
A=max(A)
B=[b for b in B if b>A]
B.sort(reverse=True)
ans=0
cnt=0
for b in B:
    if H<=0:
        break
    cnt+=1
    H-=b
if H>0:
    cnt+=(H-1)//A+1
print(cnt)
### BUGGY CODE ###

n=int(input())
S=list(map(int,input().split()))
set_S=list(set(S))
ans_stock={}
number={}
for i in set_S:
  number[i] = S.count(i)
comb = 0
for i in set_S:
  comb += number[i]*(number[i]-1)/2

for i in S:
  if i in list(ans_stock.keys()):
    print(ans_stock[i])
  else:
    ans = int(comb -  number[i]*(number[i]-1)/2 +  (number[i]-1)*(number[i]-2)/2)
    print(ans)
    ans_stock[i]=ans


### FIXED CODE ###

from collections import Counter
n=int(input())
S=list(map(int,input().split()))
number=Counter(S)
comb=0
stock={}
for i in list(number.values()):
  comb += i*(i-1)/2
for i in S:
  ans = int(comb - number[i]*(number[i]-1)/2 + (number[i]-1)*(number[i]-2)/2)
  print(ans)
### BUGGY CODE ###

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

S = []
for i in s:
    S.append(i)

ans = 100100100100
for i in range(n):
    cost = S[0:i].count('W') + s[i+1:n].count('E')
    ans = min(ans, cost)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
S = []
for i in s:
    S.append(i)

w = [0,]
for i in range(1, n):
    if S[i-1] == 'W':
        w.append(w[i-1] + 1)
    else:
        w.append(w[i-1])

e = [0 for _ in range(n)]
for i in range(n-2, -1, -1):
    if S[i+1] == 'E':
        e[i] = e[i+1] + 1
    else:
        e[i] = e[i+1]

ans = 100100100100
for i in range(n):
    cost = w[i] + e[i]
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
nox_S = S.replace('x','')
if nox_S == nox_S[::-1]:
  si, ei = 0, N-1
  ans = 0
  while si <= ei:
    cnt1 = 0
    for i in range(si,N):
      if S[i] == 'x':cnt1 += 1
      else:
        si = i+1
        break
    
    cnt2 = 0
    for i in range(ei,-1,-1):
      if S[i] == 'x':cnt2 += 1
      else:
        ei = i-1
        break
    ans += abs(cnt1-cnt2)
  print(ans)
else:
  print(-1)
  


### FIXED CODE ###

S = input()
N = len(S)
si, ei = 0, N-1
cnt = 0
while si<ei:
  if S[si] != S[ei]:
    if S[si] == 'x':
      si += 1
      cnt+=1
    elif S[ei] == 'x':
      ei -= 1
      cnt+=1
    else:
      print(-1)
      exit()
  else:
    si += 1
    ei -= 1
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
if len(a) == 1:
    ans = a[0] * (0.5) ** m
    print(int(ans))
    exit()
while m > 0:
    a.sort(reverse=True)
    #print(m)
    plus = a[0] - a[0]//2
    ngtv = a[1] - a[1]//2
    if plus > ngtv:
        m -= 1
        a[0] = a[0]//2
    else:
        m -= 1
        a[1] = a[1]//2
    #print(a)
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = [ -i for i in a ]
heapq.heapify(a)

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

n = int(input())
s = list(input())
c = 0

for i in range(1000) :
    num_1 = i // 100
    num_2 = (i - num_1*100) // 10
    num_3 = (i - num_1*100 - num_2*10) % 100
    if str(num_1) not in s :
        continue
    if str(num_2) not in s :
        continue
    if str(num_3) not in s :
        continue
    for j in range(n-2) :
        if int(s[j]) == num_1 :
            for k in range(j+1,n-1) :
                if int(s[k]) == num_2 :
                    for l in range(k+1,n) :
                        if int(s[l]) == num_3 :
                            c += 1
                            break
                    break
            break

print(c)


### FIXED CODE ###

n = int(input())
s = list(input())
c = 0

for i in range(1000) :
    num_1 = i // 100
    num_2 = (i - num_1*100) // 10
    num_3 = (i - num_1*100 - num_2*10) % 100
    if str(num_1) not in s :
        continue
    if str(num_2) not in s :
        continue
    if str(num_3) not in s :
        continue
    for j in range(n-2) :
        if int(s[j]) == num_1 :
            for k in range(j+1,n-1) :
                if int(s[k]) == num_2 :
                    for l in range(k+1,n) :
                        if int(s[l]) == num_3 :
                            c += 1
                            break
                    break
            break

print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

m = 10**5
d = set(a)
s = sum(a)
l = [0]*m
for i in d:
    l[i-1] = a.count(i)
for b, c in bc:
    s = s + l[b-1]*(c-b)
    l[c-1] += l[b-1]
    l[b-1] = 0
    print(s)

### FIXED CODE ###

from collections import Counter

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

counter = Counter(a)
sum_res = sum(a)  # はじめの合計、名前がsumだとsum関数とかぶってよくないので

# q回操作します。ループ変数は使わないので_とします（Pythonの慣習）
for _ in range(q):
    before, after = map(int, input().split())

    # 合計を変更します
    sum_res -= before * counter[before]
    sum_res += after * counter[before]

    # 個数を変更します
    counter[after] += counter[before]
    counter[before] = 0

    print(sum_res)
### BUGGY CODE ###

s = input()
sl = list(map(int, list(s)))
n = len(s)
slc = [0] * (n+1)
for i in range(n):
    slc[i+1] += sl[i]+slc[i]
ans = 0
for i in range(n-4):
    for j in range(i+4, n+1):
        if (slc[j]-slc[i])%3 ==0 and int(s[i:j])%2019==0:
            ans+=1
print(ans)

### FIXED CODE ###

s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = {}
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
[dp.update({i: dp[i-1] + dp[i-2]}) if i not in A else dp.update({i:0}) for i in range(2, N+1)]
#  for i in range(2, N+1):
#      print(i)
#      # i段目までの通りを計算する
#      if i in A:
#          # i段目が障害のときは0になっているので飛ばす
#          dp[i] = 0
#          continue
    
#      dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in a:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

print(dp[-1])