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

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

dp[0] = 1
if dp[1] != -1:
    dp[1] = 1 
else:
    dp[1] = 0

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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 not in A:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])

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

mod=10**9+7

dp=[0]*(N+1)

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

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

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

Solution (Python):


N,M=map(int,input().split())
l=list(range(N+1))

res=[1,1]
for i in range(10**5):
    res.append(res[-1]+res[-2])

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if a==start:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

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

mod = 10 ** 9 + 7

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


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

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

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

print(dp[n])

Solution (Python):
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

stair_list = [0] * (N + 2)

stair_list[0] = 1
a_s = set(a)
for i in range(N):
    if not i in a_s:
        stair_list[i + 1] += stair_list[i]
        stair_list[i + 2] += stair_list[i]


print(stair_list[N] % MOD)

Solution (Python):
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

dict = defaultdict(int)

dict[0] = 1
a_s = set(a)
for i in range(N):
    if not i in a_s:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]


print(dict[N] % MOD)

Solution (Python):
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

dict = defaultdict(int)

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

dict[0] = 1
a_s = set(a)
for i in range(N):
    if not i in a_s:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]


print(dict[N] % MOD)

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

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

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

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

Solution (Python):
import sys
N,M = map(int,input().split())
As = [int(input()) for e in range(M)]

if N == 1:
    if 1 in As:
        print(0)
    else:
        print(1)
    sys.exit()

 
if 1 in As and 2 in As:
    print(0)
    sys.exit()
 
if 1 in As and 2 not in As:
    patterns = [0,1]
 
if 1 not in As and 2 in As:
    patterns = [1,0]
 
if 1 not in As and 2 not in As:
    patterns = [1,2]
 
flags = [0 for _ in range(N)]
for e in As:
    flags[e] = 1
for i in range(3,N+1):
    value = 0
    if not flags[i-2]:
        value += patterns[i-3]
    if not flags[i-1]:
        value += patterns[i-2]
    patterns.append(value%1000000007)
print(patterns[-1]%1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    fib=[0,1]
    a,b=0,1
    for _ in range(n):
        a,b=b,(a+b)%MOD
        fib.append(b)
    A=[-1]+[int(input()) for _ in range(m)]+[n+1]
    ans=1
    for i in range(m+1):
        ans*=fib[A[i+1]-A[i]-1]%MOD
    print(ans%MOD)

resolve()

Solution (Python):
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = [INT() for _ in range(m)]


def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

start = 0
ans = 1

for k in a:
    tmp = k-start
    if tmp==0:
        print(0)
        exit(0)
    ans *= fib(tmp)
    ans%=MOD
    start = k+1

ans*=fib(n-start+1)
ans%=MOD

print(ans)

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

print(dp[-1])

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

print(dp[-1])

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

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

for i in range(m):
    a = int(input())
    b[a] = True

dp[n] = 1
mod = 10**9+7

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

print(dp[0])

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    a = {int(input().rstrip('\n')): 0 for _ in range(m)}
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in a else 0
    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]) % mod
        else:
            dp[i] = 0
    print(dp[-1])


if __name__ == '__main__':
    slove()

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())
D = [1]*(N+1) 
MOD = 10**9 + 7

for _ in range(M):
    D[int(input())] = 0

for i in range(N+1):
    if i <2 or D[i] == 0:
        continue
    D[i] = (D[i-1] + D[i-2]) % MOD

print(D[i])

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

Solution (Python):
N,M=map(int,input().split())
A=[]
B=[]
a=[]
a.append(0)
x=0
d=1
A.append(1)
A.append(2)
B.append(1)
B.append(1)
for j in range(2,N):
    A.append(A[j-1]+A[j-2])
    B.append(B[j-1]+B[j-2])
for i in range(1,M+1):
    a.append(int(input()))
    if a[i-1]==0:
        if a[i]==1:
            d=1
        else:
            x=A[a[i]-a[i-1]-2]
            d=d*x%(10**9+7)
    else:
        x=B[a[i]-a[i-1]-2]
        d=d*x%(10**9+7)
    if i>1:
        if a[i]-a[i-1]==1:
            d=0
c=N-a[M]
if c==1:
    print(d)
elif c==N:
    x=A[c-1]
    d=d*x%(10**9+7)
    print(d)
else:
    x=A[N-a[M]-2]
    d=d*x%(10**9+7)
    print(d)

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

stairs = [0] * (n+1)
broken_stairs = [0] * (n+1)

stairs[0] = 1

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

for i in range(n):
    if broken_stairs[i+1] == 0:
        stairs[i+1] += stairs[i]
    if i >= n-1:
        break
    if broken_stairs[i+2] == 0:
        stairs[i+2] += stairs[i]

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

Solution (Python):
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1
broken_a = np.zeros(N)
for a_ in a:
    broken_a[a_] = 1
if broken_a[N-1] != 1:
    ans[N - 1] = 1


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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.append(n+1)
seq = [a[0]]

for i in range(m):
    d = a[i+1] - a[i] - 1
    if d == 0:
        print(0)
        sys.exit()
    seq.append(d)

memo = [-1] * (10**5 + 7)
def fib(i):
    if i == 0: return 0
    elif i == 1: return 1
    elif memo[i] != -1: return memo[i]
    else:
        memo[i] = fib(i-1) + fib(i-2)
        return memo[i]

ans = 1
for s in seq:
    ans *= fib(s)
print(ans % 1000000007)

Solution (Python):
N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] 
C += [0]*(N+10) 
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: 
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: 
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)

Solution (Python):
import sys


okkiikazu=1000000007


		
def main():
	b , c = map(int, input().split())
	al=[int(input()) for _ in range(c)]
	al=set(al)
	rr=[0]*(b+1)
	rr[0]=1
	for i,_ in enumerate(rr):
		cc=rr[i] 
		for j in range(2):
			vv=i+1+j
			if (not (vv in al)) and (vv)<=b:
				rr[vv] += cc
		
	print(rr[-1] % okkiikazu)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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

    A = [int(input()) for _ in range(M)]

    stair_status = [True for _ in range(N+1)]

    for i in A:
        stair_status[i] = False 

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

    dp[0] = 1

    for i in range(N):
        if i +1 <= N and stair_status[i + 1]:
            dp[i+1] += dp[i]
        if i + 2 <= N and stair_status[i + 2]:
            dp[i+2] += dp[i]

    print(dp[N] % 1000000007)

        


    
if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
count = [0 for _ in range(n+1)]
count[1] = 1
count[0] = 1
for num in a:
  count[num] = -1

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

Solution (Python):
import sys

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

for i in range(m):
  analist[a[i]-1]="ana"

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    sys.exit()
if 1 in a:
  nlist.append(0)
  nlist.append(1)
elif 2 in a:
  nlist.append(1)
  nlist.append(0)
else:
  nlist.append(1)
  nlist.append(2)

for i in range(2,n):
  if analist[i]=="ana":
    nlist.append(0)
  else:
    nlist.append((nlist[i-1]+nlist[i-2])%1000000007)
print(nlist[n-1]%1000000007)

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(0, N, 1):

    if i+1 == 1 and not (i+1) in A:
        dp[i+1] = dp[i]
    elif not (i+1 in A) and not(i in A) and not(i-1 in A):
        dp[i+1] = dp[i] + dp[i-1] 
    elif not(i+1 in A) and not (i in A) and (i-1 in A):
        dp[i+1] = dp[i]
    elif not(i+1 in A) and (i in A) and not(i-1 in A):
        dp[i+1] = dp[i-1] 

print(dp[N]%1000000007)

Solution (Python):

N,M = (int(i) for i in input().split())
a = [0] * M
mod = 1000000007
for i in range(M):
    a[i] = int(input())
a.append(100000000)
flag = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break

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

for i in range(N-1):
    if i+1 == a[tmp]:
        dp[i+2] = dp[i]
    elif i == a[tmp]:
        dp[i+2] = dp[i+1]
        tmp += 1
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])

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

A    = set([int(input()) for _ in range(M)])

dp = [0]*(N+3)



for i in range(N+1):

    if i==0:
        if not (i+1) in A:
            dp[i+1] = 1 + dp[i]
        if not (i+2) in A:
            dp[i+2] = 1 + dp[i]
        continue 
    if not i+1 in A:
        dp[i+1] = dp[i] + dp[i+1]
    if not i+2 in A:
        dp[i+2] = dp[i] + dp[i+2]

print(dp[N]%(1000000007))

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

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



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

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

Solution (Python):

def main():
    N,M = map(int,input().split())
    A = set([int(input()) for _ in range(M)])
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print(ans[N] % MOD)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N, M = map(int, input().split())
A = [0] * M
dp = [-1] * (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])

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N, M = map(int, input().split())
A = [0] * M
dp = [-1] * (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]

print(dp[N] % 1000000007)

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = dict([[int(input().rstrip('\n')), 0] for _ in range(m)])
    x = [0] * (n + 1)
    x[0] = 1 if 0 not in a else 0
    x[1] = 1 if 1 not in a else 0
    for i in range(2, n+1):
        if i not in a:
            x[i] = (x[i-1] + x[i-2]) % 1000000007
        else:
            x[i] = 0
    print(x[-1])


if __name__ == '__main__':
    slove()

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

ok = [True] * (N + 1)
for a in A:
    ok[a] = False

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

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

print(dp[N])

Solution (Python):
if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])
   broken = [False] * (n+1)
   for i in range(n+1):
      if i in a:
         broken[i] = True

   MOD = 1000000007

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

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

   print(dp[n])

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

   MOD = 1000000007

   dp = [0 for i in range(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-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])

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

Solution (Python):
import sys
import math
from fractions import gcd





def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""


 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())


 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) 
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = set(map(int,sys.stdin.readlines()))

dp[0]=1

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

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=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

lim=10**9+7
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
memo = [0] * (N+1)
memo[0]=1

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

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

if 1 in a:
  a.pop()
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if len(a) > 0 and i == a[-1]:
    a.pop()
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])

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

ways = [1, 1]
for i in range(2, n + 1):
    ways.append(ways[i-2] + ways[i-1])

stairs = []
now = 0
for i in range(m):
    stairs.append(a[i] - 1 - now)
    now = a[i] + 1

stairs.append(n - now)

ans = 1
for ele in stairs:
    if ele == -1:
        ans *= 0
    else:
        ans *= ways[ele]

mod = 10 ** 9 + 7
print(ans % mod)

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

Solution (Python):
def resolve():
    n, m  = list(map(int, input().split()))
    aaa = [int(input()) for _ in range(m)]
    dp = [0 for i in range(n+1)]
    mod = 10**9 + 7
    dp[0] = 1
    isbroken = [1 for i in range(n+1)]
    for i in range(m):
        isbroken[aaa[i]] = 0
    for i in range(n):
        if i-1 >= 0:
            dp[i+1] = dp[i] * isbroken[i] + dp[i-1] * isbroken[i-1]
        else:
            dp[i+1] = dp[i] * isbroken[i]
        dp[i+1] %= mod 
    
    print(dp[n])
resolve()

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

for a in A:
    step[a]=0
for i in range(2, N+1):
    step[i]=(step[i-1]+step[i-2])%mod*step[i]
print(step[-1])

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

Solution (Python):
a,b = [int(i) for i in input().split()]
c = {int(input()) for _ in range(b) }
mod = 1000000007

memo = [1] * (a+1)

for i in c:
    memo[i] = 0

for i in range(a+1):
    if i > 1:
        memo[i] = (memo[i-1] + memo[i-2])%mod*memo[i]
        
print(memo[a])

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

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

    sep = []
    pre = -1
    ok = True
    for t in a:
        tmp = t - pre - 1
        if tmp == 0:
            ok = False
            break
        sep.append(tmp)
        pre = t
    sep.append(N-pre)
    

    if not ok:
        print(0)
        return
    max_sep = max(sep)

    MOD = 1000000007
    fib = [1] * (max_sep)
    for i in range(2, max_sep):
        fib[i] = fib[i-2] + fib[i-1]
        fib[i] %= MOD
    
    ans = 1
    for s in sep:
        ans *= fib[s-1]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

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

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

print(dp[n])

Solution (Python):
mod = 1000000007

while True:
    try:
        N, M = map(int, input().split())
        
        
        a = [0] * (N+1)
        for _ in range(M):
            a[int(input())] = 1
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 0 if a[1] else 1
        
        for i in range(2, N+1):
            if a[i]:
                dp[i] = 0
            else:
                dp[i] = dp[i-1] + dp[i-2]
        
        print(dp[N] % mod)
    except:
        break

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

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

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

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

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

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

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

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

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

def fib(x): 
    a, b = 1, 1
    if x == 0:
        return a
    elif x == 1:
        return b
    else:
        for i in range(x-1):
            a, b = b, a + b
        return b
"""

def fib(x): 
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    else:
        return(f(x-1) + f(x-2))
"""

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += fib(N) % MOD
    print(ans)
else:
    ans += fib((a[0]-1) - 0) % MOD 
    for i in range(1, M): 
        stair = (a[i] - 1) - (a[i-1] + 1) 
        if stair >= 0:
            ans *= fib(stair) % MOD 
        else:
            ans = 0
            break
    ans *= fib(N - (a[M-1] + 1)) % MOD 
    print(ans % MOD)

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

def f(x):
    a, b = 1, 1
    if x == 0:
        return a
    elif x == 1:
        return b
    else:
        for i in range(x-1):
            a, b = b, a + b
        return b
"""

def f(x): 
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    else:
        return(f(x-1) + f(x-2))
"""

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += f(N) % MOD
    print(ans)
else:
    ans += f((a[0]-1) - 0) % MOD 
    for i in range(1, M): 
        stair = (a[i] - 1) - (a[i-1] + 1) 
        if stair >= 0:
            ans *= f(stair) % MOD 
        else:
            ans = 0
            break
    ans *= f(N - (a[M-1] + 1)) % MOD 
    print(ans % MOD)

Solution (Python):
MOD_NUM = 1000000007
N, M = map(int, input().split())
alist = [int(input()) for _ in range(M)]
cases = [1] + [0 for _ in range(N)]
for a in alist:cases[a] = None

for i in range(1,N+1):
  if cases[i] is None:continue
  if cases[i-1] is not None:cases[i] += cases[i-1] 
  if i >= 2 and cases[i-2] is not None: cases[i] += cases[i-2]
print(cases[-1]%MOD_NUM)

Solution (Python):
n,m=map(int,input().split())
fib=[0]*(n+2)
fib[0]=0
fib[1]=1
for i in range(n):
  fib[i+2]=fib[i]+fib[i+1]
ans=1
k=0
for i in range(m):
  a=int(input())
  ans*=fib[a-k]
  k=a+1
ans*=fib[n-k+1]
print(ans%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

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

if N == 1:
    print(1)

else:
    a = 1
    ans = 1

    if M == 0:
        b = 1
        for i in range(2, N+1):
            ans = (a+b)%1000000007
            a, b = b, ans

    elif M == 1:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if a_list[0] == i:
                a, b = b, 0
            else:
                ans = (a+b)%1000000007
                a, b = b, ans

    else:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if m < M-1:
                if a_list[m+1] - a_list[m] == 1:
                    print(0)
                    sys.exit()

                if a_list[m] == i:
                    a, b = b, 0
                    m += 1
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

            else:
                if a_list[m] == i:
                    a, b = b, 0
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

    print(ans)

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

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 = list(map(int,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(n - 1):
    if issafe[i]: dp[i + 2] += dp[i]
    if issafe[i + 1]: dp[i + 2] += dp[i + 1]
    dp[i + 2] %= 1000000007

print(dp[n])

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

A = []
d = [1 for i in range(N+1)]
for i in range(M):
    a = int(input())
    A.append(a)
    d[a] = 0
    if i != 0:
        if a-A[i-1] == 1:
            print(0)
            exit()

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

for n in range(2,N+1):
    
        
    dp[n] = dp[n-1]+dp[n-2]
    buff = 0
    if d[n-1]:
        buff += dp[n-1]
    if d[n-2]:
        buff += dp[n-2]
    dp[n] = buff


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

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

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

print(arr[-1])