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())
data = []
dp = ['.' for i in range(N + 1)]
dp[0] = 1
dp[1] = 1
for i in range(M):
    k = int(input())
    data.append(k)
    dp[k] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[N] % mod)

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

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


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

br = [0 for i in range(n+2)]
for i in range(m):
    a = int(input())
    br[a] = 1

can = [0 for i in range(n+2)]

can[1] = 1
can[2] = 2

if br[1] == 1:
    can[1] = 0
    can[2] = 1
if br[2] == 1:
    can[1] = 1
    can[2] = 0
if br[1] == 1 and br[2] == 1:
    can[1] = 0
    can[2] = 0

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

print(can[n])

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

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

Solution (Python):


MOD_KEY = 1000000007
n, m = map(int, input().split())
dp = [0]*(n+1)
for i in range(m):
    a = int(input())
    dp[a] = -1

dp[0] = 1

for i in range(n):
    
    for j in range(1, 3):
        
        if i + j < n+1:
            if (dp[i+j] >= 0) & (dp[i] >= 0):
                dp[i+j] += dp[i]
                dp[i+j] %= MOD_KEY

if dp[n] > 0:
    print(dp[n])
else:
    print(0)

Solution (Python):
CONST = 1000000007

def noboru(n):
    a1 = 1
    a2 = 2
    ans = 0
    if (n == 0 or n == 1): return a1
    elif (n == 2): return a2
    else:
        for i in range(1, n-1):
            ans = a2 + a1
            a1 = a2
            a2 = ans
        return a2

def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos)) % CONST
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a))

Solution (Python):
BASE =  1000000007

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = []
    for i in range(M):
        not_available.append(int(input()))
    x = 0
    y = 1
    predicted_next = 1
    is_available = [True] * N
    for idx in not_available:
        is_available[idx - 1] = False

    for flag in is_available:
        if flag:
            z = x + y
            x = y
            y = z
        else:
            x = y
            y = 0

    print(y % BASE)

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

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


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

print(dp[N] % 1000000007)

Solution (Python):

import sys
sys.setrecursionlimit(1000000)

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 


def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: 
        target_step_count = a - 1 - now_step 
        ans = ans * jump(target_step_count) % mod_number
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count) % mod_number
    
    print(ans)

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
if 1 in A:
  dp[1]=0

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

Solution (Python):
def fib(n):
    if n==1:
        a=1
        return a
    if n==2:
        a=1
        return a
    a0=1
    a1=1
    cnt=2
    while cnt <n:
        a=a0+a1
        cnt+=1
        a0=a1
        a1=a
    return a


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

mod=10**9+7

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

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)
ans=(ans*c)%mod

print(ans)

Solution (Python):
def fib(n):
    if n==1:
        ans=[1]
        return ans

    ans=[1,1]
    cnt=2
    while cnt <n:
        ans.append(ans[-2]+ans[-1])
        cnt+=1
    return ans

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

mod=10**9+7

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

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)[-1]
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)[-1]
ans=(ans*c)%mod

print(ans)

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())-1
    chk[a]=False

mod=10**9+7

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

f=[0]*(N+1)

if not chk[0]:
    f[0]=0
else:
    f[0]=1

if not chk[1]:
    f[1]=0
else:
    f[1]=f[0]+1

for i in range(2,N):
    if not chk[i]:
        f[i]=0
    else:
        f[i]=f[i-2]+f[i-1]

    f[i]=f[i]%mod

print(f[N-1])

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

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

f=[0]*(N+1)
f[0]=1
if chk[1]:
    f[1]=1
else:
    f[1]=0


for i in range(2,N+1):
    if chk[i-2]:
        f[i]+=f[i-2]
    if chk[i-1]:
        f[i]+=f[i-1]
    f[i]=f[i]%mod

print(f[N])

Solution (Python):
n, m = map(int, input().split())
dp = [0] * (10**5+10)
jud = [True]*(10**5)
for k in range(m):
    a = int(input())
    jud[a] = False

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

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

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

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
M = 1000000007
dp = {}
dp[0] = 1
for i in range(1, n+1):
    if i in a:
        dp[i] = 0
        continue
    if i - 2 < 0:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % M)

Solution (Python):
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
for _ in  range(m):
    a.add(int(input()))

dp = [0 for i in range(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]
        dp[i] %= p
    else:
        dp[i] = 0

print(dp[-1])

Solution (Python):
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
for _ in  range(m):
    a.add(int(input()))

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

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

print(dp[-2]%p)

Solution (Python):
import sys
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
if m == 0:
    print(fib[n]%1000000007)
    sys.exit()
answer = fib[a[0]-1]
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        answer = 0
    else:
        answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n-a[m-1]-1] % 1000000007
print(answer)

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

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

ai=0
n1,n2=0,1
for i in range(1,n+1):
      if ai<m and i==A[ai]:
            ai+=1
            n1=n2
            n2=0
      else:
            tmp=n2
            n2=(n1+n2)%1000000007
            n1=tmp
print(n2)

Solution (Python):
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
ai=0
n1,n2=0,1
for i in range(1,N+1):
    if ai<M and i==A[ai]:
        ai+=1
        n1=n2
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)

Solution (Python):
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
crash = 0
idx = 0
for i in range(M):
    A.append(int(input()))
    if i == 0:
        crash = A[0]
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1 , N + 1):
    if i == crash:
        idx += 1
        if idx < M:
            crash = A[idx]
    else:
        if i == 1:
            dp[1] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= mod
print(dp[-1])

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

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    


if m==0:
	ans=ans*fb(n)
	
else:
	for i in range(m-1):
		if (lista[i]+1==lista[i+1])&(m>=2):
			ans=0
  	
  	
	else:
		lista.append(n)
		if lista[0]!=1:
				ans=ans*(fb(lista[0]-1))
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
		if lista[0]==1:
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
		ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)

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

Solution (Python):
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = [False for _ in range(N+1)]
for _ in range(M):
    alist[int(input())] = True

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

print(dp[N]%1000000007)

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

Solution (Python):
n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1

for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)

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


if __name__ == '__main__':
    slove()

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def f(i):
    if dp[i] != -1 and dp[i] != 0: return dp[i]
    if dp[i] == -1: return 0

    if i == -1:
        return f(i - 1)
    elif i > 1:
        dp[i] = f(i - 1) + f(i - 2)
    else:
        dp[i] = f(i - 1)
    return dp[i]

n,m = map(int,input().split())
dp = [0]*(n+1)
ary = [int(input()) for _ in range(m)]
dp[0] = 1
for i in ary:
    dp[i] = -1
    if dp[i-1] == -1 and dp[i] == -1:print(0);exit()
print(f(n)%(10**9+7))

Solution (Python):
n,m = map(int,input().split())
dp = [0]*(n+1)
ary = [int(input()) for _ in range(m)]
dp[0] = 1
for i in ary:
    dp[i] = -1
    if dp[i-1] == -1 and dp[i] == -1:print(0);exit()
for i in range(1,n+1):
    if dp[i] == -1:continue
    elif dp[i-1] == -1:dp[i] = dp[i-2]
    elif dp[i-2] == -1:dp[i] = dp[i-1]
    elif i > 1: dp[i] = dp[i-1]+dp[i-2]
    else: dp[i] = dp[i-1]
print(dp[n]%(10**9+7))

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    
    N,M = map(int, input().split())
    MOD = 1000000007
    AS = [int(input()) for _ in range(M)]
    AS = set(AS)
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in AS else 0
    for n in range(2,N+1):
        if n in AS: continue
        if n-1 not in AS:
            dp[n] += dp[n-1]
            dp[n] %= MOD
        if n-2 not in AS:
            dp[n] += dp[n-2]
            dp[n] %= MOD
    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
import bisect

p=10**9+7
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
x=[0 for i in range(N+1)]
x[0]=1
if 1 in a:
    x[1]=0
else:
    x[1]=x[0]
for i in range(2,N+1):
    if bisect.bisect_right(a,i-1)-bisect.bisect_left(a,i-1)==0: 
        x[i]+=x[i-1]
    if bisect.bisect_right(a,i-2)-bisect.bisect_left(a,i-2)==0: 
        x[i]+=x[i-2]
    x[i]%=p

print(x[N])

Solution (Python):
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
kaidan = [-1] * (n + 1)
for i in range(len(l)):
    kaidan[l[i][0]] = 0
for i in range(1, len(kaidan) + 1):
    if not (kaidan[-i] == 0):
        if i == 1:
            kaidan[-1] = 1
        elif i == 2:
            kaidan[-2] = kaidan[-1]
        else:
            kaidan[-i] = kaidan[-i + 1] + kaidan[-i + 2]
print(kaidan[0] % 1000000007)

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

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

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
if m>=2:
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fiblist[n])
if m==1:
    print(fiblist[lists[1]-1]*fiblist[n-lists[1]-1]%(10**9+7))

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def f(num):
    if memo[num] != 0 and memo[num] != -1:return memo[num]

    if memo[num] == -1:
        return f(num-1)
    if memo[num-1] == -1:
        memo[num] = f(num-1)
    elif memo[num-2] == -1:
        memo[num] = f(num-1)
    elif num > 1:memo[num] = f(num-1)+memo[num-2]
    else:memo[num] = f(num-1)


    return memo[num]

n,m = map(int,input().split())
memo = [0 for _ in range(n+1)]
for i in [int(input()) for _ in range(m)]:
    memo[i] = -1
    if memo[i] == -1 and memo[i-1] == -1:print(0);exit()
memo[0] = 1
print(f(n)%(10**9+7))

Solution (Python):
def main():

    N, M = map(int, input().split())
    stairs = [1] * N
    ans = [0] * N
    for _ in range(M):
        stairs[int(input()) - 1] = 0
    for i in range(N):
        if i == 0:
            ans[i] = stairs[i]
        elif i == 1:
            ans[i] = ans[i - 1] * stairs[i - 1] + stairs[i]
        else:
            ans[i] = (stairs[i - 1] * ans[i - 1] + stairs[i - 2] * ans[i - 2]) % (10 ** 9 + 7)
    print(ans[N - 1])

if __name__ == "__main__":
    main()

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


def fibonacci(N):
    prev = []
    for i in range(1, N+1):
        if i == 1 or i == 2:
            prev.append(1)
        else:
            prev.append(prev[-2] + prev[-1])
    return(prev[-1])


a.append(N + 1)

for i in range(M+1):
    dis = a[i] - pos
    if dis == 0:
        ans = 0
        break
    ans *= fibonacci(dis)
    pos = a[i]+1
print(ans % ((10**9)+7))

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

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


dp = [0 for _ in range(n+1)]
dp[0] = 1
for now in range(n):
  for next in range(now+1, min(n, now+2)+1):
    if(oks[next]):
      dp[next]+=dp[now]
      dp[next]%=10**9+7
print(dp[n])

Solution (Python):
def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b



ary = []
flag = 0
n, m = map(int, input().split())
for i in range(m):
  a = int(input())
  ary.append(a)
  if ary[i] == ary[i-1]+1:
    flag = 1
    break
if flag == 1:
  print(0)
else:
  ary.append(n+1)
  count = max(1,ary[0])
  count = fb(count)
  for i in range(1,len(ary)):
    sa = ary[i]-ary[i-1]-1
    if sa == 0:
      pass
    else:
        count*=fb(sa)
  count = count%1000000007
  print(count)

Solution (Python):
import sys

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

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

l = []
dan = 0
for i in range(m+1):
	l.append(a[i]-1-dan)
	dan = a[i] + 1
	if dan == n+2:
		break

if max(l) > 2:
	for i in range(2,max(l)):
		t.append(t[i-1] + t[i-2])

ans = 1
for i in l:
	if i != 0 and t[i-1] != 0:
		ans *= t[i-1]
		ans %= mod

print(ans)

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

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

Solution (Python):
n,m=map(int,input().split())
a=set(int(input()) for i 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
    if i==1:
        dp[i]=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[-1])

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

mod = 10**9+7
for _ in range(m):
    a.append(int(input()))

dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
if a:
    if a[0]==1:
        dp[1] = 0

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

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


def Fib(n):
    a, b = 1, 1
    if n == 0:
        return 0
    elif n== 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)









if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): 
      n = (A[i]-1)-0
      
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      
      
    if(i != 0): 
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)
 ans = ans*(Fib(n+1)%(10**9 + 7))
 
            
ans = ans%(10**9 + 7)
print(ans)

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

Solution (Python):

mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = -1
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

Solution (Python):
import bisect

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

for i in range(1, N+1):
  idx = bisect.bisect_left(A, i)
  if idx < len(A) and A[idx] == i:
    continue
  if i < 2:
    dp[i] = dp[i-1]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

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

Solution (Python):

mod = 1000000007

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

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

print(dp[n])

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

print(ans[N])

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

Solution (Python):
N, M = map(int, input().split())
a = []
issafe = [True for _ in range(N+1)]
for i in range(M):
    a.append(int(input()))
    issafe[a[i]] = False

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

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

print(dp[N])

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

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

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

print(dp[N])

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

Solution (Python):
def fib(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a


n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n + 1]
ans = 1

for i in range(len(a) - 1):
    if a[i] != 0 and a[i + 1] != n and a[i + 1] - a[i] == 1:
        print(0)
        exit()

    ans = ans * fib(a[i + 1] - a[i] - 2) % (10 ** 9 + 7)

print(ans)

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

for i in range(N+1):
    if dp[i] == -1:
        dp[i] = 0
    elif i > 1:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 1
        
print(dp[N]%1000000007)

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

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


def Fib(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = (a + b) % 1000000007, a % 1000000007
    return (a)


def stepcount(x, y):
    if y - x <= 1:
        return 1
    else:
        return Fib(y - x)

if m != 0:
    answer = Fib(outlist[0] - 1)

    for i in range(m - 1):
        answer *= stepcount(outlist[i] + 1, outlist[i + 1] - 1)
        answer = answer % 1000000007

    answer = (answer * stepcount(outlist[m - 1] + 1, n)) % 1000000007

    for i in range(m - 1):
        if outlist[i + 1] - outlist[i] == 1:
            answer = 0
else:
    answer = Fib(n)

print(answer)

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

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


for i in range(N):
  if i+1 not in a:
    dp[i+1]+=dp[i]
    dp[i+1] %= mod
  if i+2 <= N and i+2 not in a:
    dp[i+2]+=dp[i]
    dp[i+2]%=mod
  
print(dp[-1])

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

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

a=set(int(input()) for i 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
print(dp[-1])

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


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)

Solution (Python):
import sys
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
c=0
if 1 in l:
    c+=1
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        c+=1
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if c>=len(l):
        ans.append((ans[-1]+ans[-2])%1000000007)
    elif S==l[c]:
        c+=1
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])

Solution (Python):

def main():
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    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):

mod=10**9+7
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
def f(x):
    b=1
    c=1
    if x==1 or x==0:
        return 1
    else:
        for i in range(x-1):
            b,c=(b+c)%mod,b
        return b
if m>=1:
    s=f(a[0]-1)
    for i in range(1,m):
        if a[i]-a[i-1]==1:
            print(0)
            break
        s=(s*f(a[i]-a[i-1]-2))%mod
    else:
        s=(s*f(n-a[m-1]-1))%mod
        print(s)
else:
    print(f(n))

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

if n == 1:
    print(1)
elif n == 2:
    if a[1] == -1:
        print(1)
    else:
        print(2)
else:
    if a[1] == -1:
        b1 = 0
    else:
        b1 = 1
    if a[2] == -1:
        b2 = 0
    else:
        b2 = b1+1

    b3 = b1 + b2

    for i in range(3,n+1):
        if a[i] == -1:
            b3 = 0
        else:
            b3 = b1+b2
        if b3 > 1000000007:
            b3 = b3 % 1000000007
        b1 = b2
        b2 = b3
        if b1==b2==0:
            break

    print(b3)

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

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

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

Solution (Python):
N, M = map(int, input().split())
dp = [0 for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
else:
    dp[1] = 0
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)