Problem:
 Score : 300 points    Problem Statement 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 1 6 1
3      Sample Output 1 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        Sample Input 2 10 2
4
5      Sample Output 2 0  There may be no way to climb up the stairs without setting foot on the broken steps.       Sample Input 3 100 5
1
23
45
67
89      Sample Output 3 608200469  Be sure to print the count modulo 1\ 000\ 000\ 007 .

Solution (Python):
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=1 

dp[1]=1
for i in range(m):
    dp[t[i]]=0


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

Solution (Python):
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=1
dp[1]=1
for i in range(m):
    dp[t[i]]=0


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

Solution (Python):
n,m = map(int,input().split())
l = [int(input()) for _ in[0]*m]
l=set(l)
dp=[0]*(n+1)

dp[0]=1
dp[1]=0 if 1 in l else 1
MOD =10**9+7

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

Solution (Python):
n,m,*a=map(int,open(0).read().split())
a=set(a)
dp=[0]*(n+2)
dp[0]=1
div=1000000007
for i in range(n):
  dp[i]%=div
  if i+1 in a:
    dp[i+1]=0
  else:
    dp[i+1]+=dp[i]
  if i+2 in a:
    dp[i+2]=0
  else:
    dp[i+2]+=dp[i]
print(dp[n]%div)

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    
    dp = [-1]*(N+1)
    dp[0]=1
    dp[1]=1 
    for i in range(M):
        dp[a[i]] = 0
    
    for i in range(2,N+1):
        if dp[i] == 0:
            continue
        dp[i] = dp[i-1]+dp[i-2]
        dp[i]%=MOD
    print(dp[N]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(M)]  
    solve(N, M, a)

if __name__ == '__main__':
    main()

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

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n + 10)
dp[0] = 1
mod = 10**9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

if ok[1]:
    dp[1] = 1

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

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n + 10)
dp[0] = 1
mod = 10**9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

for i in range(n):
    if ok[i + 1]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if ok[i + 2]:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n + 10)
dp[0] = 1
mod = 1e9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

for i in range(n):
    if ok[i + 1]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if ok[i + 2]:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(int(dp[n]))

Solution (Python):
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

cnt2 = 0
cnt1 = 1
aa.append(-1)
a = aa.pop(0)


for i in range(1,n):
    if i == a:
        cnt2, cnt1 = cnt1, 0
        a = aa.pop(0)
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
mod=10**9+7
flag=1
S=[0 for i in range(n+3)]
S[0]=1
SET=set(A)
for i in range(n):
    if i in SET:
        S[i]=0
        if i+1 in SET:
            flag=0
    S[i+1]+=S[i]
    S[i+2]+=S[i]
    
print(S[n]%mod if flag==1 else 0)

Solution (Python):
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
mod=10**9+7
flag=1
S=[0]*(n+3)
S[0],S[1],S[2]=[1,1,2]
SET=set(A)
if 1 in SET:
    S[1]=0
if 2 in SET:
    S[2]=0
if 1 in SET and 2 in SET:
    flag=0
for i in range(2,n+1):
    if i in SET:
        if i+1 in SET:
            flag=0
        S[i]=0
    elif i not in SET:
        S[i]=S[i-1]+S[i-2]
print(S[n]%mod if flag==1 else 0)

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

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

Solution (Python):
n,m = map(int,input().split())
breaks = [0] * (n + 1)
for i in range(m):
    a = int(input())
    breaks[a] = 1

mod = (10**9)+7
dp = [0] * (n + 1)
dp[n] = 1
for i in reversed(range(n)):
    if(breaks[i] == 1):
        dp[i] = 0
        continue
    if(i == n - 1):
        dp[i] = dp[i+1]
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0] % mod)

Solution (Python):
mod = 1000000007

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

cur_ix = 0
for i in range(1, 3):
    if a[cur_ix] == i:
        s[i] = 0
        cur_ix += 1
    else:
        if i == 1:
            s[i] = 1
        elif i == 2:
            s[i] = s[i-1] + s[i-2] + 1

for i in range(3, N+1):
    if cur_ix < len(a) and a[cur_ix] == i:
        s[i] = 0
        cur_ix += 1
    else:
        s[i] = (s[i-1] + s[i-2]) % 1000000007
'''

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

dp = [0] * (n + 1)
dp[0] = 1
b = a[0]
j = 1
for i in range(1, n + 1):
    if i == b:
        b = a[j]
        j += 1
    else:
        tmp = dp[i - 2] + dp[i - 1]
        if tmp >= mod:
            tmp -= mod
        dp[i] = tmp
print(int(dp[-1]))

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

dp = [0] * (n + 1)
dp[0] = 1
b = a[0]
j = 1
for i in range(1, n + 1):
    if i == b:
        b = a[j]
        j += 1
    else:
        tmp = dp[i - 2] + dp[i - 1]
        if tmp >= mod:
            tmp -= mod
        dp[i] = tmp
print(int(dp[-1]))

Solution (Python):
import numpy as np

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

dp = np.zeros(n + 1, dtype=np.int64)
dp[0] = 1
b = a[0]
j = 1
for i in range(1, n + 1):
    if i == b:
        b = a[j]
        j += 1
    else:
        tmp = dp[i - 2] + dp[i - 1]
        if tmp >= mod:
            tmp -= mod
        dp[i] = tmp
print(int(dp[-1]))

Solution (Python):
n,m = map(int, input().split())

A = set()
for _ in range(m):
  A.add(int(input())) 

dp = [1]+[0]*(n)

for i in range(1, n+1):
  
  if i==1:
    dp[i] = dp[i-1]
  elif i>=2:
    dp[i] = (dp[i-1]+dp[i-2])%1000000007
    
  if i in A:
    dp[i] = 0
  
print(dp.pop())

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, m = map(int, input().split())
a = [1]+[-1]*(n)
cnt = 0
for _ in range(m):
    a[int(input())] = 0

a[1] *= -1
for i in range(2, n+1):
    if a[i] != 0:
        a[i] = ( max(0, a[i-1]) + max(0, a[i-2]) ) % MOD

print(a[-1])

Solution (Python):
N,M=map(int,input().split())
mod = 10**9+7
fram = [1]
for i in range(1,N+1):
  fram.append(fram[-1]*i%mod)






def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=fram[n]
    b=fram[k]
    c=fram[n-k]
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)])
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)

Solution (Python):
def solve():
    N, M, *a = map(int, open(0).read().split())
    ok = [True for _ in range(N+1)]
    for i in range(M):
        ok[a[i]] = False
    MOD = 1000000007

    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for i in range(N):
        for j in range(i+1, min(N+1, i+3)):
            if ok[j]:
                dp[j] += dp[i]
                dp[j] %= MOD
    print(dp[N])


if __name__ == '__main__':
    solve()

Solution (Python):
n, m = map(int, input().split())
As = [int(input()) for i in range(m)]


dp = [0] * (n+1)
mod = 10**9 + 7

is_safe = [True] * (n+1)
for i in range(m):
    is_safe[As[i]] = False



for i in range(n+1):
    if i == 0:
        dp[i] = 1
    
    elif not is_safe[i]:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1] % mod + dp[i-2] % mod) % mod


print(dp[n])

Solution (Python):
n,m = map(int,input().split())



MOD = 10 ** 9 + 7
dp = [0] * (n+1)
a_L = []

for val in range(m):
    a_L.append(int(input()))


a_L = set(a_L)
dp[0] = 1
if 1 in a_L:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if i not in a_L:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 0

print(dp[n]%MOD)

Solution (Python):
n,m = map(int,input().split())



MOD = 10 ** 9 + 7
dp = [0] * (n+1)
a_L = []

for val in range(m):
    a_L.append(int(input()))


a_L = set(a_L)
dp[0] = 1
if 1 in a_L:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    if i not in a_L:
        dp[i] = (dp[i-1] + dp[i-2])%MOD
    else:
        dp[i] = 0

print(dp[n]%MOD)

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

mod = 10**9 + 7

i = 0
b = []
for ai in a:
    b.append(ai - i)
    i = ai + 1
b.append(N + 1 - i)


@lru_cache(maxsize=None)
def f(n):
    if n < 2:
        return n
    else:
        return f(n - 2) + f(n - 1)


ans = 1
for bi in b:
    ans *= f(bi) % mod
print(ans % mod)

Solution (Python):
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
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])

Solution (Python):
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])

Solution (Python):
N,M = map(int,input().split())
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])%(10**9+7)
    if i in A:
        dp[i]=0
print(dp[N])

Solution (Python):
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])

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

Solution (Python):
MOD = 10**9+7
N, M = map(int, input().split())
broken = {int(input()) for _ in range(M)}

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

for i in reversed(range(N)):
    if i not in broken:
        dp[i] = dp[i+1] + dp[i+2]
        dp[i] %= MOD

print(dp[0])

Solution (Python):
N, M = map(int, input().split())
MOD = 1000000007

def fib(n):
  a, b = 1, 1
  for i in range(n):
    a, b = b, a+b
  return a

ans  = 1
last = 0
for _ in range(M):
  a = int(input())
  if a == last:
    ans = 0
  ans *= (fib(a-1-last) % MOD)
  last = a + 1

  
ans *= (fib(N - last) % MOD)
print(ans%MOD)

Solution (Python):
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
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[-1])

Solution (Python):
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
booli = [False]*(N+1)
for i in a:
    booli[i] = True
mod = 1000000007
INF = -1
dp = [INF]*(N+1)
dp[0] = 1
if booli[1]:
    dp[1] = 0
else:
    dp[1] = 1
def solve():
    for i in range(2,N+1):
        if booli[i]:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]+dp[i-2]
    return dp[N]%mod
print(solve())

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

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

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.insert(0, -1)
a.append(n+1)
a = [a[i+1] - a[i] - 2 for i in range(m+1)]
count = 1
if not -1 in a:
  for i in a:
    a_0 = 1
    a_1 = 1
    ans = 1
    for _ in range(i-1):
      ans = a_0 + a_1
      a_0 = a_1
      a_1 = ans
    count *= ans
  print(count % 1000000007)
else: print(0)

Solution (Python):
n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
if 1 in p:
    dp[1] = 0

for i in range(2, n+1):
    if i in p:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % s

print(dp[-1])

Solution (Python):
N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    
    



if N>=2:
    if ldp[1]!=-1:
        ldp[1]+=1
        if ldp[0]!=-1:
            ldp[1]+=1
    for i in range(2,N):
        if ldp[i]!=-1:
            if ldp[i-1]!=-1:
                ldp[i]=(ldp[i]+ldp[i-1])%K
            if ldp[i-2]!=-1:
                ldp[i]=(ldp[i]+ldp[i-2])%K

print(ldp[N-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left

N,M = map(int,input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())
a.sort()
len_a = len(a)

MOD = 10**9 + 7


dp = [0] * (N+1)


dp[0] = 1

for i in range(N):
    if i == N-1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
        continue

    index = bisect_left(a,i+1)
    if index == len_a or a[index] != i + 1:
        dp[i+1] = dp[i+1] + dp[i] % MOD
    index = bisect_left(a,i+2)
    if index == len_a or a[index] != i + 2:
        dp[i+2] = dp[i+2] + dp[i] % MOD

print(dp[-1] % MOD)

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

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

Solution (Python):
N,M=map(int,input().split())
mod=10**9+7

a=[]
for i in range(M):
    a.append(int(input()))
a.sort(reverse=True)

DP=[1]*(N+1)

if len(a)>0 and 1==a[-1]:
    DP[1]=0
    a.pop()


for i in range(2,N+1):
    if len(a)>0 and i==a[-1]:
        DP[i]=0
        a.pop()
        if DP[i-1]==0:
            print(0)
            exit()
    else:
        DP[i]=DP[i-1]+DP[i-2]
        DP[i]=DP[i]%mod

print(DP[N])

Solution (Python):
import bisect
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
broken = [0]*(N+1)
for i in range(M):
    broken[a[i]] = 1
if M == 0:  a.append(0)
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if broken[i] == 1:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])

Solution (Python):
import sys
def input():
  return sys.stdin.readline().rstrip()
mod = 10**9 + 7
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
notin = [1] * n
for i in a:
  notin[i] = 0
dp = [0] * n
dp[n - 1] = 1
if n > 1:
	dp[n - 2] = 1 + notin[n - 1]
for i in range(n - 3, -1, -1):
  dp[i] += dp[i + 1] * notin[i + 1] % mod
  dp[i] += dp[i + 2] * notin[i + 2] % mod
  dp[i] %= mod
print(dp[0])

Solution (Python):
n,m=map(int,input().split())
a={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
for i in range(2,len(dp)):
      if i not in a:
            dp[i]=dp[i-1]+dp[i-2]
      
print(dp[-1]%mod)

Solution (Python):
n,m=map(int,input().split())
a=[0]+[int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1
j=0

if m>0:
    j+=1

if 1!=a[j]:
    dp[1]=1
elif 1==a[j]:
    dp[1]=0
    j+=1
    if j>m:
        j-=1
for i in range(2,n+1):
    if i!=a[j]:
        dp[i]=dp[i-1]+dp[i-2]
    elif i-1==a[j-1]:
        print(0)
        exit()
    else:
        j+=1
    if j>m:
        j-=1
print(dp[n]%(10**9+7))

Solution (Python):
N,M = map(int, input().split())
a = [-1]+[int(input()) for _ in range(M)]+[N+1]
mod = 10**9+7
fact = [1]+[0]*N
finv = [1]+[0]*N
for i in range(1,N+1):
    fact[i] = fact[i-1]*i % mod
    finv[i] = pow(fact[i], mod-2, mod)

def cmb(a,b):
    n = max(a,b)
    r = abs(a-b)
    if not n or min(a,b) < 0:
        return 0
    else:
        return fact[n]*finv[n-r]*finv[r] % mod
ans = 1
for i in range(1,M+2):
    if a[i] == 1:
        continue
    elif a[i] == N and a[i-1] == N-1:
        continue
    elif a[i]-a[i-1] == 2:
        continue
    b = a[i]-a[i-1]-2
    ansp = 0
    for j in range(b - (b+1) // 2 + 1):
        ansp = (ansp + cmb(b-j, j)) % mod
    ans = ans * ansp % mod

print(ans)

Solution (Python):
N,M=map(int,input().split())
mod=10**9+7
A=set([int(input()) for i in range(M)])

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if N>=2:
    if 2 not in A:
        data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod



print(data[-1])

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

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista.append(am)
lista.append(0)    
an = 0
an1 = 1 
for n in range(N):
    if n+1 == lista[0]:
        del lista[0]
        
        an, an1 = an1, 0
    else:
        an, an1 = an1, (an+an1)%1000000007
print(an1)

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

print(dp[n])

Solution (Python):
import sys
input  = sys.stdin.readline

N,M = map(int,input().split())
dp = [0]*N
for i in range(M):
  a = int(input())
  dp[a-1]=-1

for i in range(N):
  if dp[i]==-1:
    dp[i]=0
  else:
    if i==0:
      dp[i]=1
    elif i==1:
      dp[i]=1+dp[0]
    else:
      dp[i]=dp[i-1]+dp[i-2]
    dp[i]=dp[i]%1000000007
print(dp[-1])

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

Solution (Python):
MOD = 10**9+7
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

safe = [True] * (n+1)
for a in A:
    safe[a] = False

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if safe[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[n])

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

Solution (Python):

def ABC129C_TypicalStairs():
    mod_num = 1000000007
    
    N, M = list(map(int, input().strip().split()))
    brk = [int(input())  for i in range(M)]
    

    dp = [0] * (N + 1)
    for i in range(M):
        dp[brk[i]] = -1

    dp[0] = 1
    if dp[1] != -1:
        dp[1] = 1

    for i in range(2, N + 1):
        if(dp[i] == -1):
            continue
        if(dp[i - 1] != -1):
            dp[i] += dp[i - 1]
            dp[i] %= mod_num
        if(dp[i - 2] != -1):
            dp[i] += dp[i - 2]
            dp[i] %= mod_num


    print(dp[N])

def main():
    ABC129C_TypicalStairs()

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
dp = [0] * (N+1)
dp[0] = 1
p = 10**9 + 7

for i in range(M):
  dp[int(input())] = -1

for i in range(N):
  if dp[i] == -1: continue
  a = dp[i] % p
  if dp[i+1] != -1: dp[i+1] += a
  if i+1 < N and dp[i+2] != -1: dp[i+2] += a

print(dp[-1] % p)

Solution (Python):
from collections import deque

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

Solution (Python):
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))

Solution (Python):
import sys
input = sys.stdin.readline

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

broken= [False]*(N+1)
for i in range(M):
    broken[int(input())] = True

dp = [0]*(N+1)
dp[0] = 1
if not broken[1]:dp[1] = 1

         
for i in range(2, N+1):
    if broken[i]:continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= (10**9 + 7)
print(dp[N])

Solution (Python):
from collections import deque
N,M = map(int,input().split())
a = deque([int(input()) for m in range(M)]+[-1])
ans = []
P = 10**9+7
for n in range(N):
    if n+1 == a[0]:
        ans.append(0)
        a.popleft()
    else:
        if n == 0:
            ans.append(1)
        elif n == 1:
            ans.append(ans[0]+1)
        else:
            ans.append((ans[n-1]+ans[n-2])%P)
print(ans[N-1])

Solution (Python):
n, m = map(int, (input().split()))
a = {int(input()) for i 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] % 1000000007)