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())
a = []
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    if M > 0:
        a += [int(input())]
    for i in range(M - 1):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
    a.append([-1])
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

Solution (Python):
N, M = map(int, input().split())
a = []
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    if M > 0:
        a += [int(input())]
    for i in range(M - 1):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
    a.append([-1])
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

Solution (Python):
import sys
n, m = map(int,input().split())
mod = 1000000007
a = [True] * (n + 1)
for i in range(m):
    a[int(sys.stdin.readline())] = False
dp = [0] * (n + 1)
dp[0] = 1

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

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

print(dp[n])

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

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

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

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))
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
        continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)

Solution (Python):
N,M = list(map(int,input().split()))
A = set(int(input())-1 for i in range(M))

S = []
for i in range(N):
  if i not in A: 
    if i == 0 :
      S += [1]
    elif i == 1:
      S += [S[0] + 1]
    else:
      S += [(S[i-1] + S[i-2]) % int(1e9+7)]
  else:
    S += [0]

print(S[-1])

Solution (Python):
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7

@lru_cache(maxsize=1000000)
def saiki(i):
    if ok[i]:
        if i == 0:
            return 1
        if i == 1:
            return 1
        return saiki(i - 1) % mod + saiki(i - 2) % mod
    else:
        return 0


n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
ok = [True] * (n + 1)
for i in a:
    ok[i] = False
print(saiki(n) % mod)

Solution (Python):


MOD = int(1e9 + 7)
N, M = map(int, input().split())

broken = [False] * (N + 1)
for i in range(M):
    broken[int(input())] = True

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 0 if broken[1] else 1

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

print(dp[N] % MOD)

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


s = [0] * (n + 1)
s[0] = 1
for i in range(n):
    j = i + 1
    while(j <= min(n, i + 2)):
        if j not in a:
            s[j] += s[i]
            s[j] = int(s[j] % 1000000007)
        j += 1

print(s[n])

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

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

wa = (10**9) + 7



dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)==0:
    now_a = -1
if len(a)!=0:
    a.reverse()
    now_a = a.pop()

for i in range(1,N+1):
    
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1



print(dp[N]%wa)

Solution (Python):
N, M = map(int, input().split(" "))
mod = 1000000007
aList = 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]
    if i in aList :
        dp[i] = 0
print(dp[N]%mod)

Solution (Python):
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 0
        for _ in range(n-1):
            (a, b) = (a+b, a)
        return a % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:

        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)

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

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

dp[0]=1
mod=1000000007
for j in a:
    L[j]=0
for i in range(1,N+1):
    if i>=2:
        dp[i]=(dp[i-1]*L[i-1]+dp[i-2]*L[i-2])*L[i]

    elif i==1:
        dp[i]=1
    dp[i]%=mod

print(dp[N])

Solution (Python):
N, M = [int(_) for _ in input().split()]
A = set([int(input()) for _ in range(M)])
dp0 = 1
dp1 = 0
for i in range(1, N + 1):
    if i in A:
        dp0, dp1 = 0, dp0
    else:
        dp0, dp1 = dp0 + dp1, dp0
    dp0 %= 10**9 + 7
    dp1 %= 10**9 + 7
print(dp0)

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

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


num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and a[i]==1):
		print("0")
		break
	elif a[i]==1:
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		print(ans%mod)
	else:
		jud=1
		count+=1

Solution (Python):
N,M = map(int,input().split())
a = []
if M >= 1:
    for i in range(M):
        a.append(int(input()))

def fibo(n):
    a, b = 1, 1
    if (n == 0) or (n == 1) or (n == 2):
        return 1
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b

aa = [] 
if M >= 2:
    for k in range(M-1):
        aa.append(a[k+1] - a[k] - 1)



    if 0 in aa:
        ans = 0

    else:
        ans = 1
        ans_list = []
        for i in range(M-1):
            ans_list.append(fibo(aa[i]))

        ans_list.append(fibo(a[0]))
        ans_list.append(fibo(N - a[M-1]))
    
    
        for i in range (len(ans_list)):
            ans = (ans * ans_list[i]) % (10**9 + 7)

elif M == 1:
    ans_list = []
    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[0]))
    ans = (ans_list[0] * ans_list[1]) % (10**9 + 7)

elif M == 0:
    ans = fibo(N+1) % (10**9 + 7)

print(ans)

Solution (Python):


n,m = (int(x) for x in input().split())
a = []
for i in range(m):
    x = int(input())
    a.append(x)

p = 0
num = [1]
if p>=m:
    num.append(1)
elif a[p] == 1:
    num.append(0)
    p += 1
else:
    num.append(1)

for i in range(2,n+1):
    if p>=m:
        temp = num[-2]+num[-1]
        num.append(temp)
    elif a[p] == i:
        num.append(0)
        p += 1
    else:
        temp = num[-2]+num[-1]
        num.append(temp)

print(num[-1]%1000000007)

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

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

    print(s[n])

main()

Solution (Python):
N,M=map(int,input().split())
a=[]
b=[0]*N
for i in range(M):
    a.append(int(input()))
if M==0:
    j=-1
else:
    j=0
if N==1:
    b[0]=1
elif M>0 and a[0]==1:
    b[0]=0
    b[1]=1
elif M>0 and a[0]==2:
    b[0]=1
    b[1]=1
else:
    b[0]=1
    b[1]=2
for i in range(N-2):
    if j==M-1 or (j>=0 and (i+2)!=a[j] and (i+1)!=a[j]):
        b[i+2]=b[i+1]+b[i]
    if j>0 and a[j]==a[j-1]+1:
        b[N-1]=0
    if j+1<M and a[j+1]==a[j]+1:
        b[N-1]=0
    elif j>=0 and (i+2)==a[j]:
        b[i+2]=b[i]
    elif j>=0 and j+1<M and (i+1)==a[j]:
        j+=1
        b[i+2]=b[i+1]
    elif j>=0 and (i+1)==a[j]:
        b[i+2]=b[i+1]
print(b[N-1]%1000000007)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod = 10**9+7
n, m = map(int, input().split())
broken = {int(input()) for _ in range(m)}

dp = [0]*(n+1)
dp[0] = 1
for i in range(n+1):
    for j in (1, 2):
        nex = i+j
        if nex <= n and not nex in broken:
            dp[nex] += dp[i]
            dp[nex] %= mod
print(dp[-1])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7
N, M = map(int, input().split())
broken = {int(input()) for _ in range(M)}

dp = [0]*(N+1)
dp[0] = 1
for i in range(N+1):
    for j in [1, 2]:
        if i+j <= N and not i+j in broken:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD
print(dp[-1])

Solution (Python):
import math
 
N, M = list(map(int, input().split()))
stairs = [0] * (N + 1)

for i in range(M):
	stairs[int(input())] = -1


for i in range(N, -1, -1):
	
	if i == N:
		stairs[i] = 1
	
	elif i == N - 1 and stairs[i] != -1:
		stairs[i] = stairs[i + 1]
	
	elif stairs[i] != -1:
		if stairs[i + 1] != -1:
			stairs[i] += stairs[i + 1]
		if stairs[i + 2] != -1:
			stairs[i] += stairs[i + 2]
print(int(stairs[0]) % 1000000007)

Solution (Python):
n, m = list(map(int, input().split() ))
broken = [int(input()) for _ in range(m)]
broken.append(-1) 
broken_idx = 0

mod = 10**9+7

num_way = [0] * (n+1)
num_way[0] = 1
if broken[broken_idx] == 1:
	num_way[1] = 0
	broken_idx += 1
else:
	num_way[1] = 1

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

print (num_way[n])

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

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

print(dp[n])

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]

print(dp[n] % mod)

Solution (Python):
N,M = map(int,input().split())
a = [True] * (N+1)

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

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if a[n]==False:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[n])

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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


def rec(n):
    if n < 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    num = rec(n - 1) + rec(n - 2)
    dp[n] = num
    return num


print(rec(N) % MOD)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+2)
    for a in A:
        is_safe[a+1] = False

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

    return dp[N+1]


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

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

cs = [0] * (N + 1)

cs[0] = 1

M = 10**9+7

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

result = cs[N]

print(result)

Solution (Python):
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    way_go_up_the_stairs = [1] + [0] * (N)
    for i in range(1, N + 1):
        if i not in a:
            way_go_up_the_stairs[i] += sum([way_go_up_the_stairs[i - j - 1]
                                            for j in range(2) if i - j >= 0])
            way_go_up_the_stairs[i] %= MOD
    return way_go_up_the_stairs[N]

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

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

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

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

dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for _ in range(m):
  dp[int(input())] = 0

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

print(dp[-1])

Solution (Python):
import sys
N, M = map(int, input().split())
if N == 1:
    print(1)
    sys.exit()
ana = [0] * M
ans = [0] * N
mod = 10 ** 9 + 7
if M != 0:
    for i in range(M):
      ans[int(input())-1] = -1
if ans[0] == -1 and ans[1] == -1:
    print(0)
    sys.exit()
elif ans[0] == -1:
    ans[0] = 0
    ans[1] = 1
elif ans[1] == -1:
    ans[0] = 1
    ans[1] = 0
else:
    ans[0] = 1
    ans[1] = 2

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

Solution (Python):
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % MOD)

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

past = 1
past_past = 0
mod = 10**9 + 7

for is_broken in is_broken_array:
    if is_broken:
        now = 0
        
    else:
        now = past + past_past
        
        now = now % mod
    past_past = past
    past = now

print(now)

Solution (Python):
import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

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

    print(dp[n])

main()

Solution (Python):
import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

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

    print(dp[n]%mod)

main()

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

dp[0] = 1

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

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))
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
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

print(dp[N] % mod)

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

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

for _ in range(M):
  i = int(input()) + 1
  step[i] = -1

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

print (step[-1] % 1000000007)

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

print(dp[N] % mod)

Solution (Python):
N, M = map(int, input().split())
try:
  a = int(input())
except EOFError:
  a = 0
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  try:
    a = int(input())
  except EOFError:
    pass
    
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

Solution (Python):
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 1
r2 = []
f1 = False
for i2 in range(n1):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        r2.append(r1)
        r1 = 1
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

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

print(d[-1])

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, m = MI()
a = [II() for _ in range(m)]

tmp = [0] * (n+1)
ok = [True] * (n+1)
for num in a:
    ok[num] = False
tmp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if ok[j]:
            tmp[j] += tmp[i]
print(tmp[n] % MOD)

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

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

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

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

print(l[-1] % 1000000007)

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

Solution (Python):
from collections import deque

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

before1 = 1
before2 = 0
ai = a.popleft() if len(a) else 0

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        ai = a.popleft() if len(a) else ai
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current

print(before1)

Solution (Python):



def main():
    n, m = map(int, input().split())
    mod = 10 ** 9 + 7
    broken = [False for _ in range(n + 1)]
    dp = [0 for _ in range(n + 2)]
    dp[n] = 1

    for i in range(m):
        ai = int(input())
        broken[ai] = True

    
    
    for j in range(n - 1, -1, -1):
        if broken[j]:
            continue

        dp[j] = dp[j + 1] + dp[j + 2]
        dp[j] %= mod

    print(dp[0])


if __name__ == '__main__':
    main()

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

com = [0, 1]
for i in range(n):
    if (i + 1) in a:
        com.append(0)
    else:
        com.append((com[-1] + com[-2]) % mod)
print(com[-1])

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

print(dp[N])

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

def main(N, M, a_list):
    div = 10**9 + 7
    a_set = set(a_list)
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_set:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-2) % div + fib(n-1)
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

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


dp = [1] * (N + 1)
for A in AL:
    dp[A] = 0

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

Solution (Python):
import numpy as np

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

step0 = 1
step1 = A[1]

ans = [step0, step1]
for i in range(2, N+1):
    now = (ans[-1] + ans[-2]) * A[i]
    ans.append(now)
print(ans[-1] % 1000000007)

Solution (Python):
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
if m==0:
    inp=[n+1]
    dis=[n+1]
else:
    for inpset in range(m):
        inp.append(int(input()))
    

    dis=[max(inp[0],1)]
    p=0
    for i in inp[:-1]:
        dis.append(inp[p+1]-inp[p]-1)
        p+=1
    dis.append(max(n-inp[-1],1))
    

def fib(x):
    a=0
    b=1
    for step in range(x):
        c=a+b
        a=b
        b=c
    return a


def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                
            else:
                break
        res=res%1000000007
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=fib(d)%1000000007
        ans=ans%1000000007
    print(ans)

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

    step0 = 0
    step1 = 1
    for i in range(1, n+1):
        temp = step0 + step1
        step0 = step1
        step1 = temp
        if(i == a[ac]):
            step1 = 0
            ac += 1

    print(step1 % 1000000007)

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

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

print(a[n] % mod)

Solution (Python):
def main(N, M, a_list):
    div = 10**9 + 7

    a_set = set(a_list)
    
    dp = {}
    dp[0] = 1
    if 1 in a_set:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_set:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i])
    
    print(dp[N] % div)


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

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

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

print(dp[-1])

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

hole_count = 0
pattern = [0,1]

if m != 0:
    a = int(input())
    hole_count += 1
else:
    a = n+1
    
for i in range(n):
    index = i + 1
    if index == a:
        pattern.append(0)
        if hole_count < m:
            a = int(input())
            hole_count += 1
    else:
        pattern.append(pattern[-1] + pattern[-2])

print(pattern[-1] % 1000000007)

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


@lru_cache(maxsize=1000000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)

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

dp =[0]*(n+1)

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

for i in [0,1]:
    if dp[i] == -1:
        dp[i] =0
    else:
        dp[i] =1

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

print(dp[-1]%1000000007)

Solution (Python):
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

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

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
status = [True]*(N+2)
for _ in range(M):
    status[int(input())] = False

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

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

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

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
steps = [1 for _ in range(N + 1)]
for _ in range(M):
    i = int(input())
    steps[i] = 0
scores = defaultdict(int)
scores[0] = 1
scores[1] = steps[1]

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

Solution (Python):
n,m = map(int,input().split())
b = [] 
for i in range(n+1):
  if i == 0 or i == 1:
    b.append(1)
  else:
    b.append(b[i-2]+b[i-1])

ans = 1
if m != 0:
  a = list(range(m))
  for i in range(m):
    a[i] = int(input())
    if i == 0:
      ans = ans*b[a[i]-1]%1000000007
    else:
      if a[i] == a[i-1]+1:
        ans = 0
      else:
        ans = ans*b[a[i]-a[i-1]-2]%1000000007
  ans = ans*b[n-a[m-1]-1]%1000000007
  print(ans)
else:
  print(b[n]%1000000007)

Solution (Python):

import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
if M > 0:
    a_set = set(map(int, s[1:]))
else:
    a_set = set()


dp = [0] * (N + 1)

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

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

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

for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if not broken[j]:
            dp[j] += dp[i]


print(dp[N]%mod)

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

mod = 10**9 + 7
dp = [0 for i in range(N+1)]
dp[0] = 1

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

for i in range(M):
    isbroken[A[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])