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())
DP = [0 for i in range(N+1)]
DP[0]=1
for i in range(M):
    DP[int(input())] = None
for i in range(N):
    if 0<i and DP[i+1]!=None and DP[i-1]!=None:
        DP[i+1]+=DP[i-1]
    if DP[i+1]!=None and DP[i]!=None:
        DP[i+1]+=DP[i]
print(DP[N]%1000000007)

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

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

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

issafe = [True] * (n+1)
for a in ai:
    issafe[a] = False

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] %= 1000000007

print(dp[n])

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

mod = 10 ** 9 + 7
for i in range(M):
    a1 = int(input())
    a[a1] = -1
    
for i in range(2,N+1):
    if a[i] == -1:
        continue
    else:
        a[i] = (max(a[i-1], 0) + max(a[i-2], 0)) % mod
        
print(a[N])

Solution (Python):
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
mod = 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] %= mod
print(dp[n])

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

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

print(dp[N])

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

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


S[0] = 1
i = 1

for a in A:
    while i < a:
        S[i] = (S[i - 1] + S[i - 2]) % MOD
        i += 1
    i += 1

print(S[N])

Solution (Python):
N, M = map(int, input().split())
a_list = set([int(input()) for i 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_list:
    dp[i] = 0
print(dp[N])

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

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

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

check = [1]*(n+1)
check.append(0)
check.append(0)
for i in range(m):
    a = int(input())
    check[a] = 0
    

count = [0]*(n+2)

mod = 10**9+7
if check[0]==1:
    count[0] = 1
    
elif count[0] == 0:
    count[1] = 1

for i in range(1,n+2):
    count[i] += count[i-1] + count[i-2]
    count[i] %= mod
    if check[i] == 0:
        count[i] = 0
    
    
print(count[n]%mod)

Solution (Python):
from sys import stdin
import sys

def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    N, M = rip()
    A = [ri() for i in range(M)]

    fbd = [False] * (N + 1)
    for n in A: fbd[n] = True
    dp = [0] * (N + 1)
    dp[0] = 1
    mod = int(1e9 + 7)
    for i in range(N):
        for j in range(1,3):
            if i + j <= N and not fbd[i + j]:
                dp[i + j] += dp[i]
                if dp[i + j] >= mod: dp[i + j] -= mod
    
    print(dp[N])
    

if __name__ == "__main__":
    main()

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

mod = 1000000007
brok = [False] * (n+1)

for i in a:
    brok[i] = True

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

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

print(dp[0])

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

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for i 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())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if len(alist)>=1 and i ==  alist[0]:
        li[i] = 0
        alist.pop(0)
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))

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

Solution (Python):
from itertools import accumulate
n,m=map(int,input().split())
dp=[0]*(n+1)
List=[int(input()) for i in range(m)]
List.sort()
step=0

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

if(m>0 and List[0]==1):
    dp[1]=0
    step+=1
for i in range(2,n+1):
    
    if(step<m and i==List[step]):
        step+=1
        dp[i]=0
    else:
        dp[i]=dp[i-2]+dp[i-1]


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

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

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

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

def binSearch(broken, e):
    l, r = 0, m-1

    while l <= r:
        mid = (l+r)//2

        if broken[mid] > e:
            r = mid - 1
        elif broken[mid] < e:
            l = mid + 1
        else:
            return True
    return False


for i in range(m):
    b = int(input())
    if broken and b-1 == broken[-1]:
        print(0)
        exit(0)
    broken.append(b)

for i in range(n+1):
    if binSearch(broken, i):
        continue
    if i >= 2:
        stairs[i] = stairs[i-1] + stairs[i-2]
    elif i == 1:
        stairs[i] = stairs[i-1]

print(stairs[-1]%mod)

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

MOD = 1000000007


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

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now] % MOD
                steps[next_] %= MOD
    print(steps[-1])


if __name__ == '__main__':
    main()

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

x = [0] * (n + 5)
mod = 1000000007
x[0] = 1
for i in range(1, n + 1):
    x[i] = x[i - 1] + x[i - 2]
    x[i] %= mod
    if i in a: x[i] = 0
print(x[n])

Solution (Python):
N,M=map(int,input().split())
A=[]
B=[True]*(N+1)
DP=[0]*(N+1)
DP[0]=1
for i in range(M):
  A.append(int(input()))
for i in range(M):
  B[A[i]]=False


for i in range(1,N+1):
  if B[i]==False:
    DP[i]=0
  else:
    if i==1:
      DP[i]=DP[i-1]
    else:
      DP[i]=(DP[i-1]+DP[i-2])%1000000007
if DP[N]==0:
  print(0)
else:
  print(DP[N])

Solution (Python):
N,M=map(int,input().split())
A=[]
B=[True]*(N+1)
DP=[0]*(N+1)
DP[0]=1
for i in range(M):
  A.append(int(input()))
for i in range(M):
  B[A[i]]=False


for i in range(1,N+1):
  if B[i]==False:
    DP[i]=0
  else:
    if i==1:
      DP[i]=DP[i-1]
    else:
      DP[i]=DP[i-1]+DP[i-2]
if DP[N]==0:
  print(0)
else:
  print(DP[N]%1000000007)

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

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

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

ans = S[n]
print(ans)

Solution (Python):
import numpy as np

n, m = map(int, input().strip().split())
array = [int(input()) for _ in range(m)]
is_broken = np.zeros(n + 1, dtype=np.bool)
for a in array:
    is_broken[a] = 1

a0 = 0
a1 = 1

if n == 1:
    if is_broken[n]:
        print(0)
    else:
        print(1)

else:
    for i in range(1, n + 1):
        if is_broken[i]:
            a2 = 0
        else:
            a2 = (a1 + a0) % 1000000007

        a0 = a1
        a1 = a2

    print(a1)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(int)
    for i in range(m):
        d[int(readline())]
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i not in d:
            if i == 1:
                dp[i] += dp[i-1]
            else:
                dp[i] += dp[i-1]
                dp[i] += dp[i-2]
            dp[i] %= mod
    print(dp[-1])


if __name__ == '__main__':
    solve()

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

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

i = -3
for _ in range(n - 1):
    if S[i] != 0:
        S[i] = S[i + 1] + S[i + 2]
    i -= 1

ans = S[0] % (10**9 + 7)
print(ans)

Solution (Python):
N, M=map(int, input().split())
mod = 1000000007
result = [0 for i in range(N+1)]
for j in range(M):
    a = int(input())
    result[a] = -1
result[0] = 1
result[1] = 1 if result[1] != -1 else 0
for i in range(2,N+1):
    if result[i] != -1:
        before1 = result[i-1] if result[i-1] != -1 else 0
        before2 = result[i-2] if result[i-2] != -1 else 0
        result[i] = (before1 + before2) % mod
print(result[-1])

Solution (Python):
from collections import deque

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

comb_stairs = [1]
D = deque(A)

for i in range(1, N + 1):
    if i == 1:
        if len(D) == 0:
            comb_stairs.append(1)
        elif D[0] == 1:
            comb_stairs.append(0)
            D.popleft()
        else:
            comb_stairs.append(1)
    else:
        if len(D) == 0:
            comb_stairs.append(comb_stairs[i - 1] + comb_stairs[i - 2])
        elif D[0] == i:
            comb_stairs.append(0)
            D.popleft()
        else:
            comb_stairs.append(comb_stairs[i - 1] + comb_stairs[i - 2])

print(comb_stairs[-1] % 1000000007)

Solution (Python):
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)

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

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

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

for i in range(m):
    ng = int(input())
    a.append(ng)
    dp[ng] = 0

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

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

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
x = [1] + [0] * N
broken = [False] * (N+1)
mod = 10**9 + 7

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

if not broken[1]:
  x[1] = 1

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

print(x[N])

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

for i in range(1, n+1):
    if i in stairs: 
        dp[i] = 0
        continue

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

print(dp[n])

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

    out = [1]*(N+1)
    for _ in range(M):
        out[int(input())] = 0
        
    for i in range(2, N+1):
        if out[i] == 1:
            out[i] = (out[i-1] + out[i-2])
    return out[-1]%1000000007
    
if __name__ == '__main__':
    print(main())

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for i 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())
mod=10**9+7
dp=[0 for i in range(N+2)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

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

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

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

for i in range(M):
    is_broken[items[i]] = 0

for i in range(N):
    if i-1 >= 0:
        dp[i+1] = dp[i]*is_broken[i] + dp[i-1]*is_broken[i-1]
    else:
        dp[i+1] = dp[i]*is_broken[i]
    dp[i+1] %= mod

print(dp[N])

Solution (Python):

import math
import heapq
import bisect


MOD = 10**9+7

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

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

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

print(ans[N])

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

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

for i in range(2, N+1):
    if li_A[i-1] == 0:
        dp[i] += dp[i-1]
    if li_A[i-2] == 0:
        dp[i] += 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)]
mod=10**9+7
b=[0]*(n+1)
b[0]=1
b[1]=1

for i in a:
    b[i]=-1

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

Solution (Python):


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

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

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

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

print(dp[N])

Solution (Python):
def calculate(n, arr2):
    steps = [0]*(n)
    steps[0] = 1

    if arr2.get(0) == True:
        steps[0] = 0
    else:
        steps[0] = 1

    if n == 1:
        return steps

    if arr2.get(1) == True:
        steps[1] = 0
    else:
        steps[1] = 1 + steps[0]

    if n == 2:
        return steps

    for index in range(2,n):
        if arr2.get(index) == True:
            steps[index] = 0
        else:
            steps[index] = steps[index-1] + steps[index-2]

    return steps

S = input().split(" ")
N = int(S[0])
M = int(S[1])


arr2 = {}
for i in range(M):
    index = int(input())
    arr2.setdefault(index-1, True)

result = calculate(N, arr2)

print(result[N-1] % 1000000007)

Solution (Python):

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

A.insert(0,0)

is_safe=[True]*(N+1)

for a in A:
    is_safe[a]=False

dp=[0]*(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1


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

Solution (Python):
N, M = map(int,input().split())
a = set([int(input()) for i in range(M)])
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2,N+1):
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

Solution (Python):
n,m = map(int, input().split())
mod = 1000000007
broken = [0 for i in range(n+1)]
for j in range(m):
    a = int(input())
    broken[a] = -1
broken[0] = 1
broken[1] = 1 if broken[1] != -1 else 0
for i in range(2,n+1):
    if broken[i] == -1:
        continue
    one = broken[i-1] if broken[i-1] != -1 else 0
    two = broken[i-2] if broken[i-2] != -1 else 0
    broken[i] = (one + two) % mod
print(broken[-1])

Solution (Python):




from copy import deepcopy


def full(shape, full_value):
    if isinstance(shape, tuple):
        if len(shape) == 2:
            return [[full_value] * shape[1] for _ in range(shape[0])]
        else:
            import numpy as np
            return np.full(shape, full_value).tolist()
    else:
        return [full_value] * shape


MOD = 10**9 + 7

N, M = list(map(int, input().split()))
to_zero = full((N + 1), False)
for _ in range(M):
    to_zero[int(input())] = True  


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

print(dp[-1])

Solution (Python):




def full(shape, full_value):
    if isinstance(shape, tuple):
        NotImplementedError()
    else:
        return [full_value] * shape


MOD = 10**9 + 7

N, M = list(map(int, input().split()))
to_zero = full((N + 1), False)
for _ in range(M):
    to_zero[int(input())] = True  


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

print(dp[-1])

Solution (Python):



MOD = 10**9 + 7
import numpy as np

N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False).tolist()
for _ in range(M):
    to_zero[int(input())] = True  


dp = np.full((N + 1), -1).tolist()
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Solution (Python):



MOD = 10**9 + 7
import numpy as np

N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False, dtype=bool)
for _ in range(M):
    to_zero[int(input())] = True  


dp = np.full((N + 1), -1, dtype='int64')
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Solution (Python):



MOD = 10**9 + 7
import numpy as np

N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False, dtype=bool)
for _ in range(M):
    to_zero[int(input())] = True  


dp = np.full((N + 1), -1, dtype='int64')
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[(i - 2):i].sum()
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Solution (Python):



MOD = 10**9 + 7


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


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

    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Solution (Python):



MOD = 10**9 + 7


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


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

    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
mod = (10 ** 9) + 7

arr = [int(input()) for i in range(0, m)]
dp = [0] * (n + 1)
dp[0] = 1

def solve():

  ok = [True] * (n+1)
  for i in range(0, m):
    ok[arr[i]] = False

  for step in range(1, n+1):
    if ok[step] == False:
      dp[step] = 0
    else:
      if step == 1:
        dp[step] = 1
      else:
        dp[step] = dp[step-1] + dp[step-2]

  print(dp[n] % mod)

def main():
  solve()

if __name__ == "__main__":
  main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    n, m, *a = map(int, read().split())
    MOD = 10**9 + 7

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

    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    is_broken = [False] * (n+1)
    for i in a:
        is_broken[i] = True
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1

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

    print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):
from __future__ import print_function

import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return















































def crange(m,n):
    return range(m,n+1)

def main():
    n,m = map(int, input().strip().split())
    a = [0 for _ in range(m)]
    for i in range(m):
       a[i]  = int(input().strip())
    a = set(a)
    
    
    l=[0 for _ in crange(0,n)]
    l[0]=1
    l[1]=0 if 1 in a else 1
    for i in crange(2,n):
        l[i] = 0 if i in a else l[i-2] + l[i-1]
        
        
    print(l[n]%(10**9 + 7))


    return

if __name__ == '__main__':
    main()


'''
find a_cnt such that
for given
n (1<=n<=10**5),
m (0<=m<=n-1),
when m>=1 then 列[a_i] ( 1<=i<=m<=n-1,1<= a[i]<=n-1),

let T := { (i,j) in [0...n]**2 | i + 2*j == n and } 

let 列 B :=[b[i] \in {1,2}] and sum(B)==n and \forall i in [0...].sum(B[0:i]) \notin





n=|T|


'''

Solution (Python):
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0

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

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

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

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

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
mod = int(1e+9 + 7)
A = [-1] + [int(input()) for i in range(M)] + [N+1]
B = []
for i in range(M+1):
  B.append(A[i+1] - A[i] - 1)
C = [0, 1]
for i in range(max(B)):
  C.append(C[i] + C[i+1])
com = 1
for i in range(len(B)):
  com *= C[B[i]] % mod
  com %= mod
print(com)

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

Solution (Python):
n,m = map(int,input().split())
ans = [1]*n

if n == 1:
    print(1)
else:
    for i in range(m):
        a = int(input())
        ans[a-1] = 0

    if ans[0] != 0 and ans[1] != 0:
        ans[0] = 1
        ans[1] = 2

    for i in range(2,n):
        if ans[i] != 0:
            ans[i] = (ans[i-1] + ans[i-2])%1000000007
        
    print(ans[n-1])

Solution (Python):
import numpy as np
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if _next not in A:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

Solution (Python):
import numpy as np
N, M = map(int, input().split())
A = np.ones(N + 2, dtype='bool')
for _ in range(M):
    A[int(input())] = False
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if A[_next]:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

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

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

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

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

for j in range(M):
    b[a[j]]=-1

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

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

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

dp = [0] * 100100
dp[0] = 1
dp[1] = 0 if 1 in A else 1
for i in range(N):
    if i+2 in A:
        continue
    dp[i+2] = dp[i] + dp[i+1]

print(dp[N] % 1000000007)

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

dp = [0] * 101000
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

print(dp[N])

Solution (Python):
import sys

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

dp = [-1]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(M):
    num = int(input())
    dp[num] = 0

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

print(dp[N]%1000000007)

Solution (Python):
MOD = 10**9+7
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
dp = [0] * (N+3)
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])

Solution (Python):

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

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

dp = [0] * (N+1)

dp[0] = 1


if 1 not in a:
    dp[1] = 1
    not_broken_stairs = set(range(2, N+1)) - set(a)
else:
    not_broken_stairs = set(range(1, N+1)) - set(a)    



for i in not_broken_stairs:
    dp[i] = dp[i-2] + dp[i-1]
    
print(dp[-1] % (10 ** 9 + 7))

Solution (Python):
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
a_ls = set()
MOD = 10**9+7
for i in range(m):
    a = int(sys.stdin.readline())
    a_ls.add(a)

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

Solution (Python):


def solve():
	mod = 10 ** 9 + 7
	
	N, M, *a = map(int, open(0).read().split())

	dp = [0] * (N + 2)
	dp[0] = 0 
	dp[1] = 1
	
	
	ok = sorted(set(range(1, N + 1)) - set(a))

	for i in ok:
		dp[i + 1] += (dp[i] + dp[i - 1]) % mod
	print(dp[-1])
solve()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
f = defaultdict(int)
for i in range(m):
    a = I()
    f[a] = 1

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