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())
broken=[int(input()) for i in range(m)]
mod=10**9+7

is_broken=[True]*(n+1)
for i in range(m):
  is_broken[broken[i]]=False
   
dp=[0]*(n+1)
dp[0]=1
if is_broken[1]:
  dp[1]=dp[0]
  
for i in range(2,n+1):
    if is_broken[i]:
       dp[i]=dp[i-1]+dp[i-2]
       dp[i]%=mod
    else:
      dp[i]=0
      
print(dp[n])

Solution (Python):
def fibonacci(n):
    if n<0:
        return 0
    else:
        a=1
        b=1
        if n==0:
            return a
        elif n==1:
            return b
        else:
            i=n-2
            while i>=0:
                x=a
                a=b
                b=x+b
                i=i-1
            return b

N,M=map(int,input().split())
a=[]
for _ in range(0,M):
    a.append(int(input()))
a.append(N+1)
m=1
for i in range(0,M+1):
    if i==0:
        m=fibonacci(a[i]-1)
    else:
        m=m*fibonacci(a[i]-a[i-1]-2)

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

Solution (Python):
Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)

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

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

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9+7
N,M = [int(i) for i in input().split()]
a = [0] * M
for i in range(M) :
    a[i] = int(input())
dp = [0] * (N+1)
dp[0] = 1
A = set(a)
for i in range(1,N+1) :
    if i in A:
        continue
    else :
        if i == 1 :
            dp[i] += dp[i-1]
        else :
            dp[i] = dp[i-1] + dp[i-2]
print(dp[N] % mod)

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

fl = [True]*N
for i in range(M):
    fl[a[i]] = False
dp = [0]*(N+1)
dp[0] = 1

for i in range(1,N+1):
    if i>0 and fl[i-1]:
        dp[i] += dp[i-1]%MOD
    if i>1 and fl[i-2]:
        dp[i] += dp[i-2]%MOD
print(dp[N]%MOD)

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

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

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

for i in range(n):
   if (b[i] != -1):
      if (b[i+1] != -1):
         b[i+1] += b[i]
      if (b[i+2] != -1):
         b[i+2] += b[i]

print(b[n] % 1000000007)

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

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

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

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

print(dp[n])

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

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

Solution (Python):
def main(N,M,a):
    dp = [-1]*N
    dp[0] = 1
    if N != 1:
        dp[1] = 2
    for i in a:
        if i == 1:
            dp[0] = 0
            dp[1] = 1
        else:
            dp[i-1] = 0
    for i in range(2,N):
        if dp[i] != 0:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]
N,M = map(int, input().split())
a = list(int(input()) for i in range(M))

print(main(N,M,a) % 1000000007)

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

dp = [999] * (n + 1)
if 0 not in a:
    dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a and n >= 2:
    if 1 in a:
        dp[2] = 1
    else:
        dp[2] = 2

mod = 10**9+7

for i in range(len(a)):
    dp[a[i]] = 0

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

print(dp[-1])

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

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

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

print(dp[N])

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

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


dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

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

print(dp[N-1]%1000000007)

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

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


dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

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

print(dp[N-1]%1000000007)

Solution (Python):
n,m=map(int,input().split())
broken=[False for i in range(n+1)]
for i in range(m):
    a=int(input())
    broken[a]=True
ans=[1]
if broken[1]:
    ans.append(0)
else:
    ans.append(1)
for i in range(2,n+1):
    if broken[i]:
        ans.append(0)
    else:
        ans.append((ans[i-1]+ans[i-2])%1000000007)
print(ans[n])

Solution (Python):

def main(N, M, a):
    dp = [-1] * (N+1)
    dp[0] = 1
    dp[1] = 1
    for i in a :
        dp[i] = 0
    for i in range(2, len(dp)):
        dp[i] = dp[i-1] + dp[i-2] if dp[i] != 0 else 0
    return dp[-1] % (10**9+7)

N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))
print(main(N,M,a))

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

for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()
dp=[0]*(n+1)
dp[0]=1

for i in range(1,n+1):
    if len(a)!=0 and i == a[0]:
        dp[i]=0
        a.pop(0)
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i] = dp[i] % (10**9+7)

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

Solution (Python):
def calculate(n, bindexes):
    arr = []
    for i in range(n):
        if bindexes.get(i):
            arr.append(0)
            continue

        if i == 0:
            arr.append(1)
        elif i == 1:
            arr.append(arr[i-1] + 1)
        else:
            arr.append(arr[i-1] + arr[i-2])
    return arr

S = input().split(" ")

n = int(S[0])
m = int(S[1])
brokenStairIndexes = {}

for i in range(m):
    brokenStairIndexes.setdefault(int(input())-1, True)


arr = calculate(n,brokenStairIndexes)

print(arr[n-1] % 1000000007)

Solution (Python):
n, m = map(int, input().split())
s = 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 s:
        continue
    x = dp[i - 1]
    if i > 1:
        x += dp[i - 2]
    dp[i] = x % MOD

print(dp[n])

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

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

for i in range(n - 1):
    dp[i + 2] = dp[i + 1] + dp[i]
mae = 0
ans = 1
for i in s:
    if i == mae:
        ans=0
    else:
        ans *= dp[i - 1 - mae]

    mae = i + 1
print(ans % (10 ** 9 + 7))

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

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

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

dp = [1] * (n + 10)
for i in range(len(a)):
    dp[a[i]] = 0

for i in range(n + 1):
    if i == 0 or i == 1:
        dp[i] = dp[i] * 1
    else:
        dp[i] = dp[i] * (dp[i - 2] + dp[i - 1])

print(dp[n] % 1000000007)

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

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

print(dp[n]%mod)

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

dp=[True]*(N+2)
S=list(int(input()) for _ in range(M))
for i in S:
    dp[i]=False
num=[0]*(N+2)
MOD=1000000007
num.insert(0,1)
for i in range(0,N):
    if dp[i]:
        num[i+1]+=num[i]
        num[i+1]%=MOD
        num[i+2]+=num[i]
        num[i+2]%=MOD
print(num[N])

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

Solution (Python):

n,m=map(int,input().split())
broken=[False for i in range(n+1)]
const=1000000007
for i in range(m):
    a=int(input())
    broken[a]=True
n_way=[1,1]
if broken[1]:
    n_way=[1,0]
for i in range(2,n+1):
    if not broken[i] :
        n_way.append((n_way[i-1]+n_way[i-2])%const)
    else:
        n_way.append(0)
print(n_way[n])

Solution (Python):


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

stairs = [i for i in range(1, n+1)]
a = [0 for _ in range(m)]
for i in range(m):
  a[i] = int(input())
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
    dp[i] = dp[i] + dp[i-1]
    if i > 1:
        dp[i] = dp[i] + dp[i-2]


print(dp[-1]%mod)

Solution (Python):
import sys

N, M = list(map(int, input().split()))
if M == 0:
  h = []
else:
  h = sys.stdin.readlines()
  h = set(map(int, list(set(h))))

if N==1:
  print(1)
elif N==2:
  if M==1:
    print(1)
  else:
    print(2)
else:
  DP = []
  DP.append(1)
  if 1 in h:
    DP.append(-1)
  else:
    DP.append(1)
  for i in range(2,N+1):
    if DP[i-2]<0 and DP[i-1]<0:
      print(0)
      exit()
    DP.append(0)
    if i in h:
      DP[i] = -1
    else:
      if DP[i-1]>=0:
        DP[i] += DP[i-1]
      if DP[i-2]>=0:
        DP[i] += DP[i-2]
      DP[i] = DP[i] % 1000000007
  print(int(DP[N]))

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

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

print(dp[n] % 1000000007)

Solution (Python):

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[0]*M
dp=[-1]*(N+1)
for i in range(M):
    tmp=int(input())
    dp[tmp]=0

dp[0]=1
dp[1]=0 if dp[1]==0 else 1

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

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

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

t2 = 0
t1 = 1

for i in range(1,n+1):
  if l == [] or i != l[0]:
    t0 = (t2+t1)%mod
  else:
    l.pop(0)
    t0 = 0
  t2 = t1
  t1 = t0

print(t0)

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

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

t, s = 1, 0

for i in range(n):
  if l[i]:
    t, s = 0, t
  else:
    t, s = (s+t)%mod, t

print(t)

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

s = 0
t = 1

for i in range(n):
  if l[i] > 0:
    t, s = 0, t
  else:
    t, s = (s+t)%mod, t

print(t)

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

t2 = 0
t1 = 1

for i in range(1,n+1):
  if l == [] or i != l[0]:
    t0 = (t2+t1)%mod
  else:
    l.pop(0)
    t0 = 0
  t2 = t1
  t1 = t0

print(t0)

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

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

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

Solution (Python):




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

Solution (Python):
MOD = 1e9 + 7

N, M = [int(i) for i in input().split()]
issafe = [True] * (N + 1)
for i in range(M):
    a = int(input())
    
    issafe[a] = False


dp = [0] * (N + 1)

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

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

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

n, m = map(int, inputs[0].split())
B = set(map(int, inputs[1:]))
A = [0 if i in B else 1 for i in range(n+3)]
MOD = 10 ** 9 + 7

dp = [0]*(n+1)
dp[0], dp[1] = 1, A[1]
for i in range(1, n):
    dp[i+1] = (dp[i] + dp[i-1]) * A[i+1] % MOD
    if A[i] + A[i+1] == 0:
        break
print(dp[n])

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

Solution (Python):

import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

MOD = int(1e09) + 7

def main():
    N ,M = cin.mapInt()
    A = [True] * (N + 1)
    for i in range(M):
        a = cin.int()
        A[a - 1] = False

    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        if A[i] == True:
            dp[i + 1] = dp[i] + dp[i - 1]
            dp[i + 1] %= MOD
    print(dp[N])
    return

if __name__ == "__main__":
    main()

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

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


print(dp[-1]%1000000007)

Solution (Python):
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 not in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[True for _ in range(n+1)]
  for _ in range(m):
    l[I()]=False

  dp=[0 for _ in range(n+1)]
  dp[0]=1
  for i in range(n):
    for j in range(1,3):
      if i+j<=n and l[i]:
        dp[i+j]+=dp[i]

  
  return dp[n]%mod


print(main())

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

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

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

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

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

print(dp_table[n])

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

stairs =[1, 1] + [0] * (n - 1)

for _ in range(m):
  stairs[int(input())] = "broken"
  
for i in range(2, n + 1):
  if stairs[i] != "broken":
    if stairs[i - 2] != "broken":
      stairs[i] += stairs[i - 2]
    if stairs[i - 1] != "broken":
      stairs[i] += stairs[i - 1]

print(stairs[-1] % 1000000007)

Solution (Python):
import numpy as np
n, m = map(int, input().split())
stairs = set([int(input()) for i in range(m)])
ans = [1] * (n+1)
mod = 10**9 + 7
if 1 in stairs:
    ans[1] -= 1
for i in range(2, n+1):
    if i in stairs:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]

print(ans[-1]%mod)

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

Solution (Python):
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    nums = []
    
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            
            continue

        if i == 0:
            nums.append(1)
            
        elif i == 1:
            
            nums.append(nums[-1] + 1)
            
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
            
    return nums[-1]


print(solve(n, hole_ids))

Solution (Python):
n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            
            nums[i] = 0
            continue

        if i == 0:
            
            nums[i] = 1
        elif i == 1:
            
            
            nums[i] = nums[i-1] + 1
        else:
            
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))

Solution (Python):


MOD = int(1e9+7)

def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    broken = [0]*(n+1)
    for i in a:
        broken[i] = 1; 

    dp = [0]*(n+2)
    dp[n] = 1
    for i in reversed(range(n)):
        if broken[i]:
            dp[i] = 0;
            continue; 
        dp[i] = (dp[i+1] + dp[i+2]) % MOD

    print(dp[0])
main()

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

mod = int(1e9+7)

dp = [0]*N

if N == 1:
    print(1)
    exit()

if a[0] and a[1]:
    dp[0] = 1
    dp[1] = 2
elif not a[0] and a[1]:
    dp[1] = 1

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

print(dp[N-1]%mod)

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

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

ls.append(0)

if ls[0] == 1:
	dp[1] = 0
	del ls[0]
else:
	dp[1] = 1

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

print(dp[n] % 1000000007)

Solution (Python):
MOD = 1e9 + 7

n, m = map(int, input().split())
a = [False] * (n+1)
for i in range(m):
    b = int(input())
    a[b] = True

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

print(int(dp[n]))

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


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

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

MOD = 10**9 + 7

dp = [0] * (n+1)
flag = [False] * (n+1)
for i in a:
    flag[i] = True

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

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

print(dp[-1])

Solution (Python):
def main():
    n,m = map(int,input().split())
    a = [-1]
    d = 10**9+7
    for i in range(m):
        a.append(int(input()))
    a.append(n+1)
    fib = [1,1]
    for i in range(n):
        fib.append(fib[-2]+fib[-1])
    ans = 1
    for i in range(m+1):
        x = a[i+1]-a[i]-2
        if x == -1:
            ans = 0
            break
        ans = ans*fib[x]%d
    print(ans)
    
if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7

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

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

Solution (Python):
import sys
from collections import deque
 
def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])
 
    atmp = -1
    if len(a) != 0:
        atmp = a.popleft()
 
    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue
 
        if i == 0 or i == 1:
            dp[i] = 1
            continue
 
        if dp[i-1] == 0 and dp[i-2] == 0:
            break
 
 
        dp[i] = dp[i-1] + dp[i-2]
 
    print(dp[N] % 1000000007)
 
if __name__ == '__main__':
    main()

Solution (Python):
dp = [0]*(10**6)

N,M = map(int, input().split())
A = {}
for i in range(N+1):
    A[i] = 0
for _ in range(M):
    a = int(input())
    A[a] = 1

dp[0] = 1

for i in range(1,N+1,1):

    if A[i]==1:
        continue
    if i==1:
        dp[i] += dp[i-1]
        continue
    if A[i-1]==0:
        dp[i] += dp[i-1]
    if A[i-2]==0:
        dp[i] += dp[i-2]


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

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

fib=[1]*(N+1)
for i in range(2,N+1):
    fib[i]=fib[i-1]+fib[i-2]
fib.append(0)

ans=fib[a[0]-1]
for i in range(M):
    ans*=fib[a[i+1]-a[i]-2]
    ans%=mod
print(ans%mod)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 1000000007
    n, m = map(int, input().split())
    a = {int(input()) for _ in range(m)}

    dp = [0] * (n+1)
    dp[:2] = 1, 1 if 1 not in a else 0

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

if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
DP = [0] * (N+1)
F = [True] * (N+1)
ANS = -1

BC=-1
for i in range(M):
  f = int(input())
  if BC == f - 1:
    print(0)
    exit(0)
  BC = f
  F[f] = False

DP[0] = 1
if F[1]:
  DP[1] = 1
for i in range(2, N+1):
  if F[i - 1]:
    DP[i] += DP[i-1]
  if F[i-2]:
    DP[i] += DP[i-2]
A = 1000000007


print(DP[N] % A)

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

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

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

safe = [True] * (n + 1)
for _ in range(m):
  safe[int(input())] = False
dp = [0] * (n + 1)

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

for i in range(2, n + 1):
  if safe[i - 1]:
    dp[i] += dp[i - 1]
  if safe[i - 2]:
    dp[i] += dp[i - 2]
  dp[i] %= 1000000007
 
print(dp.pop())

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

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

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

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


mod = 10**9+7
print(dp[n+1]%mod)

Solution (Python):

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

if N == 1:
    print(1)
    exit()
if N == 2:
    if M == 0:
        print(2)
    if M == 1:
        print(1)
    exit()

safe = [True] * (N+1)
for i in range(M):
    safe[A[i]] = False 

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

if 1 in A:
    dp[1] = 0
    dp[2] = 1
if 2 in A:
    dp[2] = 0

for i in range(3, N+1):
    if safe[i]:
        dp[i] = dp[i-1] + dp[i-2]


print((dp[N]+mod)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
mod = 10 ** 9 + 7


fib_memo = {}
def fib(N):
    if N < 2: return 1
    if N not in fib_memo:
        fib_memo[N] = fib(N-1) + fib(N-2)
    return fib_memo[N]

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

tmp_list = [0] * (M+1)
now_kaidan = 0
for i in range(M):
    tmp_list[i] = (A[i] - 1) - now_kaidan
    now_kaidan = A[i] + 1
tmp_list[-1] = N-now_kaidan
ans = 1

for v in tmp_list:
    if v == -1:     
        print(0)
        exit()
    ans *= fib(v)
    ans %= mod

print(ans%mod)

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())
brokensteps = set([int(input()) for x in range(m)])
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)

print(dp[n])

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

bs = [True for i in range(N+1)]
for i in range(M):
    a = int(input())
    bs[a] = False

dp = [0 for i in range(N+1)]
dp[0] = 1
if bs[1] != False: dp[1] = 1

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

print(dp[N] % 1000000007)

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

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

print(r[n])

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

up = [0]*(m+1)
if m == 0:
  up[0] = n
else:
  up[0] = a[0]-1
  up[m] = n - a[m-1]-1
  for i in range(m-1):
    up[i+1] = a[i+1]-a[i]-2

ans = 1
if -1 in up:
  ans = 0
else:
  f = [0]*(max(up)+1)
  f[0] = 1
  if max(up) > 0:
    f[1] = 1
    for i in range(2, max(up)+1):
      f[i] = f[i-1] + f[i-2]
  for i in range(m+1):
    ans *= f[up[i]]

print(ans % 1000000007)

Solution (Python):
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

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

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

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

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


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

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

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

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

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

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


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

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    dp = [0] * (n+1)
    dp[:2] = 1, 1 if 1 not in a else 0

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def pl(n):
    if n > 0:
        return n
    else:
        return 0

def main():
    MOD = 1000000007
    n, m = map(int, input().split())

    dp = [0] * (n+1)
    dp[0] = 1
    
    for _ in range(m):
        dp[int(input())] = -1

    for i in range(1, n+1):
        if dp[i] < 0:
            continue
        dp[i] += pl(dp[i-1])
        if i >= 2:
            dp[i] += pl(dp[i-2])
        dp[i] %= MOD
    print(max(dp[-1], 0))

if __name__ == '__main__':
    main()