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
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])%mod
 
print(dp[n])

Solution (Python):


n, m = map(int, input().split())
z = 10**9 + 7

ans = [1]
if m != 0:
    a_i = int(input())
else:
    a_i = 0
m_count = 1
if a_i == 1:
    ans.append(0)
    if m_count < m:
        a_i = int(input())
        m_count += 1
else:
    ans.append(1)
        
for i in range(2, n+1):
    if a_i == i:
        ans.append(0)
        if m_count < m:
            a_i = int(input())
            m_count += 1
    else:
        ans.append(ans[i-1]+ans[i-2])
        

print(int(ans[-1]%z))

Solution (Python):


n, m = map(int, input().split())
mod = 10**9 + 7
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])%mod

print(dp[n])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]*(n+2)
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]*(n+2)
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

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

ban = [False]* (n+1)

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

li = []
for mi in range(m):
    i = int(input())
    ban[i] = True

for i in range(n):
    if ban[i]:
        dp[i]=0
        continue
    if i+1 <n+1:
        dp[i+1] += dp[i]
    if i+2 <n+1:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))

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

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

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

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) 

for i in range(1,N+1):
  if i in A:
    continue
  x = dp[i-1]
  if i > 1:
    x += dp[i-2]
  dp[i] = x%MOD

answer = dp[N]
print(answer)

Solution (Python):

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 1000000007
dp = [1]*(N+1)
for i in a:
    dp[i] = False

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

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
A = {i:0 for i in range(N+1)}
for _ in range(M):
  A[int(input())] = 1

mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  if A[i+1] != 1: 
    dp[i+1] += dp[i]
    dp[i+1] %= mod
  if i+2 >= N+1:
    continue
  if A[i+2] != 1:
    dp[i+2] += dp[i]
    dp[i+2] %= mod

print(dp[N])

Solution (Python):
def main():
    n,m=map(int,input().split())
    res=[1,1]
    flg=0
    mod=10**9+7
    a=n
    gap=[]
    if m!=0:
        a=int(input())
        gap.append(a-1)
        for i in range(m-1):
            b=int(input())
            dif=b-a-1
            if dif==0:
                flg=1
                break
            else:
                gap.append(dif-1)
                a=b
        gap.append(n-a-1)
    else:
        gap.append(n)
    if flg==1:
        print(0)
    else:
        for i in range(2,max(gap)+1):
            res.append((res[i-1]+res[i-2])%mod)
        ans=1
        for i in gap:
            ans=(ans*res[i])%mod
        print(ans)
if __name__=="__main__":
    main()

Solution (Python):
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
        z = [[0, 0], [0, 0]]
        for (i, j, k) in product(range(2), range(2), range(2)):
                z[i][j] += X[i][k] * Y[k][j]
        return z

def mat2_pow(X, n):
        if n == 0:
                return [[1, 0], [0, 1]]
        elif n % 2:
                return mat2_mul(X, mat2_pow(X, n - 1))
        else:
                half_pow = mat2_pow(X, n / 2)
                return mat2_mul(half_pow, half_pow)

def fib(n):
        if n == 0:
                return 0
        else:
                f = [[0, 1], [1, 1]]
        return mat2_pow(f, n - 1)[1][1]


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

for k in a:
        ans *= fib(k - start)
        ans %= INF
        start = k + 1

ans *= fib(N - start + 1)
print(ans % INF)

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):
import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = {i: False for i in range(N+1)}
for m in range(M):
    a = ir()
    A[a] = True
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if A[i]:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)

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

cnt = 0
dp_table = [0 for i in range(n + 10)]
dp_table[0] = 1
dp_table[1] = 1

for i in range(m):
    dp_table[a[i]] = -10 ** 9 + 7

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

print(dp_table[n])

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

ban = [False] * (n + 1)

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

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

print(dp[n] % MOD)

Solution (Python):
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

if len(a) != 0:
    base = a.popleft()
else:
    base = -1

p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
def fb(num):
    a,b = 1,0
    for _ in range(num+1):
        a,b = a+b,a
    return b
if m==0:
    print(fb(n)%(10**9+7))
    exit()
if m>1:
    for i in range(m-1):
        if a[i+1]-a[i]==1:
            print(0)
            exit()
c=0
for i in range(m):
    if i==0 and a[0]==1:
        c+=1
    elif i==0:
        c+=fb(a[0]-1)
    else:
        c*=(fb(a[i]-a[i-1]-2)%(10**9+7))
c*=fb(n-a[-1]-1)%(10**9+7)
print(c%(10**9+7))

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

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

dp = [0] * (N+3)
dp[0] = 1
for i in range(N):
    if i in setA: continue
    dp[i] %= MOD
    dp[i+1] += dp[i]
    dp[i+2] += dp[i]

ans = dp[N] % MOD
print(ans)

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

c=[0]*(n+1)
c[0]=1
if 1 in a:
    c[1]=0
else:
    c[1]=1

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

print(c[n])

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

Solution (Python):
p = 1000000007
n, m = (int(x) for x in input().split())
seq = [1 for i in range(n+1)]
for i in range(m):
    a = int(input())
    seq[a] = 0
ans = 1
for i in range(2,n+1):
    if seq[i] == 0:
        continue
    seq[i] = (seq[i-1] + seq[i-2]) % p
print(seq[-1])

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, groupby
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

def Fibo(n):
	S = [1, 1]
	if n == 1:
		return 1
	for i in range(1, n):
		S.append(S[i] + S[i-1])

	return S[n]

if M == 0:
	print(Fibo(N)%mod)
	exit()

a = [INT()]
for i in range(1, M):
	a.append(INT())
	if a[i] == a[i-1]+1:
		print(0)
		exit()
m = [a[0]-1]
for i in range(1, M):
	m.append(a[i]-a[i-1]-2)
m.append(N-a[M-1]-1)



ans = 1
for n in m:
	ans *= Fibo(n)

print(ans%mod)

Solution (Python):
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
fib = [1,1,2]
for i in range(3,n+1):
    fib.append((fib[i-2]+fib[i-1])%mod)
if (m==0):
    print(fib[n])
    exit()
ans = 0
ans += fib[a[0]-1]

for i in range(1,m):
    if (a[i]-a[i-1]!=1):
        ans *= fib[a[i]-a[i-1]-2]
        ans %= mod
    else:
        print(0)
        exit()
ans *= fib[n-a[m-1]-1]
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p=10**9+7
n, m = map(int, input().split())
a = list(int(input()) for i in range(m))

safe = [1]*(n+1)
for aa in a:
    safe[aa]=0

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

if safe[1]:dp[1]=1

for i in range(2,n+1):
    if not safe[i]:
        continue

    dp[i] = dp[i-1]%p+dp[i-2]%p

print(dp[-1]%p)

Solution (Python):
import numpy as np

MOD = 10**9+7

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

An = np.zeros(N+1,dtype=int)
An[0] = 1

for _ in range(M):
    m = int(input())
    An[m] = -1


if An[1] == -1:
    An[1] = 0
else:
    An[1] = 1

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

    An[i] = (An[i-1] + An[i-2]) % MOD

print(An[N])

Solution (Python):
n,m=map(int,input().split())
dp=[1]*n

mod=10**9+7
for i in range(m):
  a=int(input())
  dp[a-1]=0

ans=[]
ans.append(1 if dp[0]==1 else 0)
if len(dp)>1 and dp[0]==1 and dp[1]==1:
    ans.append(2)
elif len(dp)>1 and dp[0]==1 and dp[1]==0:
    ans.append(0)
elif len(dp)>1 and dp[0]==0 and dp[1]==1:
    ans.append(1)
elif len(dp)>1 and dp[0]==0 and dp[1]==0:
    print(0)
    exit()
for i in range(2,n):
    ans.append((ans[i-1]+ans[i-2])*dp[i]%mod)
print(ans[-1]%mod)

Solution (Python):
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
ans=1
a.sort()
d={0:1,1:1,2:2,3:3,4:5,5:8,6:13,99500:49759705584609,99501:49760296517401}
def func(n):
    if n in d:
        return d[n]
    else:
        v = (func(n-1)+func(n-2))%(10**9+7)
        d[n]=v
        return v
ps=-1
a.append(n+1)
for ai in a:
    c=ai-ps-2
    ps=ai
    if c<0:
        print(0)
        exit()
    c=func(c)
    ans*=c
    ans%=10**9+7

print(ans%(10**9+7))

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

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

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

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

dp = []
for dpi in range(n):
    dp.append(0)

k = 0
a.append(0)
for j in range(n):
    if j+1 == a[k]:
        k += 1
        continue
    if j == 0:
        dp[j] = 1
    elif j == 1:
        dp[j] = dp[j-1] + 1
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n-1] % 1000000007)

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

dp = [0] * (n+1)

dp[:2] = 1, 1 if 1 not in a else 0 

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

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

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

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

n, m = map(int, input().split())
wlist = [int(input()) for _ in range(m)]

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

start = 0
ans = 1
for w in wlist:
  end = w - 1
  if end - start > 0:
    ans *= dp[w - 1 - start]
  elif end -start == 0:
    pass
  else :
    ans = 0
    break
  ans %= MOD
  start = w + 1
if not start == n:
  ans *= dp[n - start]
  ans %= MOD
print(ans)

Solution (Python):
N, M = tuple(map(int, input().split()))
A = set(map(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 in A:
        continue
    else:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[-1] % MOD)

Solution (Python):
def resolve():
	modu = 1000000007
	n, m = map(int, input().split())
	a = [False]*n
	for _ in range(m):
		a[int(input())] = True
	dp = [0]*(n+1)
	dp[0], dp[1] = 1, 1
	for i in range(2, n+1):
		if i < n and a[i]:
			continue
		multi = []
		if not a[i-1]:
			multi.append(dp[i-1])
		if not a[i-2]:
			multi.append(dp[i-2])
		dp[i] = sum(multi) % modu
	print(dp[-1])
resolve()

Solution (Python):
n,m=map(int, input().split())
a=list()
for i in range(m):
    a.append(int(input()))

mod=1e9+7

inf=float('inf')

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

for i in a:
    dp[i]=0

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

print(int(dp[-1]))

Solution (Python):
N,M=map(int,input().split())
mod=10**9+7
a=[int(input()) for _ 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])%mod*dp[i]
print(dp[-1])

Solution (Python):

import io

nim,mike = map(int,input().split())

sets={int(input()) for _ in range(mike)}

modulous=10**9+7

array=[0]*(nim+1)
array[0]=1
array[1]=1
if 1 in sets:
  array[1]=0

for i in range(2,nim+1):
  if i in sets:
    continue
  array[i]=(array[i-1]+array[i-2])%modulous
print(array[nim])

Solution (Python):
MOD = 1000000007
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
is_broken = [False for _ in range(N+1)]
for a in A:
  is_broken[a] = True




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


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

print(dp[N])

Solution (Python):
MOD = 1000000007
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
is_broken = [False for _ in range(N+1)]
for a in A:
  is_broken[a] = True




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


for i in range(N):
  if not is_broken[i+1]:
    dp[i+1] += dp[i]
    dp[i+1] %= MOD
  if i+2 <= N:
    if not is_broken[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)]
MOD = int(1e9) + 7

tf = [True for _ in range(N)]
for i in a:
    tf[i-1] = False

if N <= 2:
    if N == 1:
        if tf[0]:
            print(1)
        else:
            print(0)
    else:
        if tf[0] and tf[1]:
            print(2)
        elif tf[0] or tf[1]:
            print(1)
        else:
            print(0)
    exit()



dp = []
if tf[0]:
    dp.append(1)
else:
    dp.append(0)
if tf[1]:
    dp.append(dp[0] + 1)
else:
    dp.append(0)
for i in range(N):
    if i == 0 or i == 1:
        continue
    else:
        if tf[i]:
            dp.append((dp[i-1] + dp[i-2])%MOD)
        else:
            dp.append(0)
print(dp[N-1])

Solution (Python):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = int(1e9) + 7

tf = [True for _ in range(N)]
for i in a:
    tf[i-1] = False

if N <= 2:
    if N == 1:
        if tf[0]:
            print(1)
        else:
            print(0)
    else:
        if tf[0] and tf[1]:
            print(2)
        elif tf[0] or tf[1]:
            print(1)
        else:
            print(0)
    exit()



dp = []
if tf[0]:
    dp.append(1)
else:
    dp.append(0)
if tf[1]:
    dp.append(dp[0] + 1)
else:
    dp.append(0)
for i in range(N):
    if i == 0 or i == 1:
        continue
    else:
        if tf[i]:
            dp.append((dp[i-1] + dp[i-2])%MOD)
        else:
            dp.append(0)
print(dp[N-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
for a in A:
    dp[a] = -1
for i in range(n):
    if dp[i] == -1:
        continue
    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] % mod)

Solution (Python):

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



mod_9 = 10**9 +7
dp =[0]*(N +1)
dp[0] = 1
if 1 not in A:
    dp[1] =1
for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = dp[i+1] + dp[i] 
        dp[i+2] %= mod_9
kotae =dp[N] 
print(kotae )

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

broken = [False] * (N + 1)
for i in range(M):
    broken[int(input())] = True
dp = [0] * (N + 2)
mod = 1000000007
dp[N] = 1
for i in range(N-1,-1,-1):
    if broken[i]:
        dp[i] == 0
        continue
    dp[i] = (dp[i+1]+ dp[i+2]) % mod
    
print(dp[0])

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

mod = 1000000007

DP = [-1] * (N + 1) 
DP[0] = 1 
DP[1] = 1 

def fib(n):
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    
    return DP[n]

ans = 1
x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod
    
print(ans)

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

oks = [True for i in range(N+1)]
for i in range(M):
    x = int(input())
    a.append(x)
    oks[x] = False

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

now = 0
while now < N:
    next = now+1
    while next <= min([N, now+2]):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 1000000007 
        next += 1
    now += 1

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 a:
    dp[i] = 0

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

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

n, m, *broken = map(int, sys.stdin.read().split())
broken = set(broken)

def main():
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = int(not 1 in broken)
    for i in range(2, n + 1):
        ways[i] = (not i in broken) * (ways[i-1] + ways[i-2]) % MOD
    print(ways[n])

if __name__ ==  '__main__':
    main()

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

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

is_ok = [True] * (N+1)
for a in A:
  is_ok[a] = False

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

print(dp[N])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, *A = map(int, read().split())
 
MOD = 10**9 + 7
 
dp = [0] * (N + 10)
dp[0] = 1
is_broken = [False] * (N + 1)
 
for x in A:
    is_broken[x] = True
 
for n in range(1, N + 1):
    if is_broken[n]:
        continue
    x = dp[n - 1] + dp[n - 2]
    if x >= MOD:
        x -= MOD
    dp[n] = x
 
answer = dp[N]
print(answer)

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

a = [int(input())-1 for _ in range(M)]
T = 1
for i in range(M-1):
    if a[i]+1 == a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N == 1:
        if M==0:
            print(1)
        else:
            print(0)
    else:
        L = [0 for _ in range(N)]
        for i in range(M):
            L[a[i]] = -1
        if L[0] == -1:
            L[1] = 1
        else:
            L[0] = 1
            if L[1] != -1:
                L[1] = 2
        for i in range(2,N):
            if L[i] != -1:
                if L[i-2] == -1:
                    L[i] = L[i-1]%1000000007
                elif L[i-1] == -1:
                    L[i] = L[i-2]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
        print(L[-1])

Solution (Python):

NM = input().split()
N,M = int(NM[0]), int(NM[1])
A = set([int(input()) for _ in range(M)])
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
MOD = 1000000007
    
if(1 in A):
    dp[1] = 0

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

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



div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1
else:
    del a[0]

def stairs():
    for i in range(N-1):
        if dp[i+1] == 0 and dp[i] == 0:
            break
        if a:
            if i+2 == a[0]:
                del a[0]
                continue
        dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

Solution (Python):
fib = [1,1,1,2]
def fibonacci(n):
    if n<len(fib):
        return fib[n]
    x = len(fib)
    a = fib[len(fib)-2]
    b = fib[len(fib)-1]
    while x<=n:
        c = b
        b = a+b
        a = c
        x+=1
    return b

h = input().split(" ")
n = int(h[0])
a = []
for i in range(n+1):
    a.append(1)

m = int(h[1])
for i in range(m):
    an = int(input())
    a[an]=0

prod=1
ck = 0
sum = 0

for i in range(n+1):
    if a[i]==0:
        if ck==1:
            prod =0
            break
        prod*=fibonacci(sum)
        sum=0
        ck=1
    else:
        sum+=1
        ck=0
prod*=fibonacci(sum)
print(prod%1000000007)

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

Solution (Python):
def Fibonacci(n):
  if n==1 or n==2:
    return 1
  a,b=1,1
  for i in range (3,1+n):
    a,b=a+b,a
  return a

n,m=map(int,input().split())
bk=-1
ans=1
for i in range(m):
  a=int(input())
  if bk==-1 and a==2:
    ans*=2
  elif bk+1==a:
    print(0)
    exit()
  ans*=Fibonacci(a-bk-1)
  bk=a
if bk!=m:
  ans*=Fibonacci(n-bk)
print(ans%(10**9+7))

Solution (Python):
mod = pow(10,9)+7
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]+[mod]
DP = [1]
k = 0
for i in range(1,N+1):
    if i==A[k]:
        DP.append(0)
        k+=1
    else:
        a = DP[i-1]
        b = DP[i-2] if i>1 else 0
        DP.append((a+b)%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 = [0] * (N + 1)
dp[0] = 1
for a in A:
    dp[a] = -1

for i in range(N):
    if dp[i] >= 0:
        if dp[i + 1] >= 0:
            dp[i + 1] += dp[i]
        if i + 2 <= N and dp[i + 2] >= 0:
            dp[i + 2] += dp[i]

print(dp[N] % mod)

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
for a in A:
    dp[a] = -1

for i in range(N):
    if dp[i] >= 0:
        if dp[i + 1] >= 0:
            dp[i + 1] += dp[i]
        if i + 2 <= N and dp[i + 2] >= 0:
            dp[i + 2] += dp[i]

print(dp[N] % mod)

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M, *A = map(int, read().split())
 
MOD = 10**9 + 7
 
dp = [0] * (N + 10)
dp[0] = 1
is_broken = [False] * (N + 1)
 
for x in A:
    is_broken[x] = True
 
for n in range(1, N + 1):
    if is_broken[n]:
        continue
    x = dp[n - 1] + dp[n - 2]
    if x >= MOD:
        x -= MOD
    dp[n] = x
 
answer = dp[N]
print(answer)

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

n, m = map(int, input().split())
pattern = [1]
broken = -1
brokencnt = 0
if brokencnt < m:
    broken = int(input())
    brokencnt += 1
for i in range(1, n+1):
    if i == broken:
        pattern.append(0)
        if brokencnt < m:
            broken = int(input())
            brokencnt += 1
        continue

    if i == 1:
        pattern.append(pattern[i-1])
    if i > 1:
        pattern.append((pattern[i-1]+pattern[i-2]) % mod)

print(pattern[n])

Solution (Python):
n,m = map(int,input().split())
dp = [0]*n

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if n == 1:
    print(dp[0])
else:
    if dp[1] == 10**12:
        dp[1] = 0
    else:
        dp[1] = 1+ dp[0]

    mod = 1000000007

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

mod = 1000000007

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

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

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

print(dp[n])

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


mod=10**9+7

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

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

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

print(t[n])

Solution (Python):
div = 1000000007

n, m, *b = map(int, open(0).read().split())
a = set(b)
 
f = [0] * (n + 1)
f[0] = 1

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

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

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

  

dp=[0]*(N+3)
dp[1]=1
dp[2]=1
for i in range(3,N+3):
  dp[i]=(dp[i-1]+dp[i-2])%mod
if len(hole)==1:
  print(dp[N+1])
  exit()


ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)

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

  

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

  


ans=1
for h in hole:
  ans*=dp[h]
  ans%=mod
  
print(ans)