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):
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

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()

a = [INT() for _ in range(M)]
ng = [0]*(N+1)
for i in a:
	ng[i] = 1

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

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

Solution (Python):
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
    
k=10**9+7
for i in range(2,n+1):
    if dp[i]!=0:
        dp[i]=(dp[i-1]+dp[i-2])%k
        
print(dp[-1])

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

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

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

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

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

print(dp[n])

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

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

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

for i in range(2, n + 1):
    if i not in list_score:
        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 = set([int(input()) for _ in range(m)])
p, q = 0, 1
mod = 10 **9 + 7
for i in range(1, n+1):
    p, q = q, ((p+q)%mod)*(i not in A)
print(q)

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

dp = [0 for _ in range(n + 2)] 
dp[0] = 0
dp[1] = 1
tmp = 0
if m != 0:
    for i in range(n):
        if i + 1 != a[tmp]:
            dp[i + 2] = (dp[i] + dp[i + 1]) % (pow(10, 9) + 7)
        elif i + 1 == a[tmp]:
            if tmp < m - 1:
                tmp += 1
            dp[i + 2] = 0
elif m == 0:
    for i in range(n):
        dp[i + 2] = (dp[i] + dp[i + 1]) % (pow(10, 9) + 7)

print(dp[n + 1])

Solution (Python):

import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] 
    dp[0] = 1
    if n >= 2:
        dp[1] = 2
    for i in range(2, n):
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and tmp < m and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and (tmp >= m or 2 != a[tmp]):
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)

print(dp[n - 1] % (pow(10, 9) + 7))

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


def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

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

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

print(dp[n])

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

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

Solution (Python):
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 1000000007

a=open(0)
N,_,*a = map(int, a.read().split())

dp = [-1 for _ in range(100010)]
dp[0] = 0
for i in a: dp[i] = 0
def rec(i):
    if dp[i] > -1:
        return dp[i]
    if i<3:
        dp[i] = rec(i-1) + 1
        return dp[i]
    dp[i] = (rec(i-1)+rec(i-2))%MOD
    return dp[i]
    
print(rec(N))

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))
isHole = [False]*(n+1)


dp = [1]*(n+1)

for a in A:
    isHole[a] = True
    dp[a] = 0


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

print(dp[-1]%p)

Solution (Python):
if __name__ == "__main__":
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())
    a = list()
    for i in range(m):
        a.append(int(input()))

    dp = [0] * (n + 1)

    for aa in a:
        dp[aa] = -1

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

    if n > 1:
        if dp[2] != -1:
            dp[2] = 1 + dp[1]
        else:
            dp[2] = 0

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

    print(dp[n])

Solution (Python):
N, M = map(int, input().split())
out = set()
for _ in range(M):
    out.add(int(input()))

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

for i in range(1, N+1):
    if i not in out:
        if i == 1:
            check[i] = check[i-1]
        else:
            check[i] = check[i-2] + check[i-1]
    else:
        check[i] = 0

print(check[N] % 1000000007)

Solution (Python):
def solve():
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    isBreakable = [False] * (N+1)
    for i in range(M):
        a = int(input())
        isBreakable[a] = True

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

if __name__ == '__main__':
    solve()

Solution (Python):
div = 10 ** 9 + 7
N, M = map(int, input().split())
h = [1] * (N + 1)
for _ in range(M):
    index = int(input())
    h[index] = 0

a = 1
b = h[1]
for i in range(2, N + 1):
    a, b = b, (a + b) * h[i] % div

print(b)

Solution (Python):

mod=1000000007

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

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

ans=dp[0]%mod
print(ans)

Solution (Python):



N , M = map(int, input().split())
hole_list = [0]*(N+1)
for i in range(M):
    hole_i = int(input())
    hole_list[hole_i] = 1


cost_list = [0]*(N+1)
cost_list[0] = 1
MOD = 10**9 + 7


for i in range(1, N+1):
    if hole_list[i]==1: 
        continue

    if hole_list[i-1]==0:
        cost_list[i] += cost_list[i-1]
        cost_list[i] %= MOD

    if i-2>=0:
        if hole_list[i-2]==0:
            cost_list[i] += cost_list[i-2]
            cost_list[i] %= MOD


print(cost_list[N])

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

N, M = map(int,input().split())
a = [int(input()) for k in range(M)] + [-1]

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

dp[0] = 1
if a[0] == 1:
    dp[1] = 0
    i += 1
else:
    dp[1] = 1

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

dp[0] = 1
if 1 not in A:
  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 = map(int,input().split())
a = [int(input()) for i in range(M)]
a = set(a)

dp = [0]*(N+100)
for i in range(N+1):
  if i == 0:
    dp[i] = 1
    continue
  if i in a:
    continue
  elif i-1 in a:
    dp[i] = dp[i-2]
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a and i-2 in a:
    break
  else:
    dp[i] = dp[i-1] + dp[i-2]
  dp[i] = dp[i]%(7+10**9)
    
print(dp[N]%(7+10**9))

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

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
for i in range(m):
    dp[a[i]]=-1

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

Solution (Python):
MOD = 10**9+7
N,M = map(int,input().split())
DP = [0]*(N+3)
DP[0] = 1
state = [1]*(N+3)
for _ in range(M):
    i = int(input())
    state[i] = 0

for i in range(N):
    for j in range(1,3):
        if state[j+i]:
            DP[j+i] += DP[i]
            DP[j+i] %= MOD

print(DP[N])

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)] + [-1]
    dp = [Mint() for _ in range(N+1)]
    dp[0] = Mint(1)
    j = 0
    for i in range(1,N+1):
        if i == A[j]:
            j += 1
            continue
        dp[i] += dp[i-1]
        if i >= 2: dp[i] += dp[i-2]

    print(dp[N])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

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


if __name__ == "__main__":
    solve()

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 STR(): return input()
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 = sys.maxsize
mod = 10 ** 9 + 7

n,m = MAP()
a = [INT() for _ in range(m)]
dp = [0 for _ in range(n+2)]
dp[0] = 0
dp[1] = 1
j = 0
for i in range(2, n+2):
    if j >= m or a[j] != i - 1:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    else:
        dp[i] = 0
        j += 1
print(dp[n+1])

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


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

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


for i in range(N):
    if i == a[-1]:
        a.pop()
        dp[i] = 0
        continue
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
    dp[i + 2] += dp[i]
    dp[i + 2] %= mod

ans = dp[N]
print(ans)

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

mod = 10**9+7

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M= map(int, input().split())
    mod = 7 + 10 ** 9
    A = [True] * (N + 1)
    for _ in range(M):
        A[int(input())] = False
    DP = [0] * (N + 1)
    DP[0] = 1
    for i in range(N):
        if i < N - 1:
            if A[i + 2]: 
                DP[i + 2] += DP[i]
                DP[i + 2] %= mod
        if A[i + 1]:
            DP[i + 1] += DP[i]
            DP[i + 1] %= mod

    print(DP[N])

    return 0

if __name__ == "__main__":
    solve()

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

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

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    A = {int(input()) for i in range(M)}
    MOD = 10**9 + 7
    dp = [0]*(N+1)
    dp[0] = 1
    for i in range(N):
        if i + 1 not in A:
            dp[i+1] += dp[i]
            dp[i+1] %= MOD
        if i+2 <= N and i+2 not in A:
            dp[i+2] += dp[i]
            dp[i+2] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

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


step = [1,1] + ["x"]*(N-1)

for i in a_list:
    step[i] = 0

for i in range(2,N+1):
    if step[i] == "x":
        step[i] = ( step[i-1] + step[i-2] ) % (10**9 + 7)

print(step[N])

Solution (Python):
N, M = map(int, input().split())
A = [None]*M
for i in range(M):
    A[i] = int(input())
A = [-1] + A + [N+1]

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        a, b = 1, 1
        for _ in range(n-2):
            a, b = b, a + b
        return b

ans = 1
for i in range(M+1):
    dansuu = (A[i+1]-1)-(A[i]+1)
    if dansuu == -1:
        ans *= 0
        break
    else:
        ans *= fibonacci(dansuu + 1)

print(ans%1000000007)

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

possible_count = [0 for n in range(N + 1)]
for _ in range(M):
  i = int(input())
  possible_count[i] = -1

possible_count[0] = 1
for i in range(N):
  if possible_count[i] == -1:
    continue

  if i + 2 > N:
    possible_count[i+1] += possible_count[i] if possible_count[i+1] != -1 else 0
    continue

  possible_count[i+1] += possible_count[i] if possible_count[i+1] != -1 else 0
  possible_count[i+2] += possible_count[i] if possible_count[i+2] != -1 else 0

print(possible_count[len(possible_count) - 1] % 1000000007)

Solution (Python):
N, M = map(int, input().split())
ngs = [int(input()) for _ in range(M)]
mae = -10**9
for ng in ngs:
    if abs(ng - mae) == 1:
        print(0)
        exit()
    mae = ng
fib = [1, 1]
for i in range(N):
    fib.append(fib[-1]+fib[-2])
ans = 1
now = 0
for ng in ngs:
    l = ng - now - 1
    ans *= fib[l]
    ans %= (10**9+7)
    now = ng + 1
if now == N-1:
    print(ans)
    exit()

l = N - now
ans *= fib[l]
ans %= (10**9+7)
print(ans)

Solution (Python):
N, M = map(int, input().split(' '))
dp = [0 for _ in range(N + 1)]
for _ in range(M):
    i = int(input())
    dp[i] = -float('inf')

mod = 10**9 + 7
dp[0] = 1
for i in range(N+1):
    if dp[i] ==  -float('inf'):
        continue

    if 0 <= i-1 < N and dp[i-1] != -float('inf'):
        dp[i] += dp[i-1]

    if 0 <= i-2 < N and dp[i-2] != -float('inf'):
        dp[i] += dp[i-2]

    dp[i] = 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())
stairs = [1 for i in range(N)]
for i in range(M):
  kari = int(input())
  stairs[kari-1] = 0
mod = 1000000007
if N <= 2:
  ans = sum(stairs)
else:
  if stairs[0]==1 and stairs[1]==1:
    stairs[1] = 2
  for i in range(2, N):
    stairs[i] = (stairs[i] * (stairs[i-1] + stairs[i-2])) % mod
  ans = stairs[N-1]
print(ans)

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

N, M = [int(i) for i in input().strip().split()]
dirty_step_idxs = [0] * M
for i in range(M):
  dirty_step_idx = int(input())
  dirty_step_idxs[i] = dirty_step_idx

def fibonacci(n):
  
  a, b = 0, 1
  for i in range(n-1):
    a, b = b, a + b
  return a
  
if M == 0:
  res = fibonacci(N + 2)
else:
  res = 1
  now_step_idx = 0
  for i in range(M):
    n_step = dirty_step_idxs[i] - now_step_idx - 1
    if n_step == -1:
      res = 0
      break
    res *= fibonacci(n_step + 2)
    now_step_idx = dirty_step_idxs[i] + 1
  rest_steps = N - now_step_idx
  res *= fibonacci(rest_steps + 2) 
    
print(res % MOD)

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

div = 1e9 + 7
path = 0
prev1 = 1
prev2 = 0

for n in range(1, N+1):
  if skip[n]:
    path = 0
  else:
    path = int((prev1 + prev2) % div)

  prev1, prev2 = path, prev1

print(path)

Solution (Python):




def main():
    N, M = map(int, input().split())
    A = set([int(input()) for _ in range(M)])

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

    for i in range(1, N + 1):
        if i in A:
            continue

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

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

    print(dp[N])


if __name__ == "__main__":
    main()

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

broken = [0 for _ in range(n+1)]
for i in a:
    broken[i] = 1
dp = [0 for _ in range(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]

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

Solution (Python):
import sys

read = sys.stdin.read

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

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


a = [0 for _ in range(n+1)]
for i in IN:
    a[i] = 1




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

dp[n] = 0
if a[n-1] == 1:
    dp[n-1] = 0
else:
    dp[n-1] = 1
if a[n-2] == 1:
    dp[n-2] = 0
elif dp[n-1] == 0:
    dp[n-2] = 1
else:
    dp[n-2] = 2

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

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

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod = 10**9 + 7

pat = [1 for _ in range(N+1)]
for j in a :
    pat[j] = 0

for i in range(2,N+1) :
    if pat[i] == 0 :
        continue
    else :
        pat[i] = (pat[i-1] + pat[i-2])%mod

print(pat[N])

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

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

print(dp[n])

Solution (Python):
from collections import deque
def main():
  N,M,*A=map(int, open(0).read().split())
  mod=10**9+7
  dp = [0] * (N+1)
  A=deque(A+[N+1])
  tmp=A.popleft()
  dp[:2] = [1, 1 if tmp!=1 else 0]
  if tmp==1:
    tmp=A.popleft()
  for i in range(2, N+1):
    if i==tmp:
      tmp=A.popleft()
      continue
    dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()

Solution (Python):
def main():
  N,M,*alst=map(int, open(0).read().split())
  mod=10**9+7
  if M==0:
    dp = [0] * (N+1)
    dp[:2] = [1, 1]
    for i in range(2, N+1):
      dp[i] = (dp[i-2] + dp[i-1])%mod
    print(dp[N])
    quit()
  tmp=0
  a0=alst[0]
  alst+=[N+1]
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if alst[tmp]!=1 else 0]
  if a0==1:
    tmp=1
  for i in range(2, N+1):
    if i!=alst[tmp]:
      dp[i] = (dp[i-2] + dp[i-1])%mod
    else:
      tmp+=1
  print(dp[N])
main()

Solution (Python):
def main():
  N,M,*alst=map(int, open(0).read().split())
  alst=set(alst)
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()

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

mod = 10**9 + 7

ans = [0] * (n+2)
ans[0] = 0
ans[1] = 1
for i in range(2,n+2):
    if(i-1 in a):
        continue
    for j in [-1,-2]:
        ans[i] += ans[i+j]
    ans[i] = ans[i] % mod

print(ans[-1])

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

        if head < m and a[head] == i:
            ans[i] = 0
            head += 1
        else:
            if i == 1:
                ans[i] = 1
            else:
                
                ans[i] = (ans[i-1] + ans[i-2]) % MOD

    print(ans[n] % MOD)



if __name__ == '__main__':
    main()

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

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

if 0 in A:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1])

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

t=[True]*(n+1)

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

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


for i in range(0,n):
    for j in range(i+1,min(n,i+2)+1):
        if t[j]:
            dp[j]+=dp[i]
            dp[j] %=(1000000007)


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

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

t = 1000000007

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

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

N, M = map(int, input().split())
a = {int(input()) for i in range(M)}

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

print(dp[N])

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

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

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

mod = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if broken[1] else 1

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

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):



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

print(fib[n])

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  for i in range(2,n+1):
    if ans[i]>0:
      ans[i]=(ans[i-1]+ans[i-2])%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  for i in range(n+1):
    ans[i]=ans[i] if ans[i]==0 or i<2 else (ans[i-1]+ans[i-2])%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

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

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

for i in range(M):
    step[a[i]] = -1

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

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

print(step[N])


def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)

Solution (Python):

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

Solution (Python):

mod=10**9+7
n,m=map(int,input().split())
broken={i:False for i in range(n+1)}
for i in range(m):
    a=int(input())
    broken[a]=True
way_to_go=[0 for i in range(n+1)]
way_to_go[0]=1
if broken[1]==True:
    way_to_go[1]=0
else:
    way_to_go[1]=1
for j in range(2,n+1):
    if broken[j]==False:
        if broken[j-1]==False:
            way_to_go[j]+=way_to_go[j-1]
        if broken[j-2]==False:
            way_to_go[j]+=way_to_go[j-2]
        way_to_go[j]%=mod
print(way_to_go[n])

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

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

for i in range(M):
    step[a[i]] = -1

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

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

print(step[N])


def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)