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

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(int)
    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):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    A = [0] * (N + 1)
    for _ in range(M):
        A[II()] = 1
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if A[i] == 1:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    ans = dp[N]
    return ans

print(main())

Solution (Python):
import sys
input = sys.stdin.readline
N,M=map(int,input().split())

A=set()
for i in range(M):
    a=int(input())
    A.add(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[1]=dp[0]
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod
print(dp[N])

Solution (Python):
N, M = map(int, input().split())
MOD = 10**9 + 7
F = [0]*(N+1)
for i in range(M):
    F[int(input())-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):
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 u[i] == 1: F[i] = 0

print(F[n])

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] * (N + 1)
    dp[0] = 1
    j = 0
    for i in range(N):
        if j < M and i == a[j]:
            dp[i] = 0
            j += 1
        if i + 1 <= N:
            dp[i + 1] += dp[i]
        if i + 2 <= N:
            
            dp[i + 2] += dp[i]
    ret = dp[N] % MOD
    print(ret)
    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 = 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):
	broken[int(input())] = 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):

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 = [0 for i in range(n+10)]
    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, 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):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

arrs = set([int(input()) for _ in range(M)])
anss = [0, 1]
for i in range(1, N+1):
  if i in arrs:
    anss.append(0)
  else:
    anss.append((anss[-2] + anss[-1]) % MOD)
print(anss[-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 = [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():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

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