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())
a = [int(input()) for _ in range(M)]

MOD = 1000000007

d = [0] * (N+1)
OK = [True]*(N+1)
d[0] = 1

for i in range(M):
    OK[a[i]] = False



if(OK[1]):
    d[1] = 1
else:
    d[1] = 0

for i in range(2,N+1):
    if(OK[i-1]):
        d[i] += d[i-1]
    if(OK[i-2]):
        d[i] += d[i-2]
    d[i] %= MOD
    '''
    if(i in a):
        d[i] = 0
    else:
        d[i] = d[i-1] + d[i-2]
    d[i] %= MOD
    '''

print(d[-1])

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
NG=[False]*n
for i in range(m):
    NG[a[i]-1]=True

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

"""

"""

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*(N+1)
    dp[0] = 1
    B = set(a)
    for i in range(1, N+1):
        if i in B:
            continue
        if i > 1:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
        else:
            dp[i] = dp[i-1] % MOD
    print(dp[N])
    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=[]
for i in range(M):
    a=int(input())
    A.append(a)
DP=[0]*(1+N)
DP[0]=1
DP[1]=1
damage=[0]*(N+1)
kotae=0
for m in A:
    damage[m]=-1
if N==1:
    print(1)
elif N==2:
    if M==1:
        print(1)
    else:
        print(2)
else:
    for a in range(2,N+1):
        if damage[a-1]==-1 and damage[a-2]==-1:
            print(0)
            kotae+=1
            break
        if damage[a]==-1:
            continue
        elif damage[a-1]==-1:
            DP[a]=DP[a-2]
        elif damage[a-2]==-1:
            DP[a]=DP[a-1]
        else:
            DP[a]=DP[a-2]+DP[a-1]
    if kotae==0:
        print(DP[-1]%(pow(10,9)+7))

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
NG=[False]*n
for i in range(m):
    NG[a[i]-1]=True

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

Solution (Python):
n,m = map(int,input().split())
stairs = [True for _ in range(n+1)]
broken_stairs = [int(input()) for i in range(m)]
mod = 10**9+7

for i in broken_stairs:
    stairs[i] = False

dp = [0]*(n+1)

if stairs[1]:
    dp[1] = 1
    
if stairs[0]:
    dp[0] = 1


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

print(dp[-1])

Solution (Python):
n,m = map(int,input().split())
dp = [0 for i in range(n+1)]
is_Broken = [False for i in range(n+1)]
dp[0] = 1

for i in range(m):
    buf = int(input())
    is_Broken[buf] = True

for i in range(1,n+1):
    if is_Broken[i] == True:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        tmp = dp[i-1] + dp[i-2]
        dp[i] = tmp%(10**9+7)

print(dp[n])

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

dp = [0]*(n+1)
if m == 0:
  base = [n+1]

if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))

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

dp = [0]*(n+1)
if m == 0:
  base = [n+1]

if 1 == base[j]:
  dp[1] = 0
  if j < m-1:
    j = j + 1
else:
  dp[1] = 1

dp[0] = 1

for i in range(2,n+1):
  if not (i == base[j]):
    dp[i] = dp[i-1] + dp[i-2]
  elif i == base[j]:
    if j < m-1:
      j = j + 1
  
  
print(int(dp[n]%1000000007))

Solution (Python):












n,m = map(int,input().split())
stair = [True for _ in range(n+1)]
for _ in range(m):
    broken = int(input())
    stair[broken] = False

mod = 1000000007

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

dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if stair[next]:
            dp[next] += dp[now]
            dp[next] %= mod

print(dp[n])

Solution (Python):
import sys
N,M = map(int,input().split())
intact = [True for _ in range(N)]
dp = [0 for _ in range(N+1)]
MOD = 1000000007
for i in range(M):
  a = int(input())
  intact[a] = False
if N == 1:
  print(1)
  sys.exit(0)
dp[0] = 1
if (intact[1]):
  dp[1] = 1
for i in range(2,N+1):
  if intact[i-2]:
    dp[i] += dp[i-2]
  if intact[i-1]:
    dp[i] += dp[i-1]
  dp[i] %= MOD
print(dp[N])

Solution (Python):
import sys
import os

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = list(map(int, sys.stdin.buffer.readline().split()))
    A = set([int(sys.stdin.buffer.readline().rstrip()) for _ in range(M)])

    ret = [0, 1]
    for i in range(1, N + 1):
        if i in A:
            ret.append(0)
        else:
            ret.append((ret[-1] + ret[-2]) % MOD)

    print(ret[-1] % MOD)


if __name__ == '__main__':
    main()

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

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

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

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

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

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

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

Solution (Python):
import bisect
N, M = map(int, input().split())
A = [0]*M
for i in range(M):
  A[i] = int(input())

def index(a, x):
  i = bisect.bisect_left(a, x)
  if i != len(a) and a[i] == x:
    return i
  else:
    return -1

def dp(a,n):
  if n==N:
    return 1
  if n>N:
    return 0
  if index(a,n)!=-1:
    return 0
  else:
    return (DP[n+1]+DP[n+2])%(10**9+7)
    
DP=[0]*(N+3)

for i in range(N+2,-1,-1):
  DP[i]=dp(A,i)

ans=DP[0]
print(ans)

Solution (Python):
import bisect
N, M = map(int, input().split())
A = [0]*M
for i in range(M):
  A[i] = int(input())

def index(a, x):
  i = bisect.bisect_left(a, x)
  if i != len(a) and a[i] == x:
    return i
  else:
    return -1

def dp(a,n):
  if n==N:
    return 1
  if n>N:
    return 0
  if index(a,n)!=-1:
    return 0
  else:
    return (DP[n+1]+DP[n+2])%(10**9+7)
    
DP=[0]*(N+3)

for i in range(N+2,-1,-1):
  DP[i]=dp(A,i)

ans=DP[0]
print(ans)

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[:2]= 1, 1 if 1 not in A else 0 
for i in range(2, N+1):
    if i not in A: 
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

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[:2]= 1, 1 if 1 not in A else 0
for i in range(2, N+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[-1])

Solution (Python):
MOD = 10 ** 9 + 7

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    if N == 1 and M == 0:
        return 1
    elif N == 1 and M == 1 and A[0] == 0:
        return 0

    l = [1 for _ in range(N+1)]
    for a in A:
        l[a] = 0
        
    dp = [0 for i in range(N+1)]
    dp[1] = 0 if 1 in A else 1
    dp[2] = 0 if 2 in A else dp[1] + 1

    for i in range(3, N+1):
        if l[i] == 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD

    return dp[N] % MOD

print(solve())

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
broken = set(int(input()) for _ in range(M))

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

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

print(dp[-1])

Solution (Python):
from collections import deque
N, M = map(int, input().split())
broken = [int(input())-1 for i in range(M)] 
broken = set(broken)

if N == 1:
  print(1)
  exit()

if 0 in broken:
    if 1 in broken:
        stairs=deque([0,0])
    else:
        stairs=deque([0,1])
else:
    if 1 in broken:
        stairs=deque([1,0])
    else:
        stairs=deque([1,2])

for i in range(2,N):
    if i in broken:
        stairs.append(0)
    else:
        stairs.append((stairs[i-1]+stairs[i-2])%(10**9 + 7))
print(stairs[-1])

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

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

Solution (Python):








def resolve():

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


    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])%(10**9+7)*dp[i]

    print(dp[N])

resolve()

Solution (Python):
import sys


n, m = [int(_) for _ in input().split()]
l = {}
for i in range(m):
    l[int(input())] = 1

d = [0] * (n + 2)
d[0] = 1
if 1 not in l:
    d[1] = 1
for i in range(n):
    if i in l and i + 1 in l:
        print(0)
        sys.exit()
    elif i in l:
        d[i + 2] = d[i + 1]
    elif i + 1 in l:
        d[i + 2] = d[i]
    else:
        d[i + 2] = d[i] + d[i + 1]
    d[i + 2] = d[i + 2] % (10 ** 9 + 7)
print(d[-2])

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

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

Solution (Python):
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
a.append(-1)

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

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

N, M = map(int, input().split())
a = [0]*M
mod = 10**9+7

for i in range(M):
    a[i] = int(input())

a = set(a)
DP = [0]*(N+1)
DP[0] = 1
if 1 in a:
    DP[1] = 0
else:
    DP[1] = 1

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

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

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

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


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

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

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

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
s = set([inp() for i in range(m)])
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if i+1 in s:
        dp[i+1] = 0
        continue
    if i == 0:
        dp[i+1] += dp[i]
    else:
        dp[i+1] += dp[i] + dp[i-1]
        dp[i+1] %= mod
print(dp[-1])

Solution (Python):
MOD = 10**9 + 7
N, M = map(int, input().split())
broken = [False] * (N+1)
for i in range(M):
    a = int(input())
    broken[a] = True
dp = [0] * (10 ** 5 + 10)
dp[0] = 1
for i in range(N):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    dp[i + 1] += dp[i]
    dp[i + 2] += dp[i]
print(dp[N] % MOD)

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

print(dp[N] % MOD)

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

for x in a:
    dp[x] = 0

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

print(dp[n])

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

for x in a:
    dp[x] = 0

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


print(dp[n] if dp[n] != INF else 0)

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

dp[0] = dp[1] = 1

for x in a:
    dp[x] = 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] if dp[n] != INF else 0)

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

dp[0] = dp[1] = 1

if 0 in a:
    dp[0] = INF
if 1 in a:
    dp[1] = INF

for x in a:
    dp[x] = 0

for i in range(2, n+1):
    if dp[i] == 0:
        continue

    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = min(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)

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

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

for now in range(n):
    for next in range(now + 1, min(n + 1, now + 3)):
        if a[next]:
            dp[next] += dp[now]
            dp[next] %= 1000000007

print(dp[n])

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

dp[0] = dp[1] = 1

if 0 in a:
    dp[0] = INF
if 1 in a:
    dp[1] = INF

for x in a:
    dp[x] = 0

for i in range(2, n+1):
    if dp[i] == 0:
        continue

    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = max(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)

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

for i in range(m):
	p_ok[int(input())] = False

p[0] = 1
for now in range(0,n):
	for next in range(now+1,min(n,now+2)+1):
		if p_ok[next]:
			p[next] += p[now]
			p[next] %= mod


ans = p[n]
print(ans%mod)

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


a = set([int(input()) for _ in range(M)])

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

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
ok_step = [True for i in range(n + 1)]
dp = [0 for i in range(n + 1)]

for i in range(m):
    broken = int(input())
    ok_step[broken] = False

dp[0] = 1
for now in range(n):
    for next in range(now + 1, min(n, now + 2) + 1):
        if ok_step[next]:
            dp[next] += dp[now]
            dp[next] %= 10**9 + 7
print(dp[n])

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

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

is_broken = [False for _ in range(N + 1)]
for _ in range(M):
    a = int(input())
    is_broken[a] = True

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

for i in range(1, N + 1):
    if is_broken[i]:
        continue
    if i == 1:
        dp[i] += dp[i - 1]
    else:
        dp[i] += dp[i - 1] + dp[i - 2]

    dp[i] = dp[i] % MOD

print(dp[N])

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

if m == 0:
  l = [-1]
else:
  l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

for i in range(n):
  if i == l[skip]:
    res[0] = res[1]
    res[1] = 0
    if skip < m-1:
      skip += 1
  else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

Solution (Python):
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
  for i in range(n):
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

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

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

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math

import itertools



import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default







def main():
    n,m=map(int,input().split())
    broken=set(int(input()) for _ in range(m))
    dp=[0]*(n+5)
    dp[0]=1
    dp[1]=1
    ans=0
    for i in range(2,n+1):
        if i-1 not in broken:
            dp[i]+=dp[i-1]%MOD
        if i-2 not in broken:
            dp[i]+=dp[i-2]%MOD
    if n==1:
        print(1)
    else:
        print(dp[n]%MOD)

if __name__ == "__main__":

    main()

Solution (Python):
n, m = map(int, input().split())
a = [int(input())-1 for i in range(m)]
mod = 1000000007

dp = [0 for i in range(n+1)]
for i in a:
  dp[i+1] = -1

dp[0] = 1
for i in range(n):
  if dp[i+1] >= 0:
    dp[i+1] = (dp[i] + dp[i-1])%mod
  else:
    dp[i+1] = 0
print(dp[len(dp)-1])

Solution (Python):
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-2]+dp[i-1])%1000000007
    if i in a:
        dp[i]=0
print(dp[n])

Solution (Python):
N, M = map(int, input().split())
broken_step = [0] * (N + 1)
for _ in range(M):
    n = int(input())
    broken_step[n] = 1

dp = [1] * (N + 1)
dp[1] = 0 if broken_step[1] == 1 else dp[0]

for i in range(2, N + 1):
    if broken_step[i] == 1:
        dp[i] = 0
    else:
        dp[i] = dp[i -1] + dp[i - 2]

print(dp[-1] % 1000000007)

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

Solution (Python):
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[n]%1000000007)

Solution (Python):
N,M=map(int,input().split())
dp=[1]*(N+1)
for _ in range(M):
    a=int(input())
    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))

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

Solution (Python):
import collections
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = collections.deque([])
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]

if len(a) > 0:
    if 1 != a[0]:
        dp.append(1)
    else:
        dp.append(0)
        a.popleft()
else:
    dp.append(1)

for i in range(2, N + 1):
    if len(a) > 0:
        if i != a[0]:
            tmp = dp[0] + dp[1]
        else:
            tmp = 0
            a.popleft()
    else:
        tmp = dp[0] + dp[1]
    dp[0] = dp[1]
    dp[1] = tmp

print(dp[-1] % mod)

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

Solution (Python):

N, M = [int(s) for s in input().split()]
b = [0]*N
for _ in range(M):
    b[int(input().strip())-1] = 1

a = [0]*N

if b[0] == 0:
    a[0] = 1
if N > 1 and b[1] == 0:
    a[1] = 1 + a[0]

for i in range(2, N):
    if b[i] == 0:
        a[i] = a[i-1] + a[i-2]
print(a[-1]%1000000007)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()            
A = [INT() for i in range(M)]

dp = [INF] * (N + 1)
dp[0] = 1
dp[1] = 1
for a in A:
    dp[a] = 0

for i in range(1, N+1):
    if dp[i] == 0:
        continue
    if i-2 >= 0:
        dp[i] = min(dp[i], dp[i-1] + dp[i-2])
    elif i - 1 >= 0:
        dp[i] = min(dp[i], dp[i-1])

print(dp[N] % mod)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
break_step = [INT() for _ in range(M)] + [0]

comb = [0]*(N + 1)
comb[0] = 1

index = 0
for i in range(1, N + 1):
	if break_step[index] == i:
		comb[i] = 0
		index += 1
	else:
		if i == 1:
			comb[i] = 1
		else:
			comb[i] = comb[i - 2] + comb[i - 1]

print(comb[N]%mod)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians

from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = [INT() for i in range(M)]

    dp = [1] * (N + 1)
    for a in A:
        dp[a] = 0

    for i in range(N-1):
        dp[i+2] = dp[i+2] * (dp[i] + dp[i+1]) % mod
     
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

for i in range(M-1):
    if A[i+1] - A[i] == 1:
        print(0)
        exit()

d = [1] * (N+1)
for i in range(len(A)):
    d[A[i]] = 0

for i in range(2, N+1):
    if d[i] != 0:
        d[i] = (d[i-1] + d[i-2]) % (mod)
print(d[N])

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