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())
ans = 1
bro = list([])

for i in range(M):
    bro.append(int(input()))

bro.append(-1)

f = [0,0,1]

def Step (i):
    if i == bro[0]:
        bro.pop(0)
        f[0],f[1],f[2] = f[1],f[2],0
    else:
        f[0],f[1],f[2] = f[1],f[2],(f[1]+f[2])%(10**9+7)

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

ans = f[2]%(10**9+7)

print(ans)

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

broken = []
for _ in range(M):
  broken.append(int(input()))
broken = set(broken)

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = (f2 + f1) % mod
  f2 = f1
  f1 = f
print(f)

Solution (Python):
N,M = map(int, input().split())
ans = 1
bro = list([])

for i in range(M):
    bro.append(int(input()))

bro.append(-1)

f = [0,0,1]

def Step (i):
    if i == bro[0]:
        bro.pop(0)
        f[0],f[1],f[2] = f[1],f[2],0
    else:
        f[0],f[1],f[2] = f[1],f[2],f[1]+f[2]

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

ans = f[2]%(10**9+7)

print(ans)

Solution (Python):

MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * (num + 2)
    pattern[0] = 0
    for i in range(1, num + 2):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern

def solve():
    
    stepsList = [0] * (M + 1)
    maxSteps = 0
    if M > 0:
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N + 1]
    pattern = getPatternNum(max(stepsList) + 1)
    
    
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]
        else:
            total = (total * pattern[stepsList[k]]) % MOD
        

    return total


ans = solve()
print(ans)

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

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


dp = [0]*(n+1)
dp[0]=1
for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    dp[i] += dp[i-1]
    if i >= 2:
      dp[i] += dp[i-2]
    dp[i] = dp[i]%mod
print(dp[-1]%mod)

Solution (Python):
n,m = map(int,input().split())
mod = int(1e9+7)
f = [True for i in range(n+1)]
for i in range(m):
	f[int(input())] = False
dp=[1]+[0 for i in range(n+1)]
for i in range(n):
	if f[i+1]:
		dp[i+1] = (dp[i]+dp[i-1])%mod
print(dp[n])

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    a=set(a)
    dp[0]=1
    mod=10**9+7

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

if __name__ == '__main__':
    main()

Solution (Python):
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True 
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

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

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)

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

print(dp[-1])

Solution (Python):
def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

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

    ai = 0
    for i in range(N):
        if ai < M and A[ai] == i+1:
            dp[i+1] = 0
            ai += 1
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    
    return dp[N]


if __name__ == "__main__":
    M = 0

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

    ans = typical_stairs(N, M, A)
    print(ans)

Solution (Python):
def main():
    n,m = map(int, input().split())
    stairs = [1]*(n+1)
    mod = 1000000007
    for _ in range(m):
        stairs[int(input())] = 0
    for i in range(2, n+1):
        stairs[i] = (stairs[i-2] + stairs[i-1]) * stairs[i]
    print(stairs[n] % mod)
    
if __name__ == '__main__':
    main()

Solution (Python):
import bisect


def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

    A.sort()
    A.append(float('inf'))

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

    for i in range(N):
        if A[bisect.bisect_left(A, i+1)] == i+1:
            dp[i+1] = 0
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    
    return dp[N]


if __name__ == "__main__":
    M = 0

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

    ans = typical_stairs(N, M, A)
    print(ans)

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

Solution (Python):










import numpy as np
import math
import copy
import itertools

mod  = 1000000007

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

broken = [0 for _ in range(N + 2)]

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

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

print(dp[0])

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

a = [int(input()) for _ in range(m)]

dp = [0] * (n+3)

for x in a:
    dp[x] = -1

dp[0] = 1

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



print(dp[n])

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

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

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

print (lst[N+1]%1000000007)

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

DP = [1] * (N+1)

for i in A:
    DP[i] = 0

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

print(DP[N])

Solution (Python):


import sys
import copy

sys.setrecursionlimit(1000000)





MOD = 1000000007

N, M = map(int, input().split())
goods = [True] * (N + 4)
dp = [0] * (N + 4)

for _ in range(M):
    x = int(input())
    goods[x] = False

dp[0] = 1
for i in range(N + 1):
    if goods[i]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD


print(dp[N])

Solution (Python):
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
dp[1] = int(1 not in a)
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):
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())

aa=[0 for i in range(100000+10)]
for i in range(m):
  a=int(input())
  aa[a]=1


d=[0 for i in range(100000+10)]
p=1000000007

d[0]=1
if aa[1] == 0:
    d[1]=1
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    

print(d[n]%p)

Solution (Python):
def mulmod(x,y,p):
    return x*y % p

def test(n):
    if n<1:
        return 1
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = (memo[i-1] + memo[i-2])%1000000007
    return memo[n]

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)

for i in a:
    result = mulmod(test(i-pos-1),result,1000000007)
    pos = i+1
 
result = mulmod(test(n-pos),result,1000000007)
print(result)

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


d=[0 for i in range(100000+10)]
p=1000000007


aa=[0 for i in range(100000+10)]

for i in a:
    aa[i]=1


d[0]=1
if aa[1] == 0:
    d[1]=1
else:
    d[1]=0
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0


print(d[n]%p)

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

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

def count(s,e):
    return fib[e-s]
 
c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    
    end=a-1
    ans=ans*count(start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,end)%c_mod
print(ans)

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


main()

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


main()

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

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

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

Solution (Python):
MOD = 1000000007

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

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

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

print(count[n])

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

mod = 10**9 + 7

li = [0]*(N+2)
li[0] = 0
li[1] = 1
for i in range(M):
    a = int(input())+1
    li[a] = -1

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

print(li[-1])

Solution (Python):
N, M = map(int, input().split())
def fib(n) :
    a, b = 1, 1
    if n==0 :
        return a
    elif n==1 :
        return b
    else :
        for i in range(n-1):
            a, b = b, a+b
        return b
a=[]
b=1

for i in range(M):
    a.append(int(input()))
    if a[i]-a[i-1] == 1 :
        b=0

def rest(num) :
    return num % 1000000007
c=0
if b==0 :
    print(c)
else :
    for i in range(M+1):
        if i == 0 == M :
            c += rest(fib(N))
        elif i == 0:
            c += rest(fib(a[i]-1))
        elif i == M:
            c = rest(c * fib(N-a[i-1]-1))
        else :
            c = rest(c * fib(a[i]-a[i-1]-2))
    print(c)

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

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


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


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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())

dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))

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

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

def intinput(): return map(int,sys.stdin.readline().split())


n, m = intinput()
a = {int(sys.stdin.readline()) for _ in range(m)}
memo = [0 for x in range(n + 4)]
memo[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
    if i + 1 not in a:
        memo[i + 1] = (memo[i + 1] + memo[i]) % mod
    if i + 2 not in a:
        memo[i + 2] = (memo[i + 2] + memo[i]) % mod
print(memo[n])

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

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

print(dp[n]%mo)

Solution (Python):



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

N += 1
broken_stairs = [int(input()) for _ in range(M)]


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


for b in broken_stairs:
    dp[b] = 0


MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    
    if i + 1 < N and i + 1 not in broken_stairs:
        
        dp[i + 1] += dp[i] % MOD
    
    if i + 2 < N and i + 2 not in broken_stairs:
        
        dp[i + 2] += dp[i] % MOD
    """
    
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(dp[-1])

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

for i in range(n):
    if c[i] < 0:
      continue
    if c[i+1] >= 0:
        c[i+1] = c[i] + c[i+1]
    if c[i+2] >= 0:
        c[i+2] = c[i] + c[i+2]
    c[i] = c[i] % 10**9+7
print(c[n]%(10**9+7))

Solution (Python):

import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    


main()

Solution (Python):
import math
 
N, M = map(int, input().split())
broken_a = [0] * (N + 1)
for _ in range(M):
  broken_a[int(input())] = 1

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

print(dp[N])

Solution (Python):
lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)

Solution (Python):
N, M = map(int, raw_input().split(' '))
P = 1000000007

skip = []
for i in range(M):
    skip.append(int(raw_input()))

nums = set(range(N)) - set(skip)

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

for i in nums:
    steps[i+1] = (steps[i+1] + steps[i]) % P
    steps[i+2] = (steps[i+2] + steps[i]) % P

print steps[N]

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

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


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


DP = [1] * (N + 1)


for idx in a:
    DP[idx] = 0


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

print(DP[N]%MOD)

Solution (Python):
def fib(n):
    if n == 0: 
        return 0

    if n == 1: 
        return 1

    def matmul(M1, M2):
        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        return [[a11, a12], [a21, a22]]

    def matPower(mat, p):
        if p == 1: 
            return mat

        m2 = matPower(mat, p//2)
        if p % 2 == 0:
            return matmul(m2, m2)
        else: 
            return matmul(matmul(m2, m2),mat)

    Q = [[1,1],[1,0]]

    q_final = matPower(Q, n-1)
    return q_final[0][0]

N, M = map(int, input().split())
if(M==0):
    print(fib(N+1)%1000000007)
else:
    V = []
    for x in range(M):
        V.append(int(input()))

    result = 1

    for i in range(1, M):
        if(V[i]-V[i-1]==1):
            result = 0

    result *= fib(V[0])

    for x in range(1, M):
        result *= fib(V[x]-V[x-1]-1)

    if(V[M-1]!=N):
        result *= fib(N-V[M-1])

    print(result%1000000007)

Solution (Python):

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


dp = [1] * (n+1)

for i in a:
    dp[i] = 0

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

print(dp[n])

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

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

print(DP[N]%MOD)

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

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

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

print(dp[-1])

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

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

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

print(dp[0])

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

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

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

for i in range(M):
    fall[a[i]] = 0

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

print(dp[N])

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

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

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

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

for i in a:
    dp[i] = 0

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

print(dp[n])

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

Solution (Python):

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

    a = [True] * (N+1)
    
    for _ in range(M):
        a[int(input())] = False
    
    
    
    
    
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: 
            if a[s+1] == False:
                dp[s] = 0 
                break
            else:
                dp[s] = 0 
        else: 
            dp[s] = (dp[s+1] + dp[s+2]) % mod 
            
    print(dp[0])

main()

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

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

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

Solution (Python):
n,m=map(int,input().split())
D=[1] * (n + 1)
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]) % 1000000007 
print(D[i])

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

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

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

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

for now in range(n+1):
    for nxt in range(now+1, min(n+1, now+3)):
        if s[nxt]:
            dp[nxt] += dp[now]
            dp[nxt] %= mod

print(dp[n])

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

mod = 1000000007
 
N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]
 
for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()
 
memo = {0: 1, 1: 1, 2: 2, 3: 3}
 
def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
 
ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod
 
    lo = a + 1
    pre = a
 
print(ans)

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

dif = [a_lis[j+1]-a_lis[j]-2 for j in range(M+1)]
fib_lis = []

def fib(n):
  for k in range(n+1):
    if k==0 or k==1:
      fib_lis.append(1)
    else:
      fib_lis.append(fib_lis[k-2]+fib_lis[k-1])

  return fib_lis[-1]

max_ = max(dif)
fib(max_)
  
t = 1

for d in dif:
  if d < 0:
    t *= 0
  else:
    t *= fib_lis[d]
  t = t % 1000000007
  
print(t)

Solution (Python):



import numpy as np
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(1000)



N, M = list(map(int,input().split()))
A = {int(input()) for _ in range(M)}


rootList = np.array([1]+[0]*(N))






def main():
    for i in range(N):
        rootList[i+1] = (rootList[i]+rootList[i-1])%1000000007
        if i+1 in A:
            rootList[i+1] = 0
    print(rootList[N])

if __name__ == "__main__":
    main()

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

Solution (Python):
N, M = map(int, input().split())
 
a = [int(input()) for i in range(M)]
 
 
for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()
 
dp = [0] * (N + 1)
flag_a = [0] * (N + 1)
 
for i in range(M):
    flag_a[a[i]] = -1
 
 
if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()
 
if 1 in a and 2 in a:
    print(0)
    exit()
 
if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2
 
for i in range(3,N+1):
    if flag_a[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 = []
for i in range(M):
    a.append(int(input()))

for n, i in enumerate(a):
    if n > 0:
        if (a[n] - a[n-1]) == 1:
            print(0)
            exit()

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

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

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


print(dp[0]%1000000007)

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

def dfs(heights: int, a_index:int, a_n_1, a_n_2):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[2] = 0
        a_index += 1
        
    else:
        memo[2] = a_n_1 + a_n_2 
        
    dfs(heights+1,a_index,memo[2],a_n_1)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(3)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            

    if a[0] == 1:
        memo[1] = 0
        a_index += 1


dfs(2,a_index,memo[1],memo[0])

print(memo[2] % (10**9+7))

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

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

dp[0] = 1

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

ans = dp[N]%1000000007

print(ans)

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

MOD = pow(10, 9) + 7

MAP = [0] * (N + 1)

for x in a:
    MAP[x] = -1

MAP[0] = 1 
for i in range(N):
    if MAP[i] < 0:
        continue

    MAP[i] %= MOD
    if i + 1 <= N and MAP[i+1] >= 0:
        MAP[i+1] += MAP[i]
    if i + 2 <= N and MAP[i+2] >= 0:
        MAP[i+2] += MAP[i]

print(MAP[N] % MOD)

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

mod_num = 10 ** 9 + 7
a = [0] * M

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if i in a:
        val[1] = 0

 
print(ans)

Solution (Python):
N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * N
for i in range(M):
    a[i] = int(input())
val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[j]:
            val[1] = 0
            if len(a) - 1 != j:
                j += 1
print(ans)

Solution (Python):
import sys

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

broken = set(map(int, sys.stdin))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

Solution (Python):
mod = 1000000007

N, M = [int(i) for i in input().split()]
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]

for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()

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

ans = 1
for i in range(1, len(A)):
    f = fib[A[i] - A[i - 1] - 2]
    ans = (ans * f) % mod
print(ans)

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