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 = list(map(int, input().split()))
V = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
A = set(a)
ANS = [0 for _ in range(N + 5)]

ANS[0] = 1
for i in range(N):
    ANS[i] %= V
    if not i + 1 in A:
        ANS[i + 1] += ANS[i]
    if not i + 2 in A:
        ANS[i + 2] += ANS[i]

print(ANS[N] % V)

Solution (Python):

from sys import stdin




def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


MOD = 10**9+7
N, M = _li()

a_list = []
for _ in range(M):
    a_list.append(_i())
a_list.append(-1)

ans = [1, 1]
a_index = 0
if a_list[a_index] == 1:
    ans[1] = 0
    a_index += 1

for i in range(2, N+1):
    if i == a_list[a_index]:
        ans = [ans[1], 0]
        a_index += 1
    else:
        ans = [ans[1], ans[0] + ans[1] % MOD]
    if ans[0] + ans[1] == 0:
        break
print(ans[1] % MOD)

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

LARGE = 10**9 + 7

r_arr = [0]*(N+1)
r_arr[0] = 1
if a_dict.get(1, 0) == 1:
    r_arr[1] = 0
else:
    r_arr[1] = 1

for i in range(2, N+1):
    if a_dict.get(i, 0) == 1:
        pass
    else:
        r_arr[i] = (r_arr[i-1] + r_arr[i-2]) % LARGE

print(r_arr[-1])

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

aa = {}
for _ in range(m):
  aa[int(input())] = True

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

for i in range(2, n+1):
  if i in aa:
    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())
a = [int(input()) for _ in range(M)]
bl = [True] * (N + 2)
for aa in a:
    bl[aa] = False

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

for step_frm in range(N):
    if bl[step_frm]:
        dp[step_frm + 2] += dp[step_frm]
        dp[step_frm + 2] %= mod
        dp[step_frm + 1] += dp[step_frm]
        dp[step_frm + 1] %= mod
print(dp[N])

Solution (Python):
N, M, *C = map(int, open(0).read().split())
MOD = 10**9 + 7
F = [0]*(N+1)
for c in C:
    F[c-1] = 1

a = 1; b = 0
for i in range(N):
    if F[i]:
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

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


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

print(S[N])

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

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

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

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

dp[0] = 1

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

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

ans = dp[-1]

ans %= (10**9 + 7)

print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
A = [int(input()) for i in range(m)]
p = int(1e9) + 7

is_broken = [False] * (n + 1)

for a in A:
    is_broken[a] = True

DP = [0] * (n + 2)
DP[0] = 1

for i in range(n):
    if is_broken[i]:
        DP[i] = 0
        continue
    
    DP[i + 1] += DP[i] % p
    DP[i + 2] += DP[i] % p

print(DP[n] % p)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV=10**9+7

def mod_invs(n,mod=DIV):
    inv=[0]*(n+1)
    inv[0]=1
    inv[1]=1
    for i in range(2,n+1):
        inv[i] = (-(mod//i)*inv[mod%i]) % mod
    return inv



def main():
    N,M = ints_raw()
    As = [int_raw() for _ in range(M)]
    is_breake = [0]*(N+1)
    for a in As:
        is_breake[a]=1
    memo = [0]*(N+1)

    memo[0]=1
    memo[1]=1 if is_breake[1]==0 else 0
    for n in range(2,N+1):
        if is_breake[n]:
            continue
        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[-1]

print(main())

Solution (Python):

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

dp = [0]*(n+2)
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 not in a:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD

print(dp[-2])

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

dp = [0 for i in range(n+2)]
dp[0] = 1
a = set()
for i in range(m):
  t = int(input())
  a.add(t)

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

print(dp[n])

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

Solution (Python):
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    stairs = [0] * (N + 1)
    stairs[0] = 1
    for i in range(N):
        if i + 1 <= N and (i + 1) not in a:
            stairs[i + 1] += stairs[i]
        if i + 2 <= N and (i + 2) not in a:
            stairs[i + 2] += stairs[i]
    return stairs[N] % MOD

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

Solution (Python):
def getlist():
	return list(map(int, input().split()))

N, M = getlist()
L = [0 for i in range(N + 100)]
L[0] = 1
L[1] = 1

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

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

print(L[N] % 1000000007)

Solution (Python):
MOD = int(1e9+7)

def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    broken = [False] * (N+1)
    for a in A:
        broken[a] = True
    dp = [0] * (N+1)
    dp[0] = 1
    if not broken[1]:
        dp[1] = 1
    for i in range(2, N+1):
        if not broken[i]:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    print(dp[N])

if __name__ == "__main__":
    main()

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return


def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return


def C():
    n,m = LI()
    f = [1 for i in range(n+1)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return


def D():
    h,w = LI()
    s = SR(h)

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

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

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


def solve(N: int, M: int, a: "List[int]"):

    
    dp = [None]*(N+1)
    dp[0] = 1
    for i in a:
        dp[i] = 0
    for i in range(1, N+1):
        
        if dp[i] == None:
            b = dp[i-1]
            if i-2 >= 0:
                b += dp[i-2]
                b %= MOD
            dp[i] = b
    print(dp[N])
    return


def main():

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


if __name__ == '__main__':
    main()

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

for a in A:
    T[a] = -1

T[0] = 1
for i in range(0, N):
    if i + 1 <= N and T[i + 1] != -1 and T[i] != -1:
        T[i + 1] = (T[i + 1] + T[i]) % MOD
    if i + 2 <= N and T[i + 2] != -1 and T[i] != -1:
        T[i + 2] = (T[i + 2] + T[i]) % MOD

print(T[N])

Solution (Python):
import sys
N, M = map(int, input().split())
dp = [0]*(N + 1)
dp[0] = 1
A = [int(sys.stdin.readline()) for _ in range(M)]
D = set(A)
mod = 10**9 + 7
for i in range(1, N+1):
    res = 0
    if i - 1 >= 0 and i - 1 not in D:
        res += dp[i-1]
    if i - 2 >= 0 and i - 2 not in D:
        res += dp[i-2]
    dp[i] = res % mod
print(dp[-1])

Solution (Python):



def solve():
    n, m = map(int, input().split())
    am = set(int(input()) for i in range(m))
    ans = [0] * (n + 10)
    ans[0] = 1
    md = 10 ** 9 + 7
    for i in range(n):
        if (i + 1) not in am:
            ans[i + 1] += ans[i]
            ans[i + 1] %= md
        if (i + 2) not in am:
            ans[i + 2] += ans[i]
            ans[i + 2] %= md
    print(ans[n])

if __name__=="__main__":
    solve()

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

MOD = int(1e9) + 7

N, M = map(int, input().split())
a = [True]*(N+1)

for i in range(1, M+1):
    n = int(input())
    a[n] = False


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

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

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

Solution (Python):

MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    a = []
    for i in range(M):
        buf = input()
        a.append(int(buf))
    a.append(N+1) 
    pattern = [1]
    for i in range(1, N+3):
        pattern.append(0)
    pointer = 0
    for i in range(0, N+1):
        if a[pointer] == i:
            pattern[i] = 0
            pointer += 1
        pattern[i+1] = (pattern[i+1] + pattern[i]) % MOD
        pattern[i+2] = (pattern[i+2] + pattern[i]) % MOD
    print(pattern[N])

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from collections import defaultdict
from functools import reduce

MOD = 1000000007

A = set()




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

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

res = [0]*(n+1)

res[0] = 1
if 1 not in A:
    res[1] = 1

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

print(res[n])



class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

Solution (Python):
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
a = set() 
dp = [0] * (n+10)
dp[0] = 1
for i in range(m):
    a.add(int(input()))
for i in range(n):
    if i+1 in a and i+2 in a:
        print(0)
        exit()
    elif i+1 in a:
        dp[i+2] += dp[i]
    elif i+2 in a:
        dp[i+1] += dp[i]
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
    dp[i+1] %= MOD
    dp[i+2] %= MOD
print(dp[n] % MOD)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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)]
b = [0] * (N+1)  
for i in a:
	b[i] = 1

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

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

print(dp[N])

Solution (Python):

import sys
from operator import itemgetter






















input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())


MOD = 1000000007  

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(M) ]  
    setA = set(a)
    
    dp = [0 for i in range(N + 10)]
    dp[0] = 1
    if 1 not in setA:
        dp[1] = 1
    else:
        dp[1] = 0
    if 2 not in setA:
        dp[2] = dp[1]+1
    else:
        dp[2]=0
    for i in range(3,N+1):
        if i-1 in setA and i-2 in setA:
            dp[i] = 0
        elif i - 1 in setA:
            dp[i] = dp[i - 2] % MOD
        elif i - 2 in setA:
            dp[i] = dp[i-1]%MOD
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

    print(dp[N])

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

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

j = 0
for i in range(1, n + 1):
    if j < m and i == arr[j]:
        dp[i] = 0
        j += 1
        continue

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

print(dp[n])

Solution (Python):
mod=1000000007
N,M=map(int,input().split())
dp=[-1]*(N+1)
dp[0]=1

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

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

A = [True for i in range(N + 1)]

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

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

dp[0] = 1
for i in range(N):
    if A[i] == 0:
        continue
    dp[i + 1] += dp[i]
    dp[i + 1] %= 1000000007
    dp[i + 2] += dp[i]
    dp[i + 2] %= 1000000007

print(dp[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 collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = map(int, raw_input().split())
flag = [False] * (N + 1)
for i in range(M):
    num = input()
    flag[num] = True

DP = [0, 1] + [0] * N
for i in range(1, N + 1):
    if not flag[i]:
        DP[i + 1] = DP[i] + DP[i - 1]
        DP[i + 1] %= MOD
print DP[N + 1]

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

Solution (Python):

N,M = list(map(int,input().split()))
V = 10**9 + 7
a = [int(input()) for _ in range(M)]
A =set(a)
ANS = [0 for _ in range(N+2)]

ANS[0] = 1
for i in range(N):
    ANS[i]%= V
    if not i+1 in A:
        ANS[i+1] += ANS[i]
    if not i+2 in A:
        ANS[i+2] += ANS[i]

print(ANS[N]% V)

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

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return


def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return


def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(lambda : 0)
    dp[0] = 1

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


def D():
    h,w = LI()
    s = SR(h)

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    A = set(LIN(M))
    
    dp = [0] * (N + 1)
    dp[0]=1
    if 1 not in A:
        dp[1] = 1
    
    for i in range(2,N+1):
        if i in A:
            continue
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i]%=mod
    print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    a = set(a)
    res = [0 for _ in range(N+1)]
    res[0] = 1
    if 1 in a:
        res[1] = 0
    else:
        res[1] = 1
    
    for i in range(2, N+1):
        if i in a:
            continue
        
        res[i] = (res[i-1] + res[i-2]) % MOD

    print(res[N])

    return



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

if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())

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

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

MOD = 1000000007
n,m = getlist()

broken = [0 for i in range(n+1)]
for i in range(m):
    broken[getN()] = 1

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

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

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

print(dp[n])

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

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7





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

dp = [0] * (N + 5)
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 not in A:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N] % MOD)

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

Solution (Python):
import bisect
n,m = map(int,input().split())
p = [0]*(n+1)
mod = 10**9+7

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

p[0]=1

for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    p[i] += p[i-1]
    if i >= 2:
      p[i] += p[i-2]
    p[i] = p[i]%mod

print(p[-1]%mod)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return


def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return


def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(lambda : 0)
    dp[0] = 1

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


def D():
    h,w = LI()
    s = SR(h)

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

Solution (Python):
N, M = map(int, input().split())
P = 10**9+7
NG = [0] * (N+1)
for i in range(M):
    NG[int(input())] = 1

X = [1] + [0] * N
for i in range(1, N+1):
    if NG[i]:
        continue
    X[i] = (X[i-1] + (X[i-2] if i > 1 else 0)) % P

print(X[N])

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

MOD = 10**9 + 7

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

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


rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,M=rl()
A=[0]*M
for i in range(M):
    A[i] = ri()

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

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

print(dp[N])

Solution (Python):
p = 1000000007

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

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

F[0] = 1
for i in range(1, n+1):
	F[i] = (F[i-1]+F[i-2])%p if i > 1 else F[i-1]
	if u[i] == 1: F[i] = 0

print(F[n])

Solution (Python):
N, M = map(int, input().split())
kaidan = [True] * (N+2)
for i in range(M):
    kaidan[int(input())] = False

dp = [0]*(N+2)
dp[0] = 1
for i in range(N):
    if kaidan[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= 1000000007
    if kaidan[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= 1000000007

print(dp[N])

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
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[i] = 1
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

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

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):
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N, M = map(int, file().split())
    broken = set()
    for i in range(M): broken |= {int(file())}

    DP = [0] * (N + 1)
    DP[0] = 1
    for i in range(N):
        if i + 1 not in broken: 
            DP[i+1] += DP[i]
            DP[i+1] %= mod
        if i + 2 <= N:
            if i + 2 not in broken:
                DP[i+2] += DP[i]
                DP[i+2] %= mod
    print(DP[N])
    return 0
  
if __name__ == "__main__":
    solve()

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

for i in range(n):
    if i in s:
        continue
    for j in range(1,3):
        if i+j <= n:
            dp[i+j] = (dp[i+j] + dp[i])%mod

print(dp[-1])

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


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

for i in range(N):
    if (Broken[i + 1]) == 0 and (i + 1) <= N:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD

    if (Broken[i + 2]) == 0 and (i + 2) <= N:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N] % MOD)