AtCoder Beginner Contest 129 - Typical Stairs

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.
However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.
How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 0 \leq M \leq N-1
 - 1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1
a_2
 .
 .
 .
a_M

-----Output-----
Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

-----Sample Input-----
6 1
3

-----Sample Output-----
4

There are four ways to climb up the stairs, as follows:
 - 0 \to 1 \to 2 \to 4 \to 5 \to 6
 - 0 \to 1 \to 2 \to 4 \to 6
 - 0 \to 2 \to 4 \to 5 \to 6
 - 0 \to 2 \to 4 \to 6

Difficulty: EASY

Starter code:

Solutions:
(n, m) = map(int, input().split())
dp = [0] * (n + 2)
dp[0] = 1
for i in range(m):
	dp[int(input())] = -1
for i in range(n):
	if dp[i] >= 0:
		if dp[i + 1] >= 0:
			dp[i + 1] += dp[i]
		if dp[i + 2] >= 0:
			dp[i + 2] += dp[i]
print(dp[n] % 1000000007)


(n, m) = map(int, input().split())
a = [False] * (n + 1)
for i in range(m):
	A = int(input())
	a[A] = True
mod = 10 ** 9 + 7
dp = [0] * (n + 1)
if not a[1]:
	dp[1] = 1
if n > 1:
	if not a[2]:
		dp[2] = dp[1] + 1
for i in range(3, n + 1):
	if not a[i - 2]:
		dp[i] += dp[i - 2]
		dp[i] %= mod
	if not a[i - 1]:
		dp[i] += dp[i - 1]
		dp[i] %= mod
	if a[i]:
		dp[i] = 0
print(dp[n] % mod)


(n, m) = map(int, input().split())
w = [1 for _ in range(n + 1)]
for _ in range(m):
	w[int(input())] = 0
for i in range(2, n + 1):
	if w[i] != 0:
		w[i] = w[i - 2] + w[i - 1]
print(w[-1] % 1000000007)


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
A = [1] * (n + 1)
for i in range(m):
	A[int(input())] = 0
B = [1] * (n + 1)
if A[1] == 0:
	B[1] = 0
for i in range(2, n + 1):
	B[i] = A[i] * (B[i - 1] + B[i - 2]) % mod
print(B[n])


import sys
(n, m) = map(int, input().split())
a = list(map(int, sys.stdin))
a.append(0)
prev = 0
cur = 1
m = 0
for i in range(1, n + 1):
	if a[m] == i:
		(prev, cur) = (cur, 0)
		m += 1
	else:
		(prev, cur) = (cur, (cur + prev) % 1000000007)
print(cur)


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


(N, M) = map(int, input().split())
A = set([int(input()) for i in range(M)])
B = [0] * (N + 1)
B[0] = 1
for i in range(1, N + 1):
	B[i] = B[i - 1] + B[i - 2]
	if i in A:
		B[i] = 0
print(B[N] % 1000000007)


(N, M) = map(int, input().split())
dp = [1] * (N + 1)
for i in range(M):
	dp[int(input())] = 0
for i in range(2, N + 1):
	if dp[i] != 0:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] % 1000000007)


import sys
(N, M) = map(int, input().split())
S = set(map(int, sys.stdin))
(a, b) = (0, 1)
for i in range(1, N + 1):
	if i in S:
		(a, b) = (b, 0)
	else:
		(a, b) = (b, a + b)
print(b % (10 ** 9 + 7))


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
a = set([int(input()) for i in range(m)])
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	if i in a:
		dp[i] = 0
print(dp[n])


(n, _, *l) = map(int, open(0).read().split())
l = set(l)
s = i = 0
t = 1
while i < n:
	i += 1
	(s, t) = (t, (s + t) % (10 ** 9 + 7) * (not {i} & l))
print(t)


(n, m, *a) = map(int, open(0).read().split())
b = [1] * (n + 1)
for i in a:
	b[i] = 0
for i in range(2, n + 1):
	b[i] = (b[i - 1] + b[i - 2]) % 1000000007 * b[i]
print(b[-1])


(n, m) = list(map(int, input().split()))
L = [False] * (n + 1)
for _ in range(m):
	a = int(input())
	L[a] = True
dp = [0] * (n + 1)
dp[0] = 1
MOD = 1000000007
for i in range(1, n + 1):
	if L[i]:
		continue
	if i == 1:
		dp[1] = 1
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % MOD)


import sys
f = sys.stdin.readline
(n, m) = map(int, f().split())
l = set((int(f()) - 1 for _ in range(m)))
(s, t) = (0, 1)
for i in range(n):
	(s, t) = (t, (s + t) % (10 ** 9 + 7) * (1 - (i in l)))
print(t)


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
d = [1] * (n + 1)
for i in range(m):
	d[a[i]] = 0
for i in range(2, n + 1):
	if d[i] != 0:
		d[i] = d[i - 1] + d[i - 2]
print(d[n] % (10 ** 9 + 7))


MOD = 1000000007
(N, M) = list(map(int, input().split()))
cnt = [0 for _ in range(N + 1)]
cnt[0] = 1
for _ in range(M):
	a = int(input())
	cnt[a] = -1
for i in range(1, N + 1):
	if cnt[i] == -1:
		cnt[i] = 0
		continue
	if i == 1:
		cnt[i] = cnt[i - 1]
	else:
		cnt[i] = (cnt[i - 1] + cnt[i - 2]) % MOD
print(cnt[N])


(N, M) = map(int, input().split())
res = 0
flag = True
INF = 100000000000
stepList = [INF] * (N + 1)
stepList[0] = 1
stepList[1] = 1

def stepF(K):
	if K == 0:
		return stepList[0]
	else:
		for i in range(1, K + 1):
			if i == 1:
				pass
			elif stepList[i] == INF:
				stepList[i] = stepList[i - 2] + stepList[i - 1]
		return stepList[K]
if M == 0:
	res = stepF(N)
else:
	List = []
	for i in range(M):
		List.append(int(input()))
	for i in range(M):
		if i == 0:
			res = stepF(List[i] - 1)
		else:
			if List[i] - List[i - 1] == 1:
				flag = False
				break
			res = res * stepF(List[i] - List[i - 1] - 2)
	res = res * stepF(N - List[M - 1] - 1)
if flag:
	print(res % 1000000007)
else:
	print(0)


(N, M) = map(int, input().split())
issafe = [1] * (N + 1)
for i in range(M):
	a = int(input())
	issafe[a] = 0
dp = [0] * (N + 1)
dp[0] = 1
if issafe[1]:
	dp[1] = 1
for i in range(2, N + 1):
	if issafe[i - 1]:
		dp[i] += dp[i - 1]
	if issafe[i - 2]:
		dp[i] += dp[i - 2]
	dp[i] %= 10 ** 9 + 7
print(dp[N])


(n, m) = list(map(int, input().split()))
a = list((int(input()) for _ in range(m)))
MOD = 10 ** 9 + 7
is_broken = [0] * (n + 1)
dp = [0] * (n + 1)
dp[0] = 1
for x in a:
	is_broken[x] = 1
for i in range(n):
	for j in range(i + 1, min(n, i + 2) + 1):
		if not is_broken[j]:
			dp[j] += dp[i]
			dp[j] %= MOD
print(dp[n])


(n, m) = map(int, input().split())
a = set()
for _ in range(m):
	a.add(int(input()))
DP = [None] * 100001
DP[0] = 1
if 1 in a:
	DP[1] = 0
else:
	DP[1] = 1

def stairs(n):
	for i in range(2, n + 1):
		DP[i] = DP[i - 1] + DP[i - 2]
		if i in a:
			DP[i] = 0
		DP[i] %= 10 ** 9 + 7
	return DP[n]
print(stairs(n))


(N, M) = (int(a) for a in input().split())
stair = [1] * (N + 1)
for i in range(1, M + 1):
	a = int(input())
	stair[a] = 0
for i in range(2, N + 1):
	stair[i] *= (stair[i - 1] + stair[i - 2]) % (10 ** 9 + 7)
print(stair[N])


(n, m) = map(int, input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	if i in A:
		dp[i] = 0
print(dp[n])


(n, m) = map(int, input().split())
a = set((int(input()) for _ in range(m)))
dp = [0] * (n + 2)
dp[0] = 1
for i in range(n):
	if i in a:
		continue
	dp[i + 1] += dp[i]
	dp[i + 2] += dp[i]
print(dp[n] % 1000000007)


(N, M) = map(int, input().split())
A = [int(input()) for _ in range(M)]
A = set(A)
MOD = 1000000007
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
	if i in A:
		continue
	dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
print(dp[N])


(N, M) = list(map(int, input().split()))
a_s = set([int(input()) for _ in range(M)])
mod = 10 ** 9 + 7
ans = [0] * (N + 1)
ans[0] = 1
for i in range(1, N + 1):
	if i - 1 not in a_s:
		ans[i] = ans[i - 1]
	if i > 1:
		if i - 2 not in a_s:
			ans[i] += ans[i - 2]
	if i - 1 in a_s and i - 2 in a_s:
		break
	else:
		ans[i] = ans[i] % mod
print(ans[-1])


(n, m) = map(int, input().split())
p = [True for _ in range(n + 1)]
p[0] = 1
p[1] = 1
for _ in range(m):
	a = int(input())
	p[a] = 0
for i in range(2, n + 1):
	if p[i]:
		p[i] = p[i - 1] + p[i - 2]
print(p[n] % (10 ** 9 + 7))


(N, M) = map(int, input().split())
a = [int(input()) for _ in range(M)] + [10 ** 6]
A = [0] * (N + 2)
A[0:2] = [0, 1]
j = 0
for i in range(N):
	if i + 1 != a[j]:
		A[i + 2] = (A[i] + A[i + 1]) % (10 ** 9 + 7)
	else:
		j += 1
print(A[N + 1])


(N, M) = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF
print(dp[N])


(N, M) = map(int, input().split())
stairs = [1] * (N + 1)
for m in range(M):
	a = int(input())
	stairs[a] = 0
for n in range(2, N + 1):
	stairs[n] = (stairs[n - 1] + stairs[n - 2]) * stairs[n]
print(stairs[N] % 1000000007)


import sys
(N, M) = list(map(int, input().split()))
a = [False] * (N + 1)
for i in range(M):
	a[int(input())] = True
b = [0] * (N + 1)
if N < 2:
	print(1)
	return
b[-1] = 1
for i in reversed(list(range(0, N))):
	if a[i]:
		b[i] = 0
		continue
	if i == N - 1:
		b[i] = b[i + 1]
	else:
		b[i] = (b[i + 1] + b[i + 2]) % (10 ** 9 + 7)
print(b[0])


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
dp = [0] * (N + 1)
for _ in range(M):
	dp[int(input())] = -1
dp[0] = 1
for i in range(N + 1):
	if dp[i] == -1:
		continue
	if i + 1 <= N and dp[i + 1] != -1:
		dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
	if i + 2 <= N and dp[i + 2] != -1:
		dp[i + 2] = (dp[i + 2] + dp[i]) % MOD
print(dp[N])


(N, M) = map(int, input().split())
a = [int(input()) for i in range(M)]
dp = [1] * (N + 1)
mod = 10 ** 9 + 7
for A in a:
	dp[A] = 0
for i in range(N + 1):
	if i >= 2 and dp[i]:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[N])


(N, M) = map(int, input().split())
a = [0] * (N + 1)
INF = 10 ** 100
NUM = 7 + 10 ** 9
dp = [0] * (N + 1)
for _ in range(M):
	tmp = int(input())
	a[tmp] = 1
dp[0] = 1
if not a[1]:
	dp[1] += dp[0]
for i in range(2, N + 1):
	if a[i]:
		continue
	dp[i] += dp[i - 1] + dp[i - 2]
	dp[i] %= NUM
print(dp[N])


(N, M) = map(int, input().split())
A = set([int(input()) for _ in range(M)])
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
	if i in A:
		dp[i] = 0
print(dp[N])


M = 10 ** 9 + 7
import sys
f = sys.stdin.readline
(n, m) = map(int, f().split())
(s, t) = (0, 1)
u = 0 if m < 1 else int(f())
for i in range(n):
	if i == u - 1:
		(s, t) = (t, 0)
		try:
			u = int(f())
		except:
			pass
	else:
		(s, t) = (t, (s + t) % M)
print(t)


(n, m) = map(int, input().split())
a = set([int(input()) for _ in range(m)])
(p, q) = (0, 1)
for i in range(1, n + 1):
	(p, q) = (q, (p + q) % (10 ** 9 + 7) * (not i in a))
print(q)


(N, M) = map(int, input().split())
st = [1] * (N + 1)
for i in range(M):
	x = int(input())
	st[x] = 0
for i in range(2, N + 1):
	if st[i]:
		st[i] = st[i - 1] + st[i - 2]
print(st[-1] % 1000000007)


(n, m) = map(int, input().split())
D = [1] * (n + 1)
for _ in range(m):
	D[int(input())] = 0
for i in range(n + 1):
	if D[i] == 0 or i < 2:
		continue
	D[i] = (D[i - 1] + D[i - 2]) % 1000000007
print(D[i])


def main():
	(N, M) = [int(i) for i in input().split()]
	pos = 0
	ans = 1
	fib = [1 for _ in range(N + 1)]
	for i in range(2, N + 1):
		fib[i] = fib[i - 1] + fib[i - 2]
	for _ in range(M):
		a = int(input())
		if a == pos:
			ans = 0
			pos = N
			break
		elif a == pos + 1:
			pos = a + 1
		else:
			ans *= fib[a - 1 - pos]
			pos = a + 1
	if pos + 1 < N:
		ans *= fib[N - pos]
	print(ans % 1000000007)

def __starting_point():
	main()
__starting_point()


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

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

def MF():
	return map(float, input().split())

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

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	(N, M) = MI()
	L = set([I() for i in range(M)])
	mod = 1000000007
	D = [0] * (N + 2)
	D[1] = 1
	for i in range(1, N + 1):
		if not i in L:
			D[i + 1] = (D[i] + D[i - 1]) % mod
	print(D[N + 1] % mod)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
Stlist = [1] * N
for i in range(M):
	breakstair = int(input())
	Stlist[breakstair - 1] = 0
Comb = [1, 2]
if N == 1:
	Comb = Stlist
else:
	if Stlist[0] == 0:
		Comb[0] = 0
		Comb[1] = 1
	if Stlist[1] == 0:
		Comb[1] = 0
	for i in range(2, N):
		Comb.append((Comb[i - 1] + Comb[i - 2]) % (10 ** 9 + 7))
		if Stlist[i] == 0:
			Comb[i] = 0
print(Comb[-1])


(n, m) = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]
dp = [0] * n
for i in a:
	dp[i - 1] = -1
if n == 1:
	if dp[0] == 0:
		print(1)
		return
	elif dp[0] == -1:
		print(0)
		return
if dp[1] >= 0 and dp[0] >= 0:
	dp[0] = 1
	dp[1] = 2
elif dp[1] == -1 and dp[0] >= 0:
	dp[0] = 1
elif dp[1] >= 0 and dp[0] == -1:
	dp[1] = 1
else:
	print(0)
	return
for j in range(2, n):
	if dp[j] >= 0:
		if dp[j - 1] >= 0 and dp[j - 2] >= 0:
			dp[j] = dp[j - 1] + dp[j - 2]
		elif dp[j - 1] == -1 and dp[j - 2] >= 0:
			dp[j] = dp[j - 2]
		elif dp[j - 1] >= 0 and dp[j - 2] == -1:
			dp[j] = dp[j - 1]
		else:
			print(0)
			return
print(dp[n - 1] % (10 ** 9 + 7))


key = 10 ** 9 + 7
(N, M) = map(int, input().split())
A = [int(input()) for _ in range(M)]
A.sort()
A += [-1]

def solve():
	steps = list()
	count = 0
	index = 0
	for i in range(N + 1):
		if i == A[index]:
			if count == 0:
				return 0
			else:
				steps.append(count)
				count = 0
				if index < M:
					index += 1
		else:
			count += 1
	else:
		steps.append(count)
		count = 0
	smax = max(steps)
	fibs = [0] * smax
	for i in range(smax):
		if i == 0 or i == 1:
			fibs[i] = 1
		else:
			fibs[i] = fibs[i - 1] + fibs[i - 2]
	else:
		ans = 1
		for s in steps:
			ans *= fibs[s - 1]
			ans %= key
	return ans
ans = solve()
print(ans)


(n, m) = map(int, input().split())
A = {int(input()) for _ in range(m)}
dp = [1] + [0] * (n + 1)
for i in range(n):
	if i in A:
		continue
	dp[i + 1] += dp[i]
	dp[i + 2] += dp[i]
print(dp[n] % (10 ** 9 + 7))


(G, N) = [int(_) for _ in input().split(' ')]
ret = ()
T = [-1] * (G + 1)
T[0] = 1
T[1] = 1
for i in range(N):
	t = int(input())
	T[t] = 0
for i in range(2, G + 1):
	if T[i] == -1:
		T[i] = (T[i - 1] + T[i - 2]) % 1000000007
print(T[G])


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
a = set(a)
d = [1] + [1] * n
for i in range(1, n):
	if i in a:
		d[i] = 0
		d[i + 1] = d[i - 1]
	else:
		d[i + 1] = d[i] + d[i - 1]
print(d[n] % 1000000007)


import sys
input = lambda : sys.stdin.readline().strip()
(n, m) = [int(x) for x in input().split()]
can = [True for i in range(n + 1)]
for i in range(m):
	ai = int(input())
	can[ai] = False
C = [0 for i in range(n + 1)]
for i in range(n + 1):
	if i == 0:
		C[i] = 1
	else:
		C[i] = sum((C[j] if j >= 0 and can[j] else 0 for j in (i - 1, i - 2))) % (10 ** 9 + 7)
print(C[n])


(n, m) = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
dp = [1] + [1] * 100010
for i in a:
	dp[i] = 0
for i in range(2, n + 1):
	if dp[i]:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % 1000000007)


(N, M) = map(int, input().split())
A = [True] * N
for _ in range(M):
	a = int(input())
	A[a - 1] = False
waru = 10 ** 9 + 7
dp = [0] * (N + 1)
(dp[0], dp[1]) = (1, 1)
if not A[0]:
	dp[1] = 0
for i in range(2, N + 1):
	if not A[i - 1]:
		dp[i] = 0
	else:
		dp[i] = (dp[i - 1] + dp[i - 2]) % waru
print(dp[-1])


(n, m) = map(int, input().split())
l = set([int(input()) for i in range(m)])
c = [0] * (n + 1)
c[0] = 1
c[1] = 1
if 1 in l:
	c[1] = 0
for i in range(2, n + 1):
	if i in l:
		c[i] = 0
	else:
		c[i] = (c[i - 1] + c[i - 2]) % 1000000007
print(c[n])


(n, m) = map(int, input().split())
a = set([int(input()) for _ in range(m)])
step = [0] * (n + 1)
step[0] = 1
if 1 not in a:
	step[1] = 1
else:
	step[1] = 0
for i in range(2, n + 1):
	if i in a:
		continue
	step[i] = (step[i - 1] + step[i - 2]) % 1000000007
print(step[-1])


(n, m) = map(int, input().split())
a = [0] * (m + 1)
mod = 1000000007
for i in range(m):
	a[i] = int(input())
s = [1, 1]
j = 0
for i in range(2, n + 1):
	if i - 1 == a[j]:
		s[i - 1] = 0
		j += 1
	s.append(s[i - 1] + s[i - 2])
print(s[n] % mod)


(n, m) = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 10 ** 9 + 7
c = [0] * (n + 1)
for i in a:
	c[i] = -1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if m > 0 and a[0] == 1 else 1
for i in range(2, n + 1):
	if c[i] == -1:
		continue
	dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[-1])


p = 10 ** 9 + 7
(N, M) = map(int, input().split())
status = [1] * (N + 1)
for i in range(M):
	status[int(input())] = 0
dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
	if i + 1 <= N and status[i + 1]:
		dp[i + 1] += dp[i] % p
	if i + 2 <= N and status[i + 2]:
		dp[i + 2] += dp[i] % p
print(dp[N] % p)


(N, M) = map(int, input().split())
Aset = set()
for _ in range(M):
	Aset.add(int(input()))
mod = 10 ** 9 + 7
num = [0] * (N + 1)
for i in range(2):
	if not i in Aset:
		num[i] += 1
for i in range(2, N + 1):
	if i in Aset:
		num[i] = 0
	else:
		num[i] += num[i - 1] + num[i - 2]
		num[i] %= mod
print(num[-1] % mod)


(n, m) = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
	if i in a:
		dp[i] = 0
print(dp[n])


(n, m) = map(int, input().split())
a = set([int(input()) for _ in range(m)])
nums = [0] * (n + 1)
nums[0] = 1
if 1 not in a:
	nums[1] = 1
for i in range(2, n + 1):
	if i not in a:
		nums[i] = nums[i - 1] + nums[i - 2]
print(nums[n] % (10 ** 9 + 7))


(n, m) = map(int, input().split())
a_list = [int(input()) for _ in range(m)]
dp = [1] * (n + 1)
for a in a_list:
	dp[a] = 0
for i in range(2, n + 1):
	if dp[i] != 0:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % (10 ** 9 + 7))


import sys
(n, m) = map(int, input().split())
c = set(map(int, sys.stdin))
d = [0] * (n + 1)
d[0] = 1
d[1] = 1 if 1 not in c else 0
for j in range(2, n + 1):
	if j in c:
		pass
	else:
		d[j] = (d[j - 1] + d[j - 2]) % 1000000007
print(d[n])


(n, m) = map(int, input().split())
mod = pow(10, 9) + 7
dp = [0] * (n + 5)
for _ in range(m):
	a = int(input())
	dp[a] = -1
dp[0] = 1
for i in range(n):
	if not dp[i] == -1:
		dp[i] %= mod
	else:
		continue
	if not dp[i + 1] == -1:
		dp[i + 1] += dp[i]
	if not dp[i + 2] == -1:
		dp[i + 2] += dp[i]
ans = dp[n] % mod
print(ans)


import numpy as np
(N, M) = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10 ** 9 + 7
dp = np.zeros(N + 1)
dp[0] = 1
if 1 not in A:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in A:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= mod
print(int(dp[N]))


MOD = 10 ** 9 + 7
INT = lambda : int(input())
INTM = lambda : map(int, input().split())
STRM = lambda : map(str, input().split())
STR = lambda : str(input())
LIST = lambda : list(map(int, input().split()))
LISTS = lambda : list(map(str, input().split()))

def do():
	(n, m) = INTM()
	b_sts = [False] * n
	for i in range(m):
		b = INT()
		b -= 1
		b_sts[b] = True
	step = [0] * (n + 2)
	step[1] = 1
	for i in range(n):
		if b_sts[i]:
			continue
		else:
			step[i + 2] = (step[i + 1] + step[i]) % MOD
	print(step[-1] % MOD)

def __starting_point():
	do()
__starting_point()


(n, m) = map(int, input().split())
oks = [True] * (n + 1)
for _ in range(m):
	a = int(input())
	oks[a] = False
mod = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
if oks[1]:
	dp[1] = 1
for i in range(2, n + 1):
	if oks[i]:
		dp[i] = dp[i - 1] + dp[i - 2]
		dp[i] %= mod
print(dp[-1])


def main3():
	(N, M) = map(int, input().split())
	ng_step = set([int(input()) for _ in range(M)])
	dp = [0 for i in range(N + 1)]
	dp[0] = 1
	if 1 in ng_step:
		dp[1] = 0
	else:
		dp[1] = 1
	for i in range(2, N + 1):
		if i in ng_step:
			dp[i] = 0
		else:
			dp[i] = dp[i - 1] + dp[i - 2]
	print(dp[N] % (10 ** 9 + 7))

def __starting_point():
	main3()
__starting_point()


M = 10 ** 9 + 7
f = input
(n, m) = map(int, f().split())
(s, t) = (0, 1)
u = 0 if m < 1 else int(f())
for i in range(n):
	if i == u - 1:
		(s, t) = (t, 0)
		try:
			u = int(f())
		except:
			pass
	else:
		(s, t) = (t, (s + t) % M)
print(t)


p = 1000000007
(n, m) = map(int, input().split())
u = [0] * (n + 1)
F = [0] * (n + 1)
for i in range(m):
	x = int(input())
	u[x] = 1
F[0] = 1
for i in range(1, n + 1):
	F[i] = (F[i - 1] + F[i - 2]) % p
	if u[i] == 1:
		F[i] = 0
print(F[n])


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
u = [0] * (n + 1)
F = [0] * (n + 1)
for i in range(m):
	x = int(input())
	u[x] = 1
F[0] = 1
for i in range(1, n + 1):
	F[i] = F[i - 1] + F[i - 2]
	if u[i] == 1:
		F[i] = 0
print(F[n] % mod)


(n, m) = map(int, input().split())
D = [1] * (n + 1)
for _ in range(m):
	D[int(input())] = 0
for i in range(n + 1):
	if i > 1:
		D[i] = (D[i - 1] + D[i - 2]) % (10 ** 9 + 7) * D[i]
print(D[i])


(n, m) = map(int, input().split())
a = set([int(input()) for i in range(m)])
mod = 1000000007
dp = [1, 1]
if 1 in a:
	dp[1] = 0
for i in range(2, n + 1):
	if i in a:
		dp.append(0)
	else:
		dp.append((dp[-1] + dp[-2]) % mod)
print(dp[-1] % mod)


(n, m) = list(map(int, input().split()))
broken = [False] * (n + 1)
for _ in range(m):
	broken[int(input())] = True
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7
for i in range(2, n + 1):
	if not broken[i - 1]:
		dp[i] += dp[i - 1]
	if not broken[i - 2]:
		dp[i] += dp[i - 2]
	dp[i] %= MOD
print(dp[n])


(n, m) = map(int, input().split())
a = set([int(input()) for _ in range(m)])
mod = 10 ** 9 + 7
fl = [0] * (n + 1)
fl[0] = 1
for i in range(1, n + 1):
	if i not in a:
		fl[i] = (fl[i - 1] + fl[i - 2]) % mod
	else:
		fl[i] = 0
print(fl[-1])


(n, m) = map(int, input().split())
x = set([int(input()) for _ in range(m)])
f = [0] * (n + 1)
f[0] = 1
for i in range(1, n + 1):
	f[i] = (f[i - 1] + f[i - 2]) % (10 ** 9 + 7)
	if i in x:
		f[i] = 0
print(f[n] % (10 ** 9 + 7))


(N, M) = map(int, input().split())
A = [int(input()) for n in range(M)]
S = [1] * (N + 1)
for a in A:
	S[a] = 0
for i in range(2, N + 1):
	S[i] = (S[i - 1] + S[i - 2]) % 1000000007 * S[i]
print(S[-1])


(n, m) = map(int, input().split())
a = [int(input()) for _ in range(m)]
b = [1 for i in range(n + 1)]
for i in a:
	b[i] = 0
for i in range(2, n + 1):
	cnt = b[i - 1] + b[i - 2]
	if b[i] != 0:
		b[i] = cnt
print(b[-1] % 1000000007)


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
mod = 10 ** 9 + 7
ans = 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= mod
if m == 0:
	ans = dp[n]
else:
	begin = 0
	end = a[0] - 1
	for i in range(m):
		end = a[i] - 1
		ans *= dp[end - begin]
		if i + 1 < m and a[i + 1] == a[i] + 1:
			ans = 0
			break
		else:
			begin = end + 2
	ans *= dp[n - a[m - 1] - 1]
print(ans % mod)


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


(n, m, *a) = map(int, open(0).read().split())
dp = [0] * (n + 1)
b = [1] * (n + 1)
for i in a:
	b[i] = 0
dp[0] = 1
if b[1]:
	dp[1] = 1
for i in range(2, n + 1):
	if b[i]:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] % (10 ** 9 + 7))


tmp = list(map(int, input().split()))
n = tmp[0]
m = tmp[1]
s = [1] * (n + 1)
for i in range(m):
	m = int(input())
	s[m] = 0
for i in range(2, n + 1):
	if s[i] != 0:
		s[i] = s[i - 1] + s[i - 2]
print(s[n] % 1000000007)


(N, M, *A) = list(map(int, open(0).read().split()))
Aset = set(A)
mod = 10 ** 9 + 7
num = [0] * (N + 1)
for i in range(2):
	if not i in Aset:
		num[i] += 1
for i in range(2, N + 1):
	if i in Aset:
		num[i] = 0
	else:
		num[i] += num[i - 1] + num[i - 2]
		num[i] %= mod
print(num[-1] % mod)


(n, m) = list(map(int, input().split()))
a = set(list((int(input()) for _ in range(m))))
mod = 1000000007
memo = [0] * (n + 1)
memo[0] = 1
for i in range(1, n + 1):
	memo[i] = memo[i - 1] + memo[i - 2]
	if i in a:
		memo[i] = 0
print(memo[-1] % mod)


(n, m) = map(int, input().split())
a_l = [int(input()) for _ in range(m)]
dp = [1] * (n + 1)
dp[0] = 1
if 1 not in a_l:
	dp[1] = 1
else:
	dp[1] = 0
if n > 1:
	for i in a_l:
		dp[i] = 0
	if 2 not in a_l:
		dp[2] = dp[0] + dp[1]
	else:
		dp[2] = 0
	for i in range(2, n + 1):
		if dp[i] != 0:
			dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[-1])


def main():
	(N, M) = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	a = [0] * (N + 1)
	a[0] = 1
	banned = [False] * (N + 1)
	for x in range(M):
		n = int(input())
		banned[n] = True
	for i in range(1, N + 1):
		res = 0
		if not banned[i - 1]:
			res += a[i - 1]
		if not banned[i - 2]:
			res += a[i - 2]
		a[i] = res
	print(a[-1] % mod)
	return
main()


(N, M) = [int(x) for x in input().split()]
dp = [1] * (N + 1)
for i in range(M):
	dp[int(input())] = 0
if N == 1:
	print(1)
else:
	for i in range(N - 1):
		dp[i + 2] = (dp[i] + dp[i + 1]) * dp[i + 2]
	print(dp[N] % 1000000007)


(n, m) = map(int, input().split())
a = list((int(input()) for _ in range(m)))
dp = [[] for _ in range(n + 1)]
dp[0] = 1
if m == 0:
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
	print(dp[n])
	return
if a[0] == 1:
	dp[1] = 0
	j = 1
else:
	dp[1] = 1
	j = 0
for i in range(2, n + 1):
	if j < m:
		if a[j] == i:
			dp[i] = 0
			j += 1
			continue
	dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])


(N, M) = map(int, input().split())
a = [0]
for i in range(0, M):
	a.append(int(input()))
a.append(N + 1)
b = [0] * (N + 2)
b[0] = 0
b[1] = 1
for j in range(0, M + 1):
	for i in range(a[j] + 2, a[j + 1] + 1):
		b[i] = (b[i - 1] + b[i - 2]) % 1000000007
print(b[N + 1])


(n, m) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [1] * (n + 1)
for _ in range(m):
	dp[int(input())] = 0
dp[1] *= dp[0]
for i in range(2, n + 1):
	dp[i] *= dp[i - 1] + dp[i - 2]
print(dp[-1] % mod)


(N, M) = map(int, input().split())
A = set([int(input()) for _ in range(M)])
step = [0] * (N + 1)
step[0] = 1
if 1 not in A:
	step[1] = 1
else:
	step[1] = 0
for i in range(2, N + 1):
	if i in A:
		continue
	step[i] = (step[i - 1] + step[i - 2]) % 1000000007
print(step[-1])


(n, _, *a) = map(int, open(0).read().split())
a = set(a)
(c, d) = (1, 0)
for i in range(n):
	n = (c + d) % (10 ** 9 + 7) * (not -~i in a)
	(c, d) = (n, c)
print(n)


(N, M) = map(int, input().split())
broken = [0] * N
for _ in range(M):
	a = int(input())
	broken[a] = 1
dp = [0] * (N + 2)
dp[N] = 1
for i in range(N - 1, -1, -1):
	if broken[i] == 1:
		dp[i] = 0
	else:
		dp[i] = (dp[i + 1] + dp[i + 2]) % 1000000007
print(dp[0])


(N, M) = map(int, input().split())
A = {int(input()) for _ in [0] * M}
D = [1, 0 if 1 in A else 1]
for i in range(2, N + 1):
	D += [0] if i in A else [(D[-1] + D[-2]) % 1000000007]
print(D[N])


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
b = set(a)
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for j in range(n):
	if j + 1 not in b:
		dp[j + 2] = (dp[j] + dp[j + 1]) % (10 ** 9 + 7)
	else:
		dp[j + 2] = 0
print(dp[j + 2] % (10 ** 9 + 7))


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

def Fib(n):
	(a, b) = (0, 1)
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n - 2):
			(a, b) = (b, a + b)
		return b
(n, m) = input2()
A = [int(input()) for _ in range(m)]
INF = 1000000007
start = 0
ans = 1
for a in A:
	tmp = a - start
	if tmp > 1:
		fib = Fib(tmp + 1)
		ans *= fib
		ans %= INF
	elif tmp == 0:
		ans = 0
		break
	start = a + 1
if n - start > 1:
	ans *= Fib(n - start + 2)
	ans %= INF
print(ans)


(N, M) = map(int, input().split())
A = set([int(input()) for _ in range(M)])
mod = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in A:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in A:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= mod
print(dp[N])


(n, m) = list(map(int, input().split()))
a = {}
for i in range(m):
	a[int(input())] = True
c = [0] * (n + 1)
c[0] = 1
for i in range(1, n + 1):
	if not i in a:
		c[i] = c[i - 1] + c[i - 2]
print(c[n] % 1000000007)


(n, m) = map(int, input().split())
A = list((int(input()) for i in range(m))) + [-1]
dp = [0] * (n + 1)
dp[0] = 1
j = 0
for i in range(1, n + 1):
	if i == A[j]:
		dp[i] = 0
		j += 1
	else:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % 1000000007)


(N, M) = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
step = [0] * (N + 1)
last = -1
for a in A:
	if a == last + 1 or a == last - 1:
		print(0)
		return
	step[a] = 1
	last = a
ans = [0] + [1] + [0] * N
chk = 0
for i in range(1, N + 1):
	if step[i] == 0 and chk <= 0:
		ans[i + 1] = ans[i] + ans[i - 1]
		chk = 0
	elif step[i] == 1:
		ans[i + 1] = ans[i]
		chk = 2
	elif step[i] == 0 and chk > 0:
		ans[i + 1] = ans[i]
		chk -= 1
print(ans[-1] % (10 ** 9 + 7))


(N, M) = map(int, input().split())
A = set([int(input()) for _ in range(M)])
dp = [0, 1]
for i in range(N):
	if i + 1 in A:
		dp.append(0)
	else:
		dp.append(dp[i] + dp[i + 1])
print(dp[N + 1] % 1000000007)


(n, m) = map(int, input().split())
mod = int(1000000000.0 + 7)
f = [True for i in range(n + 1)]
for i in range(m):
	f[int(input())] = False
dp = [1] + [0 for i in range(n + 1)]
for i in range(n):
	if f[i + 1]:
		dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])


(n, m) = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))
mod = 1000000007
memo = [-1] * (n + 1)
memo[0] = 0
for k in range(m):
	memo[a[k]] = 0
for i in range(1, n + 1):
	if memo[i] != -1:
		pass
	elif i <= 2:
		memo[i] = memo[i - 1] + 1
	else:
		memo[i] = memo[i - 1] + memo[i - 2]
print(memo[-1] % mod)


(N, M) = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
	if k > n - k:
		k = n - k
	de = 1
	nu = 1
	for i in range(k):
		de *= n - i
		de = de % MOD
		nu *= i + 1
		nu = nu % MOD
	nu = pow(nu, -1, MOD)
	return de * nu % MOD

def calc_from_step(step):
	temp = 0
	for i in range(1 + step // 2):
		temp += comb(step - i, i)
	return temp
arr = [1, 1]
steps = []
step = 0
s = 0
for i in range(M):
	l = int(input()) - 1
	steps.append(l - s)
	if s > l:
		print(0)
		return
	if step < l - s:
		step = l - s
	s = l + 2
l = N
steps.append(l - s)
if step < l - s:
	step = l - s
for i in range(step - 1):
	arr.append((arr[i] + arr[i + 1]) % MOD)
ans = 1
for i in steps:
	ans *= arr[i]
	ans = ans % MOD
print(ans)


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
a = sorted(list(set(range(2, n + 1)) - set(a)))
for i in a:
	dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
print(dp[n] % MOD)


(n, m) = list(map(int, input().split()))
A = []
broken = [True] * n
for i in range(m):
	a = int(input())
	A.append(a)
	broken[a] = False
dp = [0] * (n + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	if broken[i - 1]:
		dp[i] += dp[i - 1]
	if i >= 2 and broken[i - 2]:
		dp[i] += dp[i - 2]
	dp[i] %= mod
print(dp[n])


(n, m) = map(int, input().split())
step = [True] * n
r = [0, 1]
MOD = 10 ** 9 + 7
for _ in range(m):
	broken = int(input())
	step[broken - 1] = False
for (i, tf) in enumerate(step):
	if tf:
		r += [(r[i] + r[i + 1]) % MOD]
	else:
		r += [0]
print(r[-1])


import numpy as np
mod = 1000000007
(N, M) = map(int, input().split())
a = np.array([int(input()) for _ in range(M)])
dp = np.full(N + 1, -1)
dp[0] = 1
index = 0
for i in range(1, N + 1):
	if index < M and i == a[index]:
		dp[i] = 0
		index += 1
	else:
		dp[i] = dp[i - 1]
		if i >= 2:
			dp[i] += dp[i - 2]
		dp[i] %= mod
print(dp[N])


mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
l = [1] * (n + 1)
for i in range(m):
	a = int(input())
	l[a] = 0
for i in range(2, n + 1):
	if l[i] == 0:
		continue
	l[i] = (l[i - 2] + l[i - 1]) % mod
print(l[n])


MOD = 10 ** 9 + 7
(N, M) = [int(s) for s in input().split()]
ans = [1 for s in range(N + 2)]
ans[N + 1] = 0
for i in range(M):
	ans[int(input())] = 0
for i in range(1, N + 1):
	if ans[i] != 0:
		ans[i] = (ans[i - 1] + ans[i - 2]) % MOD
print(ans[N])


(N, M) = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10 ** 9 + 7
step = [1] * (N + 1)
for a in A:
	step[a] = 0
for i in range(2, N + 1):
	step[i] = (step[i - 1] + step[i - 2]) % mod * step[i]
print(step[-1])


(N, M) = map(int, input().split())
br = set([int(input()) for _ in range(M)])
dp = [0] * (N + 1)
dp[0] = 1
if not 1 in br:
	dp[1] = 1
for i in range(2, N + 1):
	if not i in br:
		dp[i] += (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[-1])


key = 10 ** 9 + 7
(N, M) = map(int, input().split())
A = [int(input()) for _ in range(M)] + [-1]
fibs = [0] * (N + 1)
index = 0
for i in range(N + 1):
	if i == A[index]:
		fibs[i] = 0
		index += 1
	elif i == 0 or i == 1:
		fibs[i] = 1
	else:
		fibs[i] = (fibs[i - 1] + fibs[i - 2]) % key
print(fibs[N])


(N, M, *C) = map(int, open(0).read().split())
MOD = 10 ** 9 + 7
F = [0] * (N + 1)
for c in C:
	F[c - 1] = 1
a = 1
b = 0
for i in range(N):
	if F[i]:
		(a, b) = (0, a)
	else:
		(a, b) = ((a + b) % MOD, a)
print(a)


(n, m) = map(int, input().split())
l = set((int(input()) - 1 for _ in range(m)))
(s, t) = (0, 1)
for i in range(n):
	(s, t) = (t, (s + t) % (10 ** 9 + 7) * (1 - (i in l)))
print(t)


(N, M) = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = set(A)
X = [1, 1 if 1 not in B else 0]
for i in range(2, N + 1):
	x = (X[-1] + X[-2]) % 1000000007
	X.append(x if i not in B else 0)
print(X[N])


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)] + [-1]
dp = [0] * (10 ** 5 + 5)
(dp[0], idx) = (1, 0)
for i in range(1, n + 1):
	if a[idx] == i:
		idx += 1
		dp[i] = 0
		if dp[i - 1] == 0:
			print(0)
			return
	else:
		dp[i] += dp[i - 1] + dp[i - 2]
		dp[i] %= 10 ** 9 + 7
print(dp[n])


(n, m) = map(int, input().split())
a = [0] * (m + 2)
a[m] = n + 10
a[m + 1] = n + 10
for i in range(m):
	a[i] = int(input())
answer = [0] * (n + 1)
answer[0] = 1
if n == 1:
	if a[0] == 1:
		print(0)
	else:
		print(1)
else:
	answer[0] = 1
	if a[0] == 1:
		answer[1] = 0
		a.pop(0)
	else:
		answer[1] = 1
	for i in range(2, n + 1):
		if a[0] == i or a[1] == i:
			answer[i] = 0
		elif a[0] == i - 1:
			answer[i] = answer[i - 2]
			a.pop(0)
		else:
			answer[i] = answer[i - 1] + answer[i - 2]
		answer[i] = answer[i] % 1000000007
	print(answer[n])


(n, b, *a) = map(int, open(0).read().split())
a = set(a)
d = i = 0
c = 1
while i < n:
	i += 1
	b = (c + d) % (10 ** 9 + 7) * (not {i} & a)
	(c, d) = (b, c)
print(b)


(N, M) = map(int, input().split())
A = set((int(input()) for m in range(M)))
dp = (N + 1) * [0]
dp[0] = 1
for n in range(1, N + 1):
	if n not in A:
		dp[n] = (dp[n - 2] + dp[n - 1]) % (10 ** 9 + 7)
print(dp[-1])


(N, M) = map(int, input().split())
step = [1] * (N + 1)
for _ in range(M):
	A = int(input())
	step[A] = 0
for i in range(2, N + 1):
	if step[i] == 0:
		continue
	step[i] = (step[i - 1] + step[i - 2]) % (10 ** 9 + 7)
print(step[-1] % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
(N, M) = map(int, input().split())
dp = [1] * (N + 1)
for i in range(M):
	dp[int(input())] = 0
for n in range(2, N + 1):
	if dp[n] != 0:
		dp[n] = dp[n - 1] + dp[n - 2]
print(dp[N] % MOD)


(N, M) = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
dp = [0] * (N + 1)
dp[0] = 1
safe = []
for i in range(1, N + 1):
	if len(A) != 0:
		if A[0] == i:
			A.pop(0)
			continue
	safe.append(i)
for s in safe:
	for i in range(1, 3):
		if s - i >= 0:
			dp[s] += dp[s - i]
	dp[s] %= 10 ** 9 + 7
print(dp[N])


(N, M) = map(int, input().split())
List = [int(input()) for _ in range(M)]
P = 10 ** 9 + 7
dp = [1] * (N + 1)
for i in List:
	dp[i] = 0
for j in range(1, N):
	if dp[j + 1] != 0:
		dp[j + 1] = dp[j] + dp[j - 1]
print(dp[N] % P)


(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
a = set(a)
A = [0] * (n + 1)
A[0] = 1
for i in range(1, n + 1):
	if i in a:
		A[i] == 0
	else:
		A[i] = A[i - 1] + A[i - 2]
print(A[n] % (10 ** 9 + 7))


(N, M) = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod = 10 ** 9 + 7
X = [1 for _ in range(N + 1)]
for i in a:
	X[i] = 0
for j in range(2, N + 1):
	if X[j]:
		X[j] = X[j - 1] + X[j - 2]
ans = X[N] % mod
print(ans)


def solve(N, a):
	mod = 10 ** 9 + 7
	dp = [0] * (N + 1)
	step = [0] * (N + 1)
	for aa in a:
		step[aa] = 1
	dp[0] = 1
	if step[1] == 0:
		dp[1] = 1
	for i in range(2, N + 1):
		if step[i] == 0:
			dp[i] = dp[i - 1] + dp[i - 2]
			dp[i] %= mod
	return dp[N]

def __starting_point():
	(N, M) = list(map(int, input().split()))
	a = [int(input()) for _ in range(M)]
	print(solve(N, a))
__starting_point()


(N, M) = map(int, input().split())
As = [1] * (N + 1)
mod = 10 ** 9 + 7
for _ in range(M):
	i = int(input())
	As[i] = 0
for i in range(N - 1):
	if As[i + 2] > 0:
		As[i + 2] = As[i + 1] + As[i]
print(As[-1] % mod)


(N, M, *a) = map(int, open(0).read().split())
dp = [1] * (N + 1)
for i in a:
	dp[i] = 0
for n in range(2, N + 1):
	dp[n] = (dp[n - 1] + dp[n - 2]) % 1000000007 * dp[n]
print(dp[N])


(N, M) = map(int, input().split())
A = [1] * (N + 1)
for i in range(M):
	K = int(input())
	A[K] = 0
for j in range(2, N + 1):
	if A[j] != 0:
		A[j] = A[j - 1] + A[j - 2]
print(A[N] % (10 ** 9 + 7))


M = 10 ** 9 + 7
(n, m, *l) = map(int, open(0).read().split())
dp = [1] + [0] * n
for i in l:
	dp[i] = -1
dp[1] += 1
for i in range(n - 1):
	if dp[i + 2] < 0:
		dp[i + 2] = 0
	else:
		dp[i + 2] = (dp[i] + dp[i + 1]) % M
print(dp[n])


INIT = 1
(n, m) = map(int, input().split())
dp = [INIT for i in range(n + 1)]
for i in range(m):
	a = int(input())
	dp[a] = 0
for i in range(2, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]
print(dp[n] % 1000000007)


(n, m) = map(int, input().split())
broken = [False] * (n + 1)
for _ in range(m):
	i = int(input())
	broken[i] = True
dp = [0] * (n + 1)
dp[0] = 1
mod = 1000000007
for i in range(1, n + 1):
	if broken[i]:
		continue
	if i == 1:
		dp[1] = 1
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % mod)


import sys
pin = sys.stdin.readline
sys.setrecursionlimit(10000000)

def f(n):
	if n == 0:
		return 1
	if n == 1:
		if dp[n] == 0:
			return 0
		return 1
	if dp[n] == 0:
		return 0
	if dp[n - 1] == -1:
		dp[n - 1] = f(n - 1)
	if dp[n - 2] == -1:
		dp[n - 2] = f(n - 2)
	return dp[n - 1] + dp[n - 2]
(N, M) = map(int, pin().split())
mod = 1000000007
dp = [-1] * (N + 1)
dp[0] = 1
for i in range(M):
	dp[int(pin())] = 0
print(f(N) % mod)


import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
broken = set([int(readline()) for i in range(M)])
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in broken:
	dp[1] = 1
DIV = 10 ** 9 + 7
for i in range(2, N + 1):
	if i in broken:
		continue
	dp[i] = dp[i - 2] + dp[i - 1]
	dp[i] %= DIV
print(dp[N])


(n, m) = map(int, input().split())
a1 = 0
ans = 1
for i in range(m + 1):
	if i == m:
		a2 = n + 1
	else:
		a2 = int(input())
	l = a2 - a1
	if l == 0:
		print(0)
		return
	if l > 2:
		fst = 1
		snd = 1
		for _ in range(l - 2):
			nfst = snd
			snd = fst + nfst
			fst = nfst
		ans *= snd
	a1 = a2 + 1
print(ans % (10 ** 9 + 7))


(n, m) = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 10 ** 9 + 7
a.append(float('INF'))
a = a[::-1]
dp = [0] * (n + 1)
dp[0] = 1
if a[-1] != 1:
	dp[1] = 1
else:
	a.pop()
for i in range(2, n + 1):
	if i == a[-1]:
		a.pop()
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= mod
print(dp[n])


def main():
	(N, M) = list(map(int, input().split()))
	A = set([int(input()) for x in range(M)])
	mod = 10 ** 9 + 7
	dp = [0] * 10 ** 6
	dp[0] = 1
	for i in range(N + 1):
		if i in A:
			continue
		dp[i + 1] += dp[i] % mod
		dp[i + 2] += dp[i] % mod
	print(dp[N] % mod)

def __starting_point():
	main()
__starting_point()


fib = [0, 0, 1, 2]
for i in range(4, 100005):
	fib.append(fib[i - 1] + fib[i - 2])
(n, m) = map(int, input().split())
a = [int(input()) for i in range(m)]
a = set(a)
(p, q) = (0, 1)
for i in range(1, n + 1):
	(p, q) = (q, (p + q) % (10 ** 9 + 7) * (not i in a))
print(q)


(n, m) = map(int, input().split())
l = {int(input()) for i in range(m)}
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(1, 1 + n):
	if i not in l:
		dp[i] += dp[i - 1] + dp[i - 2]
		dp[i] %= 10 ** 9 + 7
print(dp[n])


(n, m) = list(map(int, input().split()))
lst = [-1 for i in range(n + 1)]
for i in range(m):
	x = int(input())
	lst[x] = 0
lst[0] = 1
for i in range(1, n + 1):
	if i == 1:
		if lst[1] == -1:
			lst[1] = 1
	elif lst[i] == 0:
		pass
	else:
		lst[i] = (lst[i - 1] + lst[i - 2]) % 1000000007
print(lst[n])


(N, M) = map(int, input().split())
rs = [-1] * (N + 1)
rs[0] = 1
rs[1] = 1
for m in range(M):
	am = int(input())
	rs[am] = 0
for n in range(1, N):
	rs[n + 1] = 0 if rs[n + 1] == 0 else rs[n] + rs[n - 1]
print(rs[N] % 1000000007)


(n, m) = map(int, input().split())
inf = 1000000007
ans = 1
dp = [1] * (n + 1)
for i in range(m):
	dp[int(input())] = 0
for i in range(n - 1):
	dp[i + 2] = (dp[i] + dp[i + 1]) * dp[i + 2]
print(dp[-1] % inf)


(n, m) = map(int, input().split())
step = []
now = 0
for i in range(m):
	next = int(input()) - 1
	step.append(next - now)
	now = next + 2
step.append(n - now)
step.sort()

def fibo():
	s = []
	a = 1
	b = 1
	s.append(a)
	s.append(b)
	for i in range(n):
		c = a + b
		a = b
		b = c
		s.append(c)
	return s
ans = 1
if step[0] < 0:
	ans = 0
else:
	f = fibo()
	for i in step:
		ans *= f[i]
print(ans % 1000000007)


(n, _, *l) = map(int, open(0).read().split())
l = set(l)
(s, t) = (0, 1)
for i in range(n):
	(s, t) = (t, (s + t) % (10 ** 9 + 7) * (not {i + 1} & l))
print(t)


(n, m) = map(int, input().split())
a = {int(input()) for i in range(m)}
mod = 10 ** 9 + 7
x = 1 if 1 not in a else 0
dp = [1, x] + [0] * (n - 1)
for i in range(2, n + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] % mod)


url = 'https://atcoder.jp//contests/abc129/tasks/abc129_c'

def main():
	(n, m) = list(map(int, input().split()))
	isbreak = [False] * (n + 1)
	for _ in range(m):
		isbreak[int(input())] = True
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(n):
		for j in range(i + 1, min(i + 3, n + 1)):
			if not isbreak[j]:
				dp[j] += dp[i]
				dp[j] %= 1000000007
	print(dp[-1])

def __starting_point():
	main()
__starting_point()


MOD = 10 ** 9 + 7
(n, m) = map(int, input().split())
a = [0] * m
dp = [1] * (n + 1)
for i in range(m):
	a[i] = int(input())
	dp[a[i]] = 0
for i in range(2, n + 1):
	if dp[i] == 0:
		continue
	else:
		dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % MOD)


(n, m, *a) = map(int, open(0).read().split())
a = set(a)
mod = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for st in range(2, n + 1):
	if st in a:
		continue
	dp[st] = dp[st - 1] + dp[st - 2]
	dp[st] %= mod
print(dp[n])


import sys
mod = 10 ** 9 + 7
inf = float('inf')
from math import sqrt, ceil
from collections import deque, Counter, defaultdict
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP, Decimal
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
(n, m) = list(map(int, input().split()))
A = [int(input()) for i in range(m)]
NG = [0] * (10 ** 5 + 10)
for i in A:
	NG[i] = 1

@lru_cache(maxsize=10 ** 10)
def qwe(x):
	if x == n:
		return 1
	if x > n:
		return 0
	if NG[x + 1] and NG[x + 2]:
		print(0)
		return
	if NG[x + 1]:
		return qwe(x + 2) % mod
	if NG[x + 2]:
		return qwe(x + 1) % mod
	return (qwe(x + 2) + qwe(x + 1)) % mod
print(qwe(0))


(n, m) = map(int, input().split())
ans = [0] * (n + 1)
p = 10 ** 9 + 7
ans[0] = 1
for i in range(m):
	ans[int(input())] = -1
if ans[1] != -1:
	ans[1] = 1
for i in range(2, n + 1):
	if ans[i] == -1:
		continue
	ans[i] = max(ans[i - 1], 0) + max(ans[i - 2], 0)
	ans[i] %= p
print(ans[n] % p)


(n, m) = map(int, input().split())
u = [0] * (n + 1)
for i in range(m):
	u[int(input())] = 1
ll = [0] * (n + 2)
ll[1] = 1
for i in range(2, n + 2):
	if not u[i - 1]:
		ll[i] = ll[i - 1] + ll[i - 2]
print(ll[-1] % 1000000007)


(n, m) = map(int, input().split())
a = [True] * (n + 1)
for i in range(m):
	a[int(input())] = False
r = [0] * (n + 1)
r[0] = 1
for i in range(1, n + 1):
	if not a[i]:
		continue
	r[i] = (r[i - 1] + r[i - 2]) % 1000000007
print(r[n])


mod = 10 ** 9 + 7
(n, m) = map(int, input().split())
l = [0] * n
for _ in range(m):
	l[int(input()) - 1] = 1
s = 0
t = 1
for i in range(n):
	if l[i] > 0:
		(t, s) = (0, t)
	else:
		(t, s) = ((s + t) % mod, t)
print(t)


(n, m) = list(map(int, input().split()))
MOD = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
for _ in range(m):
	dp[int(input())] = -1
for i in range(n + 1):
	if dp[i] == -1:
		continue
	if i + 1 <= n and dp[i + 1] != -1:
		dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
	if i + 2 <= n and dp[i + 2] != -1:
		dp[i + 2] = (dp[i + 2] + dp[i]) % MOD
print(dp[-1])


(n, m) = map(int, input().split())
fib = [0] * (n + 2)
fib[0] = 0
fib[1] = 1
for i in range(n):
	fib[i + 2] = fib[i] + fib[i + 1]
ans = 1
k = 0
for i in range(m):
	a = int(input())
	ans *= fib[a - k]
	k = a + 1
ans *= fib[n - k + 1]
print(ans % 1000000007)


(N, M) = map(int, input().split())
lsS = [1, 1] + [0] * (N - 1)
for i in range(M):
	lsS[int(input())] = -1
for i in range(2, N + 1):
	if lsS[i] == -1:
		continue
	else:
		if lsS[i - 2] != -1:
			lsS[i] += lsS[i - 2]
		if lsS[i - 1] != -1:
			lsS[i] += lsS[i - 1]
		lsS[i] = lsS[i] % (10 ** 9 + 7)
print(lsS[N])


def f():
	(n, m) = map(int, input().split())
	a = [int(input()) for _ in range(m)]
	for i in range(m - 1):
		if a[i] + 1 == a[i + 1]:
			return 0
	mod = 10 ** 9 + 7
	x = [1] * (n + 1)
	for j in a:
		x[j] = 0
	for k in range(2, n + 1):
		if x[k] == 1:
			x[k] = (x[k - 1] + x[k - 2]) % mod
	return x[n]
print(f())


div = 10 ** 9 + 7
(N, M) = map(int, input().split())
h = [1] * (N + 1)
for _ in range(M):
	index = int(input())
	h[index] = 0
a = 1
b = h[1]
for i in range(2, N + 1):
	(a, b) = (b, (a + b) * h[i] % div)
print(b)


(N, M) = map(int, input().split())
a = [1] * (N + 1)
for i in range(M):
	a[int(input())] = 0
mod = 1000000007
ans = [0] * (N + 1)
ans[0] = 1
for i in range(1, N + 1):
	ans[i] = (ans[i - 2] * a[i - 2] + ans[i - 1] * a[i - 1]) % mod
print(ans[N])


(n, m) = map(int, input().split())
a = [1] * (n + 1)
for i in range(m):
	a[int(input())] = 0
p0 = a[0]
p1 = a[1]
for i in range(2, n + 1):
	if a[i] == 1:
		p2 = p0 + p1
	else:
		p2 = 0
	(p0, p1) = (p1, p2)
print(p1 % 1000000007)


(N, M) = map(int, input().split())
A = [int(input()) for i in range(M)]
n = 0
if M != 0:
	a = b = A[0]
else:
	a = b = -2
c = 0
ans = [0, 1]
for i in range(1, N + 1):
	if i == a:
		c = 0
		n += 1
		b = a
		if n <= M - 1:
			a = A[n]
	elif i - 2 == b:
		c = ans[-1]
	elif i - 1 == b:
		c = ans[-2]
	else:
		c = ans[-1] + ans[-2]
	c %= 10 ** 9 + 7
	ans.append(c)
print(ans[-1])


MOD = 10 ** 9 + 7
(N, M) = [int(s) for s in input().split()]
ls = [1 for _ in range(N + 1)]
for i in range(M):
	ls[int(input())] = 0
for n in range(2, N + 1):
	if ls[n] != 0:
		ls[n] = (ls[n - 1] + ls[n - 2]) % MOD
print(ls[N])


(n, m) = map(int, input().split())
a = set([int(input()) for x in range(m)])
l = [0] * (n + 1)
l[0] = 1
for i in range(1, n + 1):
	if i in a:
		l[i] = 0
		continue
	else:
		l[i] = l[i - 2] + l[i - 1]
print(l[-1] % 1000000007)


(N, M) = map(int, input().split())
A = []
MOD = 1000000007
for _ in range(M):
	a = int(input())
	A.append(a)
DP = [1] * (N + 1)
for i in A:
	DP[i] = 0
for i in range(2, N + 1):
	DP[i] = (DP[i - 1] + DP[i - 2]) % MOD * DP[i]
print(DP[-1])


(N, M) = map(int, input().split())
D = [1] * (N + 1)
MOD = 10 ** 9 + 7
for _ in range(M):
	D[int(input())] = 0
for i in range(N + 1):
	if i < 2 or D[i] == 0:
		continue
	D[i] = (D[i - 1] + D[i - 2]) % MOD
print(D[i])


(n, m) = map(int, input().split())
broken = set()
stairs = [0] * (n + 2)
stairs[n] = 1
for _ in range(m):
	a = int(input())
	broken.add(a)
for j in range(n):
	if n - 1 - j in broken:
		continue
	stairs[n - 1 - j] = stairs[n - j] + stairs[n + 1 - j]
print(stairs[0] % 1000000007)


(n, m) = map(int, input().split())
const = 1000000007
r = [1 for i in range(n + 1)]
for i in range(m):
	r[int(input())] = 0
for i in range(2, n + 1):
	if r[i] > 0:
		r[i] = (r[i - 1] + r[i - 2]) % const
print(r[n])


(n, m) = map(int, input().split())
dq = [1] * (n + 1)
for _ in range(m):
	dq[int(input())] = 0
mod = 10 ** 9 + 7
(x, y) = (0, 1)
for i in range(1, n + 1):
	(x, y) = (y, dq[i] * (x + y) % mod)
print(y)


(N, M) = map(int, input().split())
MOD = 10 ** 9 + 7
F = [0] * (N + 1)
for i in range(M):
	F[int(input()) - 1] = 1
a = 1
b = 0
for i in range(N):
	if F[i]:
		(a, b) = (0, a)
	else:
		(a, b) = ((a + b) % MOD, a)
print(a)


MOD = 10 ** 9 + 7
(N, _, *a) = map(int, open(0).read().split())
A = set(a)
dp = [0 for _ in range(N + 1)]
dp[:2] = (1, 0 if 1 in A else 1)
for i in range(2, N + 1):
	if i not in A:
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
print(dp[N])


(N, M) = map(int, input().split())
A = [0] * M
for i in range(M):
	A[i] = int(input())
A = set(A)
K = 10 ** 9 + 7
X = [0] * (N + 1)
X[0] = 1
X[1] = 1 * (1 not in A)
for i in range(2, N + 1):
	if i not in A:
		X[i] = (X[i - 1] + X[i - 2]) % K
print(X[-1])


import sys
input = sys.stdin.readline
MOD = pow(10, 9) + 7

def MODINV(n: int, MOD=MOD):
	return pow(n, MOD - 2, MOD)

def main():
	(N, M) = list(map(int, input().split()))
	DP = [0] * (N + 1)
	ngset = set()
	for _ in range(M):
		a = int(input())
		ngset.add(a)
	DP[0] = 1
	if 1 not in ngset:
		DP[1] = DP[0]
	for i in range(2, N + 1):
		if i in ngset:
			continue
		DP[i] = DP[i - 1] + DP[i - 2]
		DP[i] %= MOD
	print(DP[N])

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
MOD = 10 ** 9 + 7
(p, q, n) = (0, 1, 1)
for _ in range(M):
	a = int(input())
	while n <= a:
		(p, q) = (q, p + q)
		n += 1
	q = 0
while n <= N:
	(p, q) = (q, p + q)
	n += 1
print(q % MOD)


(N, M) = [int(i) for i in input().split()]
AS = {int(input()) for _ in range(M)}
t = [1, 1 if 1 not in AS else 0]
for i in range(2, N + 1):
	if i in AS:
		t.append(0)
		continue
	t.append(t[i - 2] + t[i - 1])
print(t[N] % 1000000007)