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())
a=set()
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a.add(int(input()))
for i in range(1,n+1):
    if i in a:
        continue
    if i>=1:
        dp[i]+=dp[i-1]
    if i>=2:
        dp[i]+=dp[i-2]
    dp[i]%=mod
print(dp[-1])

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+9999) 
    pattern = [1]
    for i in range(1, N+10):
        pattern.append(0)
    pointer = 0
    for i in range(0, N+2):
        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 sys
input = sys.stdin.readline

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

ANSLIST=[0]*(N+4)
ANSLIST[0]=1

for i in range(N):
    if not(i+1 in A):
        ANSLIST[i+1]=(ANSLIST[i+1]+ANSLIST[i])%mod

    if not(i+2 in A):
        ANSLIST[i+2]=(ANSLIST[i+2]+ANSLIST[i])%mod

    
    

print(ANSLIST[N])

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

Solution (Python):
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):
N, M = map(int, input().split())
a = []
stair = [1 for i in range(N+1)]
for i in range(M):
    stair[int(input())] = 0

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

dp[0] = 1

MOD = 1000000007

for i in range(1, N+1):
    if stair[i] == 1:
        dp[i] = (dp[i-1] + dp[i-2]) % 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(100000 + 5)]

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

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

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

for i in range(N):
  if a[i]==-1:
    continue
  if a[i+1]!=-1:
    a[i+1]+=a[i]
    a[i+1]%=MOD
  if i+2<=N and a[i+2]!=-1:
    a[i+2]+=a[i]
    a[i+2]%=MOD
print(a[N])

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

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

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

print(dp[-1])

Solution (Python):
n,m = map(int,input().split())
way = [1 for _ in range(n+1)]
for i in range(m):
  ai = int(input())
  way[ai] = 0
for i in range(2,n+1):
  if way[i] != 0:
    way[i] = (way[i-1]+way[i-2])%1000000007
print(way[n])

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


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

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

MOD =  1000000007

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

a_list = set()
for _ in range(M):
	a_list.add(int(input()))



counts = [0] * (N + 3)
counts[0] = 1
for i in range(N):
	if not i in a_list:
		counts[i + 1] = (counts[i + 1] + counts[i]) % MOD
		counts[i + 2] = (counts[i + 2] + counts[i]) % MOD


print(counts[N])

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


MOD = 10**9 + 7

N, M = inpl()
A = [False for i in range(N + 1)]
for i in range(M):
    a = int(input())
    A[a] = True
p = 1
pp = 0
ans = 0

for i in range(1, N + 1):
    if A[i] is True:
        pp = p
        p = 0
    else:
        ans = p + pp
        pp = p
        p = ans
    

print(ans % MOD)

Solution (Python):
MOD = 1000000007

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)] + [N + 2]

dp, id = [0, 1], 0
for i in range(N):
    if A[id] - 1 == i:
        id += 1
        dp.append(0)
    else:
        dp.append(dp[-1] + dp[-2])

print(dp[-1] % MOD)

Solution (Python):
N, M = map(int,input().split())
P = 1000000007
a = []
for _ in range(M):
    a.append(int(input()))
a.append(N+3)
dp = [0]*(N+2)
dp[0] = 0
dp[1] = 1
t = 0
for i in range(N):
    if i+1 == a[t] :
        t += 1
        continue
    else:
        dp[i+2] = (dp[i+1] + dp[i])%P
print(dp[N+1])

Solution (Python):
import sys
import math
from itertools import accumulate as acc
MOD=10**9+7
N,M=map(int,input().split())
if N==1: print(1),sys.exit()
a=[0]*(N+1)
for i in range(M):
  a[int(input())]=-1
pat=[0 for i in range(N+1)]
pat[0]=1
if a[1]==0: pat[1]=1

for i in range(2,N+1):
    if a[i]==-1: continue
    if a[i-1]==0 and a[i-2]==0: pat[i]=pat[i-1]+pat[i-2]
    elif a[i-1]==0 and a[i-2]==-1: pat[i]=pat[i-1]
    elif a[i-1]==-1 and a[i-2]==0: pat[i]=pat[i-2]
    else: print(0),sys.exit()
    pat[i]%=MOD
print(pat[N])

Solution (Python):
N,M = map(int,input().split())
MOD = 10**9 + 7
a = []
broken = [False for i in range(N+1)]
if M > 0:
	for i in range(M):
		x = int(input())
		a.append(x)
		broken[x] = True

	for i in range(M-1):
		if a[i+1]-a[i] == 1:
			print(0)
			exit()

dp = [0 for i in range(N+1)]
dp[0] = 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]) % MOD
print(dp[N])

Solution (Python):

"""



"""
import sys


def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    if N == 1:
        return 1 if 1 not in A else 0
        
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


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


if __name__ == '__main__':
    main(sys.argv[1:])

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):
Q = 10**9+7
N, M = map( int, input().split())
V = [0]*(N+1)
dp = [0]*(N+1)
dp[0] = 1
for _ in range(M):
    a = int( input())
    V[ a] = 1
for i in range(N):
    dp[i] %= Q
    if i == N-1:
        dp[N] += dp[N-1]
        continue
    if V[i+1] == 0:
        dp[i+1] += dp[i]
    if V[i+2] == 0:
        dp[i+2] += dp[i]
print(dp[N]%Q)

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

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

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

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

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

print(dp[N])

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
n,m = m()


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

for i in range(m):
	k = int(input())
	dp[k] = -1

for i in range(2,n+1):
	if dp[i] == -1:
		continue
	elif dp[i-1] == -1 and dp[i-2] == -1:
		continue
	elif dp[i-1] == -1:
		dp[i] += dp[i-2]
	elif dp[i-2] == -1:
		dp[i] += dp[i-1]
	else:
		dp[i] += dp[i-1] + dp[i-2]
print(dp[-1]%(10**9+7))

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

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

next_a = a.pop(0)

for i in range(N):
    if next_a == i:
        dp[i] = 0
        next_a = a.pop(0)
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
print(dp[N]%1000000007)

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

for i in range(n):
    if not ok[i]:
        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):
Mod = 10**9+7
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]

v = [-1]*(n+1)
v[0] = 1

for t in a:
  v[t] = 0

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

print(v[n])

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

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

dp = [0] * (n+1)

dp[0] = 1
dp[1] = memo[1]

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

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 1)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 < n + 1 and dp[i + 1] != -1 and dp[i] != -1:
        dp[i + 1] += dp[i] % mod
        dp[i + 1] %= mod
    if i + 2 < n + 1 and dp[i + 2] != -1 and dp[i] != -1:
        dp[i + 2] += dp[i] % mod
        dp[i + 2] %= mod
print(dp[n] % mod)

Solution (Python):
N, M = map(int, input().split())
a = [True] * (N + 3)
a[N + 1] = False
a[N + 2] = False

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

MOD = 10 ** 9 + 7

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

Solution (Python):
N,M = map(int,input().split())
p = 1000000007
L = []
for i in range(M):
  L.append(int(input()))
dp = [float('inf')]*(N+1)
dp[0] = 1
if 1 in L:
  dp[1] = 0
else:
  dp[1] = 1
for j in range(len(L)):
  dp[L[j]] = 0
for i in range(N-1):
  if dp[i+2] == float('inf'):
    dp[i+2] = (dp[i+1]+dp[i])%p
print(dp[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


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 + 1000)
dp[0] = 1

for i in range(N):
    if i + 1 not in A:
        dp[i + 1] += dp[i]
        
    if i + 2 not in A:
        dp[i + 2] += dp[i]
        

print(dp[N] % MOD)

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

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

isBroken = [False] * (N+1)
for A in As:
    isBroken[A] = True

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

print(dp[N])

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

for i in range(n):
    if i+1 not in aa:
        l[i+1]+=l[i]
        l[i+1]=l[i+1]%mod
    if i+2 not in aa and i+2<n+1:
        l[i+2]+=l[i]
        l[i+2]=l[i+2]%mod

print(l[n])

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

MOD = 1000000007

n,m = get_nums_l()
breaks = map(int, sys.stdin.readlines())

dp = [0] * (n+1)

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

dp[n] = 1

for i in range(n-1, -1, -1):
    if dp[i] == -1:
        continue
    
    x = 0
    if dp[i+1] != -1:
        x += dp[i+1]
    
    if i <= (n-2) and dp[i+2] != -1:
        x += dp[i+2]
    
    dp[i] = x % MOD

print(dp[0])

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

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

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

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] = dp[i] % MOD

print(dp[N])

Solution (Python):
n,m = map(int,input().split())
A = [int(input()) for i in range(m)]
B = [0 for i in range(10**5+10)]
for i in range(len(A)):
    B[A[i]] = 1

mod = 10**9 + 7

DP = [1,1]
if B[1] == 1:
    DP[1] = 0
for i in range(2,n+1):
    p1 = DP[i-2] % mod
    p2 = DP[i-1] % mod
    if B[i-2] == 1:
        p1 = 0
    if B[i-1] == 1:
        p2 = 0
    DP.append((p1+p2)%mod)
print(DP[n])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


m = Mod(10**9 + 7)


@mt
def slv(N, M, A):
    dp = [0] * (N+3)
    b = [False] * (N+3)
    for a in A:
        b[a] = True

    A.sort(reverse=True)
    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

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
    dp[1] = dp[0] if A[1] == 0 else 0
    for i in range(2, 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):
N, M = map(int, input().split())
A = [True for _ in range(N + 1)]
for _ in range(M):
    A[int(input())] = False
num = [0 for _ in range(N + 1)]
num[0] = num[1] = 1
for n in range(2, N + 1):
    if not A[n]:
        continue
    if A[n - 1]:
        num[n] += num[n - 1]
    if A[n - 2]:
        num[n] += num[n - 2]
    num[n] %= 10 ** 9 + 7
print(num[N] % (10 ** 9 + 7))

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+5)
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):
MODULO = 1000000007


def solve(n, xs):
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in xs else 0
    for i in range(2, n + 1):
        if i in xs:
            dp[i] = 0
        else:
            if i - 1 not in xs:
                dp[i] += dp[i - 1]
            if i - 2 not in xs:
                dp[i] += dp[i - 2]
        dp[i] %= MODULO
    return dp[n]
         


def main():
    n, m = (int(z) for z in input().split())
    xs = {int(input()) for _ in range(m)}
    res = solve(n, xs)
    print(res)


if __name__ == "__main__":
    main()

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

def inpl(): return list(map(int, input().split()))
N, M = inpl()
MOD = 10**9 + 7
A = [1]*(N+3)
for _ in range(M):
    a = int(input())
    A[a] -= 1

DP = [0]*(N+3)
DP[0] = 1
for i in range(N):
    DP[i+1] = ((DP[i+1] + DP[i])*A[i+1])%MOD
    DP[i+2] = ((DP[i+2] + DP[i])*A[i+2])%MOD
print(DP[N])

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


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

print(dp[N])

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

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

mod = 10 ** 9 + 7

dp = [0] * (N + 1)
dp[0] = 1
not_use = [False] * (N + 1)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        if i < N:
            dp[i + 1] += dp[i]
            dp[i + 1] %= mod
        if i < N - 1:
            dp[i + 2] += dp[i]
            dp[i + 2] %= mod

print(dp[N] % mod)

Solution (Python):
Q = 1000000007
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
dp = {
    0: 1,
    1: 0 if 1 in a else 1
}

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


print(dp[n])

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

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

Solution (Python):

mod = 10**9 + 7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ng = [False] * (10**5 + 1)
for x in a:
    ng[x] = True
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
    if i > 0 and not ng[i - 1]: dp[i] += dp[i - 1]
    if i > 1 and not ng[i - 2]: dp[i] += dp[i - 2]
    dp[i] %= mod
print(dp[n])

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

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

for n in range(1,N+1):
  if n in A:
    ans[n] = 0
  else:
    ans[n] = (ans[n-1] + ans[n-2])%mod

print(ans[N])

Solution (Python):




MOD = 1000000007


N,M = map(int, input().split())
dp = [1 for _ in range(N+1)]
for i 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[-1])

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split())
d = defaultdict(lambda:1)

for i in range(M):
    a = int(input())
    d[a] = 0

mod = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
dp[1] = d[1]
for i in range(N-1):
    dp[i+2] = dp[i+1] + dp[i]
    dp[i+2] *= d[i+2]
    dp[i+2] %= mod
print(dp[N])

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

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n, m = get_li()
    A = get_data(m, [int])
    MOD = 1000000007
    dp = [0] * (n + 2)
    dp[0] = 1
    dp[-1] = 0
    stepable = [True] * (n + 2)
    for a in A:
        stepable[a] = False
    for i in range(1, n + 1):
        if stepable[i]:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    print(dp[n])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
arr=set([int(input()) for _ in range(m)])
dp=[0]*(n+1)
if 1 not in arr:
  dp[1]=1
if n>=2:
  if 2 not in arr:
    dp[2]=dp[1]+1
for i in range(3,n+1):
  if i not in arr:
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n]%1000000007)

Solution (Python):
mod=10**9+7
n,m=map(int,input().split())
A=[int(input()) for _ in range(m)]
A=list(set(A))
A.sort()
DP=[0]*(n+1)
DP[0]=1
if A:
    j=0
    if A[0]!=1:
        DP[1]=1
    else:
        if j<len(A)-1:
            j+=1
    for i in range(2,n+1):
        if i==A[j]:
            if j<len(A)-1:
                j+=1
        else:
            DP[i]=DP[i-1]+DP[i-2]
            DP[i]%=mod
    print(DP[-1])
else:
    DP[1]=1
    for i in range(2,n+1):
        DP[i]=DP[i-1]+DP[i-2]
        DP[i]%=mod
    print(DP[-1])

Solution (Python):
N,M = map(int,input().split())
MOD = 10**9 + 7
a = []
broken = [False for i in range(N+1)]
for i in range(M):
	x = int(input())
	a.append(x)
	broken[x] = True

for i in range(M-1):
	if a[i+1]-a[i] == 1:
		print(0)
		exit()

dp = [0 for i in range(N+1)]
dp[0] = 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]) % MOD
print(dp[N])

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
ans = 1
dp = [0] * (n + 3)
dp[0] = 1
for i in range(n):
    if i + 1 not in a:
        dp[i + 1] += dp[i]
    if i + 2 not in a:
        dp[i + 2] += dp[i]
print(dp[n] % (10 ** 9 + 7))

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m = li()
a = [ni() for _ in range(m)]
aset = set(a)

MOD = 10**9+7

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

for i in range(n):
    if i+1 in aset:
        continue

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

    else:
        dp[i+1] = dp[i] + dp[i-1]
        dp[i+1] %= MOD

print(dp[n])

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

"""



"""
import sys


def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


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


if __name__ == '__main__':
    main(sys.argv[1:])

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

stair = [0 for i in range(N+1)]
notbroken = [1 for i in range(N+1)]
for i in range(M):
    a = int(input())
    notbroken[a] = 0
for i in range(N+1):
    if i == 0:
        stair[i] = 1
        continue
    if i == 1:
        stair[i] = 1
        continue
    stair[i] = (stair[i-1] * notbroken[i-1] + stair[i-2] * notbroken[i-2]) * notbroken[i]
    stair[i] %= 10**9+7

print(stair[N])

Solution (Python):
def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

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

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

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

for i in range(2,N+1):
    if dp[i]==0:
        pass
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[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


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








MOD = 10**9+7

n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}



dp = [0]*(n+10)
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])