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):
def flog(N, M, a):
  dp = [10**4] * (N + 1)
  dp[0] = 1
  dp[1] = 1
  
  if 1 in a:
    dp[1] = 0

  for j in a:
    dp[int(j)] = 0
    
  for i in range(2, N+1):
    if dp[i] != 0:
      dp[i] = dp[i - 1] + dp[i - 2]
  return dp[N] % INF
      
if __name__ == "__main__":
  N, M = map(int, input().split())
  a = [input() for i in range(M)]
  INF = 1000000007
  print(flog(N, M, a))

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

ng = [0]*(n+1)
for i in range(m):
    ng[int(input())] = 1

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

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

print(dp[n])

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

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

for i in range(ng):
  x = int(input())
  nglist[x] = 1
 
for i in range(1,n+1):

  if nglist[i]==1:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
mod = 1000000007
brokens = set([int(input()) for i in range(M)])

dp = [0] * (N + 1)
dp[0] = 1
for now in range(N + 1):
    if now + 1 < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0
        dp[now + 2] += dp[now] if now + 2 not in brokens else 0
    elif now < N:
        dp[now + 1] += dp[now] if now + 1 not in brokens else 0

print(dp[-1] % mod)

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

Solution (Python):
def main():
    MOD = 10**9 + 7
    N, M = list(map(int, input().split(' ')))
    broken = [0 for _ in range(N + 1)]
    for _ in range(M):
        broken[int(input())] = 1
    dp = [0 for _ in range(N + 1)]
    dp[0] = 1
    for s in range(1, N + 1):
        if broken[s] == 1:
            continue
        n = dp[s - 1]
        if s - 2 >= 0:
            n += dp[s - 2]
        dp[s] += n
        dp[s] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
breakstep = [True]*(N+1)
for _ in range(M):
    breakstep[int(input())] = False

dp = [0]*(N+1)

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

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

Solution (Python):
n,m,*a = map(int,open(0).read().split())
mod = 10**9+7
s = [i-j-2 for i,j in zip(a+[n+1],[-1]+a)]
if -1 in s:
  print(0)
  exit()
f = [1,1]
for i in range(2,max(s)+1):
  f.append(f[i-1]+f[i-2])
ans = 1
for i in s:
  ans = ans*f[i]%mod
print(ans)

Solution (Python):
n,m,*a = map(int,open(0).read().split())
mod = 10**9+7
s = [i-j-2 for i,j in zip(a+[n+1],[-1]+a)]
if -1 in s:
  print(0)
  exit()
f = [1,1]
for i in range(2,max(s)+1):
  f.append(f[i-1]+f[i-2])
ans = 1
for i in s:
  ans *= f[i]
print(ans%mod)

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

dp = [0] * (n+5)
dp[0] = 1
for i in range(n):
    dp[i] %= 1000000007
    if i+1 not in a:
        dp[i+1] += dp[i]
    if i+2 not in a:
        dp[i+2] += dp[i]
print(dp[n] % 1000000007)

Solution (Python):
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
ans = 0
if N == 1:
    ans = 1
else:
    counts = [0] * (N + 1)
    if ok[1]:
        counts[1] = 1
    if ok[2]:
        counts[2] = counts[1] + 1
    for s in range(3, N + 1):
        if ok[s]:
            count = counts[s-1] + counts[s-2]
            count %= 1000000007
            counts[s] = count
    ans = counts[N]
print(ans)

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

INF=1000000007
dp=[1]*(n+1)

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

print(dp[-1]%INF)

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

Solution (Python):

n,m = map(int,input().split())
b = [True] * n
for i in range(m):
    x = int(input())
    b[x-1] = False

dp = [0] * n
if(n == 1):
    print(1)
    exit()
if(b[0]):
    dp[0] = 1
    if(b[1]):dp[1] = 2
else:
    if(b[1]):dp[1] = 1

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

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

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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m >= 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M = inputMap()
	ans = [0 for i in range(N+1)]
	ans[0] = 1
	a = []
	for i in range(M):
		tmp = inputInt()
		a.append(tmp)

	a.sort()
	for i,val in enumerate(a):
		if i == 0:
			continue
		if val == a[i-1] + 1:
			print(0)
			sys.exit()

	for i in range(N+1):
		tmp = bisect_left(a, i)
		if tmp < len(a):
			tmp = a[bisect_left(a, i)]
		else:
			tmp = -1
		
		if i+1 <= N:
			if i+1 == tmp:
				pass
			else:
				ans[i+1] = (ans[i+1] + ans[i]) % mod
		if i+2 <= N:
			if i+2 == tmp:
				pass
			else:
				ans[i+2] = (ans[i+2] + ans[i]) % mod

	print(ans[N])






def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Solution (Python):
N,m=map(int,input().split())
s= set([int(input()) for i in range(m)])
INF=1000000007

dp=[0]*(N+1)
dp[0]=1
if 1 not in s:
  dp[1]=1
else:
  dp[0]
for i in range(2,N+1):
  if i in s:
    continue
  dp[i]=dp[i-1]+dp[i-2]
  dp[i]=dp[i]%INF
  
print(dp[N])

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

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

print(dp[n]%1000000007)

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

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

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

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

if 1 not in A:
    lst[1] = 1


for i in range(2, N + 1):
    if i in A:
        lst[i] = 0
        continue

    lst[i] = lst[i - 1] % MOD + lst[i - 2] % MOD

print(lst[-1] % MOD)

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

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

print(dp[n])

Solution (Python):

n,m=map(int,input().split())

a=set()
for i in range(m):

    a.add(int(input()))

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


print(dp[n])

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

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

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

num=[0 for i in range(n+2)]
num[0]=0
num[1]=1
mod=10**9+7
for i in range(n):
    if a[i]:
        num[i+2]=(num[i+1]+num[i])%mod

print(num[n+1])

Solution (Python):
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:
        l[i] = (l[i - 1] + l[i - 2])%(10**9 + 7)

print(l[-1])

Solution (Python):
def resolve():
    MOD = 10 ** 9 + 7
    n, m = map(int, input().split())

    
    dp = [1] * (n + 1)

    for _ in range(m):
        dp[int(input())] = 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])
    
resolve()

Solution (Python):
import numpy as np
def resolve():
    MOD = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    dp = np.array([1] * (n + 1))
    dp[a] = 0

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

    print(dp[n])
    
resolve()

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

dp = [-float("inf")]*(N+1)
dp[0] = 1
dp[1] = 1

for i in a:
    dp[i] = 0

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

print(dp[N])

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

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = 0 + (1 not in a)

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

print(dp[n])

Solution (Python):
import sys
import functools
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
@functools.lru_cache(maxsize=None)
def count(p):
    if p==0 or p==1:
        return a[p]
    if a[p]==1:
        x=count(p-1)+count(p-2)
        return x
    else:
        return 0
print(count(n)%1000000007)

Solution (Python):
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
for i in range(M-1):
    if A[i+1]-A[i] == 1:
        print(0)
        exit()
L = []
k = [i for i in range(N+1)]
a = 0
for i in range(M):
    L.append(k[a:A[i]])
    a = A[i]+1
L.append(k[a:N+1])
ans = 1
B = [0,1]
for i in range(N-M):
    B.append(B[-2] + B[-1])
for i in range(len(L)):
    ans *= B[len(L[i])]
print(ans%1000000007)

Solution (Python):
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 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] %= MOD
        
print(dp[n])

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

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

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

Solution (Python):
from sys import stdin
N,M = map(int,input().split())
a = [int(stdin.readline()) for _ in range(M)]
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
A[1] = 1
for i in a:
  A[i] = -1
if A[1] == -1:
  A[1] = 0
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if A[i] == -1:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])

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

Solution (Python):
n, m = [int(x) for x in input().split()]


a = set(int(input()) for x in range(m))
_MOD = 1000000007

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

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

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

print(dp[n])

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

for a in A:
	DP[a]=-1
	
if DP[1]==-1:DP[1]=0

for i in range(n-1):
		if DP[i+2]<0:
			DP[i+2]=0
		else:
			DP[i+2]=DP[i+1]+DP[i]

print(DP[n]%1000000007)

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

a = [0]*(n+1)
for i in range(m):
    a[int(input())] = -1

dp = [0]*(n+1)

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

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

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

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

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

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

print(dp[n])

Solution (Python):
n,m=map(int,input().split())
fib=[1]
a=1
b=1
for i in range(n):
    fib.append(b)
    c=b
    b+=a
    a=c

total=1
cannot=0
s=-1
if m==0:
    total=fib[n]%(10**9+7)
else:
    for i in range(m):
        t=int(input())
        if t-s == 1:
            cannot+=1
            break
        else:
            total*=fib[t-s-2]
            total%=10**9+7
        s=t



    if n+1-t <= 1:
        cannot+=1
    else:
        total*=fib[n-t-1]
        total%=10**9+7

if cannot != 0:
    print(0)
else:
    print(total)

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

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

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

print(dp[n] % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[1]*(n+1)
for i in range(m):
    a[int(input())]=0
memo={}
def count(p):
    if p in memo:
        return memo[p]
    if p==0:
        return 1
    if p==1:
        return a[p]
    if a[p]==1:
        x=count(p-1)+count(p-2)
        memo[p]=x
        return x
    else:
        memo[p]=0
        return 0
print(count(n)%1000000007)

Solution (Python):

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)

Solution (Python):
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
    if bad_one==1 and len(b) != 0:
        bad_one=b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

Solution (Python):
from collections import deque

n,m = map(int,input().split())
step = [i for i in range(2, n+1)]
broken = []
for i in range(m):
    broken += [int(input())]

mod = pow(10,9) + 7 
dp = [0 for _ in range(n+1)]
dp[0] = 1

if m == 0:
    dp[1] = 1
    for i in step:
        dp[i] = dp[i-1] + dp[i-2]
else:
    b = deque(broken)
    if not broken[0] == 1:
        dp[1] = 1
    elif len(b) > 1:
        b.popleft()
    if len(broken) != 0:
        bad_one = b.popleft()
    for i in step:
        if i != bad_one:
            dp[i] = (dp[i-1]+dp[i-2]) % mod
        elif i == bad_one and len(b) != 0:
            bad_one = b.popleft()
print(dp[n] % mod)

Solution (Python):





N, M = map(int, input().split())
arr = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0, N+1)]
for x in arr:
    stairs[x] = False

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

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2, N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)

Solution (Python):
N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0,N+1)]
for x in arr:
    stairs[x] = False

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

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7


def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for _ in range(M)])
    
    if N == 1:
        print(1)
        return
    
    prepre = 1
    pre = 1
    if A and A[0] == 1:
        pre = 0
        A.popleft()

    for i in range(2, N + 1):
        if A and A[0] == i:
            pre, prepre = 0, pre
            A.popleft()
        else:
            pre, prepre = (pre + prepre) % mod, pre
        
    print(pre)



if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1


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


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


def MI1(): return map(int1, input().split())


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


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n - 1, memo) + Fibo(n - 2, memo)
        return memo[n]


def solve():
    n, m = MI()

    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            keiro = 0
        else:
            keiro = Fibo(d + 2)
        
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1


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


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


def MI1(): return map(int1, input().split())


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


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def Fibo(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fibo(n - 1, memo) + Fibo(n - 2, memo)
        return memo[n]


def solve():
    M = list(MI())
    if len(M) == 2:
        n, m = M
    else:
        n = M[0]
        m = 0

    s = 0
    mod = 1000000007
    ans = 1
    for _ in range(m):
        t = II() - 1
        d = t - s
        if d < 0:
            keiro = 0
        else:
            keiro = Fibo(d + 2)
        
        ans = ans * keiro % mod
        s = t + 2
    d = n - s
    if d < 0:
        keiro = 0
    else:
        keiro = Fibo(d + 2)

    ans = ans * keiro % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
 
sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7
 
 
def input():
    return sys.stdin.readline().strip()
 
 
def main():
    N, M = map(int, input().split())
    dp = [0] * (N + 1)
    safe = [True] * (N + 1)
    for _ in range(M):
        a = int(input())
        safe[a] = False
 
    dp[0] = 1
    for i in range(1, N + 1):
        if i == 1 and safe[i]:
            dp[i] = dp[i - 1]
        else:
            if safe[i]:
                dp[i] = dp[i - 1] + dp[i - 2]
                dp[i] %= MOD
 
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()

Solution (Python):
N, M = list(map(int, input().split()))
A = {i: 0 for i in range(N+1)}
mod = 10 ** 9 + 7
for _ in range(M):
    A[int(input())] = 1
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
 
for i in range(N+1):
    if A.get(i+1) == 0:
        dp[i + 1] += dp[i]
    if A.get(i+2) == 0:
        dp[i + 2] += dp[i]
 
print(dp[N]%mod)

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

print(dp[n])

Solution (Python):
n, m=map(int, input().split())
a=[int(input()) for i in range(m)]
mod=10**9 +7
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:
        dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%mod)

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

a=set(a)
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):
import sys
N, M = map(int, sys.stdin.readline().split())
a = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

if M > 0:
    j = 0
    for i in range(N):
        if i == 0:
            if a[j] == 1:
                list[i] = 0
            else:
                list[i] = 1
        elif i == 1:
            if a[j] == 2:
                list[i] = 0
            elif a[0] == 1:
                list[i] = 1
            else:
                list[i] = 2
        else:
            if a[j] == i + 1:
                list[i] = 0
            else:
                list[i] = (list[i - 1] + list[i - 2]) % MOD
        if i + 1 == a[j] and j < M - 1:
            j += 1

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    dp = [0] * (N + 1)
    safe = [True] * (N + 1)
    for _ in range(M):
        a = int(input())
        safe[a] = False

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

    print(dp[-1])


if __name__ == "__main__":
    main()

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

for i in a:
    b[i] = 0

for i in range(2, n + 1):
    if b[i] != 0:
        b[i] = (b[i - 2] + b[i - 1])%(10**9 + 7)

print(b[-1])

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

for i in a:
    b[i] = 0

for i in range(2, n + 1):
    if b[i] != 0:
        b[i] = b[i - 2] + b[i - 1]

print(b[-1]%(10**9 + 7))

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


dp=[1] * (n +1)

for i in range(m):
    a= int(input())
    dp[a] = 0

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

    dp[i] = (dp[i+1] + dp[i+2]) %p

print(dp[0])

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

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

b = [1]*(n + 1)

for i in a:
    b[i] = 0

for i in range(2, n + 1):
    if b[i] != 0:
        b[i] = (b[i - 2] + b[i - 1])%(10**9 + 7)

print(b[-1])

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, m = mi()
    L = [ii() for _ in range(m)]

    FIBO = [0] * (n+1)    
    for i in range(n+1):
        if i == 0 or i == 1:
            FIBO[i] = 1
        else:
            FIBO[i] = (FIBO[i-1] + FIBO[i-2]) % mod

    prev = 0
    ans = 1
    for broken_step in L:
        if prev == broken_step:
            print(0)
            exit()
        ans = (ans * FIBO[broken_step - 1 - prev]) % mod
        prev = broken_step + 1
    ans = (ans * FIBO[n - prev]) % mod
    print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
mod = 10**9+7
n,m = map(int,input().split())
a = set()
for i in range(m):
  a.add(int(input()))
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):
n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1
for j in l:
  memo[j]=0
  
for i in range(2,n+1):
  if memo[i]==0:
    continue
  else:
    memo[i]=((memo[i-1]%q)+(memo[i-2]%q))%q
print(memo[-1]%q)

Solution (Python):
n,m=list(map(int,input().split(" ")))
a=[]
dp=[float("inf") for i in range(n+1)]
for i in range(m):
  a=int(input())
  dp[a]=0
dp[0]=1
if dp[1] != 0:
  dp[1]=1
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 = [int(x) for x in input().split()]
a_list = [0] * m
for i in range(m):
    a_list[i] = int(input())

mod = 1000000007

temp_list = [0] * (n + 1)
temp_list[0] = 1
temp_list[1] = 1
j = 0
if j < m and a_list[0] == 1:
    temp_list[1] = 0
    j = 1

for i in range(2, n + 1):
    if j < m and i == a_list[j]:
        j += 1
        continue
    temp_list[i] = (temp_list[i - 2] + temp_list[i - 1]) % mod
print(temp_list[n])