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] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in [int(input()) for _ in range(m)]:
    dp[i] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])

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

p,q=(0,1)

for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q%(10**9+7))

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

print(dp[-1])

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

Solution (Python):
N,M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))
    
def fibonacci(n):
    listf = [0]+[1]*n
    a, b = 1, 0
    for i in range(n-1):
        a, b = (a+b)%1000000007 , a
        listf[i+2] = a
    return listf 

fib = fibonacci(N+1)
if a:
    ans = [a[0]]
    
    for i in range(M-1):
        ans.append(a[i+1]-a[i]-1)
            

    result = 1
    for j in range(len(ans)):
        result = result * fib[ans[j]] % 1000000007
    
    result = result * fib[(N - a[-1])] % 1000000007
    
    print(result)
else:
    ans = fib[-1]
    print(ans)

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

Solution (Python):
INF = (10 ** 9) + 7
N, M = map(int, input().split())

aLst = set(int(input()) for i in range(M))
ansLst = [0] * (N + 1)
ansLst[0] = 1

for i in range(1, N + 1):
    if i in aLst:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Solution (Python):
INF = (10 ** 9) + 7
N, M = map(int, input().split())

aLst = set(int(input()) for _ in range(M))
ansLst = [0] * (N + 1)
ansLst[0] = 1

for i in range(1, N + 1):
    if i in aLst:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Solution (Python):
N ,M = map(int, input().split())
X = [int(input()) for _ in range(M)]
S = [0] * (N + 1)
dp = [0] * (N + 1)
mod = int(1e9 + 7)

for i in range(M):
	S[X[i]] = -1


for i in range(0, len(X) - 1):
	if X[i + 1] - X[i] == 1:
		print('0')
		exit()

dp[0] = 1
if S[1] != 1: dp[1] = 1

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


print(dp[N])

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

dp = [0]*(n+2)
mod = int(1e9+7)
dp[n] = 1
for i in range(n-1, -1 , -1):
  if broken[i]:
    dp[i] = 0
  else:
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

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

dp = [0]*(n+2)
dp[0] = 1
broken = 0
for i in range(n):
    if broken < len(a) and i == a[broken]:
        broken += 1
    else:
        dp[i+1] = (dp[i+1] + dp[i]) % (10e8+7)
        dp[i+2] = (dp[i+2] + dp[i]) % (10e8+7)
print(int(dp[-2]))

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

if M == 0:
    maxM = N
else:
    maxM = a[0] - 1
    for i in range(1, M):
        maxM = max(maxM, a[i] - a[i-1] - 2)
    maxM = max(maxM, N - a[-1])

dp = [0] * (maxM+1)
dp[1] = 1
if maxM > 1:
    dp[2] = 2
    if maxM > 2:
        for n in range(3, maxM+1):
            dp[n] = (dp[n-1] + dp[n - 2]) % 1000000007

if M == 0:
    print(dp[-1])
    exit()

if a[0] == 1:
    ans = 1
else:
    ans = dp[a[0] - 1]

if M > 1:
    for i in range(1, M):
        if a[i] - a[i - 1] == 1:
            ans = 0
        elif a[i] - a[i - 1] == 2:
            continue
        else:
            ans = ans * dp[a[i] - a[i - 1] - 2] % 1000000007
if N - a[-1] != 1:
    ans = ans * dp[N - a[-1] - 1] % 1000000007
print(ans)

Solution (Python):
import numpy as np
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a_a=np.ones( N+1 )
MOD=7+10**9
for i in range(M):
    a_a[a[i]]=0
c=np.zeros(N+1)
c[0]=1
for i in range(1,N+1):
    if i==1:
        c[i]=c[i-1]*a_a[i-1]
    else:
        c[i]=c[i-1]*a_a[i-1]%MOD+c[i-2]*a_a[i-2]%MOD
print(int(c[N])%MOD)

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

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

print((dp[-1])%MOD)

Solution (Python):
import sys

n,m=map(int,input().split())
c=set(map(int,sys.stdin))

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[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):
s,n=map(int,input().split())
if n>0:
	x=list(int(input()) for _ in range(n))

w0=int(1)
b0=int(0)
cnt=0

for i in range(1,s):
	if n>0 and i==x[cnt]:
		w1=int(0)
		b1=w0
		w0=w1
		b0=b1
		if cnt<n-1: 
			cnt+=1
	else:
		w1=b0+w0
		b1=w0
		w0=w1
		b0=b1

print((w0+b0)%1000000007)

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

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

dp=[1]+[0]*n

j=0

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

Solution (Python):

import logging
logging.basicConfig(level=logging.DEBUG)
logging.disable(logging.CRITICAL)

def main():
    N, M = list(map(int, input().split()))
    dp = [[] for _ in range(N+2)]
    dp[0] = 0
    dp[1] = 1

    for _ in range(M):
        a = int(input())
        dp[a+1] = 0

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

    logging.debug("{}".format(dp))
    return dp[N+1]

if __name__ == '__main__':
    print(main())

Solution (Python):
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
j=0
for i in range(1,N+1):
    if j<M and i==a[j]:
        j+=1
    elif i==1:
        c[i]=1
    else:
        c[i]=(c[i-1]+c[i-2])%MOD
print(c[-1]%MOD)

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

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

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

Solution (Python):
n,m= map(int, input().split())
if m!=0:
  a = [int(input()) for _ in range(m)]
else:
  a=[0]
dp=[0]*(n+1)
dp[0]=1
j=0

for i in range(1,n+1):
    if i==a[j]:
        if j<m-1:
            j+=1
    else:
        if i==1:
            dp[i]=1
        else:
            dp[i]=dp[i-1]+dp[i-2]

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

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



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

    
  print(A[n-1])
  
else:print(1)

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

Solution (Python):

mod = 1000000007
 
n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False
 
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod


print(dp[n])

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

Solution (Python):


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





p = [0] * (N + 1)
p[0] = 1
for i in A:
    p[i] = -1

for i in range(N):
    if p[i] < 0: continue
    if p[i + 1] >= 0:
        p[i + 1] += p[i]
    if i < N - 1 and p[i + 2] >= 0:
        p[i + 2] += p[i]
    

print(p[-1] % 1000000007)

Solution (Python):

import sys
input = sys.stdin.readline
 
def main():
    N, M = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])
 
 
if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    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
input = sys.stdin.readline

def main():
    n, m = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(m)]))
    MOD = 10 ** 9 + 7
    a, b = 1, 1 if not 1 in A else 0
    for i in range(2, n + 1):
        if i in A:
            a, b = b, 0
        else:
            a, b = b, (a + b) % MOD
    print(b)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    A = set(map(int, [input() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() for _ in range(M)]))
    MOD = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if 1 not in A else 0
    for i in range(2, N + 1):
        if i in A:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() 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
        else:
            for j in range(1, 3):
                if i - j >= 0:
                    dp[i] = (dp[i] + dp[i - j]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().rstrip().split()))
    A = set(map(int, [input().rstrip() 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
        else:
            for j in range(1, 3):
                if i - j >= 0:
                    dp[i] = (dp[i] + dp[i - j]) % MOD
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):

mod = 1000000007

n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False

dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod


print(dp[n])

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

Solution (Python):
temp=input().split()
N=int(temp[0])
M=int(temp[1])

index=[int(1) for i in range(N)]
for i in range(M):
  index[int(int(input())-1)]=0

temp=[0, 1]
for i in range(N):
  if index[i]==1:
    temp=[temp[1], temp[0]+temp[1]]
  else:
    temp=[temp[1], 0]
    
print(temp[1]%1000000007)

Solution (Python):

N, M = (int(_) for _ in input().split())
a = [0 for i in range(M)]
MOD = 10 ** 9 + 7
for i in range(M):
    a[i] = int(input())
a.append(0)
dp = [0 for i in range(N + 1)]
j = 0
for i in range(N + 1):    
    if i == a[j] and M != 0:
        j += 1
    elif i == 0:
        dp[i] = 1
    elif i == 1:
        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 i in range(m)]
broken = set(a)
dp=[0]*(n+1)
mod = 10**9 + 7

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

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

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

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

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

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

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

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

Solution (Python):
from collections import defaultdict

MOD = 1000000007


def main():
    n, m = list(map(int, input().split()))
    stairs = defaultdict(lambda: True)
    for i in range(m):
        a = int(input())
        stairs[a] = False

    dp = defaultdict(lambda: 0)
    dp[0] = 1

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

    print(dp[n])


main()

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

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

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

ans = 1
for i in range(m):
    if a[i+1]-a[i]-1 == 0:
        ans = 0
        break
    elif a[i+1]-a[i]-1 == 1:
        continue
    else:
        dp = [1] + [0]*(a[i+1]-a[i]-2)
    for j in range(1, a[i+1]-a[i]-1):
        dp[j] = dp[j-1] + dp[j-2]
    ans *= dp[-1]

print(ans%1000000007)

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

broken = [False] * (n + 1)
for x in xs:
    broken[x] = True

cache = [-1] * (n + 1)

def solve(pos, n, broken, cache):
    if pos > n or broken[pos]:
        return 0
    if pos == n:
        return 1
    res = cache[pos]
    if res >= 0:
        return res
    res = solve(pos+1, n, broken, cache) + solve(pos+2, n, broken, cache)
    cache[pos] = res = res % 1000000007
    return res

for tmp in range(n,0,-1):
    solve(tmp,n,broken,cache)

print(solve(0,n,broken,cache))

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

broken = [0] * N
for i in range(M):
    broken[int(input())] = 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]

print(dp[0] % MOD)

Solution (Python):
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

Solution (Python):
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

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

cs = []
for i in range(m + 1):
    c = bs[i+1] - bs[i] - 2
    if (c < 0):
        print(0)
        exit()
    cs.append(bs[i+1] - bs[i] - 2)
mc = max(cs)

ds = [1, 1, 2]
for i in range(mc + 1):
    if i < 3:
        continue
    ds.append(ds[i-1] + ds[i-2])

r = 1
for c in cs:
    r *= ds[c]

print(r % 1000000007)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)









N, M = LI()
A = set([_I() for i in range(M)])














"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""

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

dp[0] = 1
dp[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]
        dp[i] %= mod

print(dp[N])

Solution (Python):

import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

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

print(dp[-1])

Solution (Python):
mod = 1000000007
N,M = list(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]%mod)

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


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = 1
        else:
            dp[i] = 1
    else:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] = dp[i] % 1000000007
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)

Solution (Python):


import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)



for i in range(0,m):
	tmp = int(input())
	a[tmp]=0




for i in range(2,n):
	a[i]=a[i]*(a[i-1]+a[i-2])


if(n==1):
	print(1)
else:
	print((a[n-1]+a[n-2])% 1000000007)

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):
import sys
sys.setrecursionlimit(10**9)

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

set_inputs = set(inputs)
mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in set_inputs:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        if i - 1 not in set_inputs:
            dp[i] += dp[i-1]
        if i - 2 not in set_inputs:
            dp[i] += dp[i-2]

print(dp[-1] % mod)

Solution (Python):
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	fib = [0,1,1,2]
	for i in range(3,10**5+100):
		fib.append(fib[i-1]+fib[i])
	n,m = map(int,input().split())
	last = 0
	ans = 1
	a =  []
	for i in range(m):
		a.append(int(input()))
	for t in a:
		ans *= fib[t-last]
		last =  t+1
	ans *= fib[n-last+1]
	print(ans%(10**9+7))


def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

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

m = len(a)

diffs = []
for i in range(m-1):
    diffs.append(a[i + 1] - a[i] - 2)
diffs.sort()

fibs = []
for i in range(0, max(diffs) + 1):
    if i == 0:
        fibs.append(1)
    elif i == 1:
        fibs.append(1)
    else:
        fibs.append(fibs[-1] + fibs[-2] % 1000000007)

def func(k):
    if (k == -2):
        return 1
    elif (k == -1):
        return 0
    else:
        return fibs[k]

ans  = 1
for i in range(len(diffs)):
    ans = ans * func(diffs[i]) % 1000000007

print(ans)

Solution (Python):




n, m = map(int, input().split())
step_count = [0 for _ in range(n+1)]
ng_step = [False for _ in range(n+1)]
for _ in range(m):
  ng = int(input())
  ng_step[ng] = True

for i in range(n+1):
  if ng_step[i]:
    step_count[i] = 0
  else:
    if i==1:
      step_count[i] = 1
    elif i==2:
      step_count[i] = 1 + step_count[i-1]
    else:
      step_count[i] = (step_count[i-2]+step_count[i-1])%(10**9+7)

print(step_count[-1])

Solution (Python):
n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, 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 = {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):
MOD = 10**9 + 7

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

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

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

for _ in range(m):
    broken[int(input())] = 1

dp[0] = 1

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

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

print(dp[n])

Solution (Python):
N, M = list(map(int, input().split()))
As = set()
for i in range(0, M):
    As.add(int(input()))
C = 10 ** 9 + 7

dp = [0 for _ in range(N + 1)]
dp[0] = 1
dp[1] = 0 if 1 in As else 1

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

print(dp[N])

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

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

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

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

ans = [0]*(n+1)
for j in range(n+1):
  if j in l:
    ans[j] = 0
  else:
    if j == 0:
      ans[j] = 1
    elif j == 1:
      ans[j] = ans[j-1]
    else:
      ans[j] = ans[j-1] + ans[j-2]
print(ans[-1]%1000000007)

Solution (Python):
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
if m == 0:
    a.append(-1)
j = 0
k = len(a)-1
if 1 == a[j]:
    dp.append(0)
    j = min(k,j+1)
else:
    dp.append(1)

for i in range(2,n+1):
    if i == a[j]:
        dp.append(0)
        j = min(k,j+1)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))

Solution (Python):

import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

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

print(dp[-1])