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

from operator import mul
from functools import reduce


n, m = [int(i) for i in input().split()]
arr = [int(input()) for i in range(m)]


arr.append(n+1)
arr.insert(0, -1)

div_arr = [arr[i+1]-arr[i]-1 for i in range(len(arr)-1)]


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

print(reduce(mul, [Fib(i+1) for i in div_arr])%1000000007)

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


for j in range(2,N+1):
  if A[j]!=0:
    A[j]=A[j-1]+A[j-2]
    

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

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


for j in range(2,N+1):
  if A[j]!=0:
    A[j]=A[j-1]+A[j-2]
    

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

Solution (Python):
from operator import mul
from functools import reduce

n, m = [int(i) for i in input().split()]
arr = [int(input()) for i in range(m)]
arr.append(n+1)
arr.insert(0, -1)
div_arr = [arr[i+1]-arr[i]-1 for i in range(len(arr)-1)]


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

if 0 in div_arr:
  print(0)
else:
  print(reduce(mul, [Fib(i+1) for i in div_arr])%1000000007)

Solution (Python):










import math
import sys
import itertools
import queue

mod = 1000000007

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 2)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

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

Solution (Python):










import math
import sys
import itertools
import queue

mod = 1000000007

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 2)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

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

Solution (Python):










import math
import sys
import itertools
import queue

mod = 1000000007

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 2)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

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

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

for i in range(M):
  d[a[i]] = 1

t[0]=t[1]=1
if M>0:
  t[1] = 0 if (a[0]==1) else 1

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

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

Solution (Python):
import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

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

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)

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

count = 0
for i in a:
    if i+1 in a:
        print(0)
        exit()

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

print(dp[N])

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

now = 0
if 1 in a:
    prev1 = 0
else:
    now = 1
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now

print(now%Num)

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

Solution (Python):

import bisect
from collections import defaultdict

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

    current_step = 0
    prev_prev_step = 1
    if 1 in As:
        prev_step = 0
    else:
        prev_step = 1
        current_step = 1

    for i in range(2, N+1):
        if i in As:
            current_step = 0
        else:
            current_step = (prev_step + prev_prev_step) % BIG_NUM
        prev_prev_step = prev_step
        prev_step = current_step

    print(current_step)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = [int(x) for x in input().split()]
bad = [False for i in range(n + 1)]
for i in range(m):
  bad[int(input())] = True
mod = 10 ** 9 + 7
dp = [0 for i in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
  if bad[i]: 
    continue
  x1 = dp[i - 1] if (i > 0) and not bad[i - 1] else 0
  x2 = dp[i - 2] if (i > 1) and not bad[i - 2] else 0
  dp[i] = x1 + x2
  if dp[i] >= mod:
    dp[i] -= mod
print(dp[n])

Solution (Python):



N,M = list(map(int,input().split()))
B = [True] * N

for _ in range(M):
    B[int(input())-1] = False
dp = [0] * N
if B[0]:
    dp[0] = 1
if N >= 2 and B[1]:
    dp[1] = dp[0] + 1 
mod = 10**9 + 7
for i in range(2,N):
    if B[i] :
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

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

Solution (Python):
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

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

Solution (Python):



n,m = list(map(int,input().split()))
a = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
flg = [True]*(n+1)
mod = 1000000007
for i in a:
    flg[i] = False
dp[0] = 1
for i in range(1,n+1):
    if flg[i]:
        if i == 1:
            dp[i] += dp[i - 1]
        else:
            dp[i] += dp[i - 2] + dp[i - 1]

    dp[i] %= mod
print(dp[n])

Solution (Python):
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)

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

counts = [1,1]+[0 for _ in range(10**6)]

for i in range(M):
    counts[L[i]-1] = -1

MOD = 10**9 + 7
for i in range(10**5+1):
    if counts[i] == -1:
        continue
    if counts[i+1] != -1:
        counts[i+1] += counts[i]
        counts[i+1] %= MOD
    if counts[i+2] != -1:
        counts[i+2] += counts[i]
        counts[i+2] %= MOD
print(counts[N-1]%MOD)

Solution (Python):
step = [int(i) for i in input().split()]
breaked_step = [int(input()) for i in range(step[1])]
dp = [1] * (step[0] + 1)
ans = 0
ans_ptn = 0
par = 1000000007

"""for i in range(len(breaked_step) - 1):
    if breaked_step[i + 1] - breaked_step[i] == 1:
        ans = 0
    else:
        ptn = breaked_step[i + 1] - breaked_step[i]
        ans_ptn += ptn * 2
        print("breaked_step[i + 1] - breaked_step[i]:{} - {}".format(breaked_step[i+1], breaked_step[i]))
        print("ans_ptn:{}".format(ans_ptn))

ans = ans_ptn % par"""
for i in breaked_step:
    dp[i] = 0

for j in range(1, step[0]):
    
    if dp[j + 1] != 0:
        dp[j + 1] = (dp[j] + dp[j - 1]) % par
        

print(dp[step[0]])

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

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


for i in range(2, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1

print(dp[-1])

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


broken = [False] * 100100
for i in a:
	broken[i] = True


dp = [0] * 100100


dp[0] = 1


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

print(dp[n])

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

fib = [0, 1]
for i in range(100100):
	fib.append((fib[i] + fib[i + 1] % MOD))

res = 1
for i in range(m + 1):
	p, q = a[i], a[i + 1]
	res = (res * fib[q - p - 1]) % MOD

print(res)

Solution (Python):

def fib(n):
    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a + b
    return b

N, M = map(int,input().split())
break_step = []
step_list = [i for i in range(N+1)]
for i in range(M):
    break_step.append(int(input()))
count_list = []
count = 0
for i in break_step:
    count = i - count
    count_list.append(count)
    count = i + 1
count = N - count + 1
count_list.append(count)
ans = 1
for i in count_list:
    ans = ans * fib(i)
if 0 in  count_list:
    print(0)
else:
    print(ans%1000000007)

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

P = 10**9+7
dp = [1]*(N+1)

for i in List:
    dp[i]=0

for j in range(1, N):
    if dp[j+1]!=0:
        dp[j+1] = (dp[j]+dp[j-1])%P
        
print(dp[N])

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

P = 10**9+7
dp = [1]*(N+1)

for i in List:
    dp[i]=0

for j in range(1, N):
    if dp[j+1]!=0:
        dp[j+1] = (dp[j]+dp[j-1])%P
        
print(dp[N])

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

P = 10**9+7
dp = [1]*(N+1)

for i in List:
    dp[i]=0

for j in range(1, N):
    if dp[j+1]!=0:
        dp[j+1] = dp[j]+dp[j-1]
        
print(dp[N]%P)

Solution (Python):


[N, M] = [int(i) for i in input().split()]
a_list = []
for m in range(M):
    a_list.append(int(input()))

stairs_status = [-1] * (N + 1)
stairs_status[0] = 1
for a in a_list:
    stairs_status[a] = 0

for n in range(1, N + 1):
    if n == 1:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1]
    else:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1] + stairs_status[n - 2]


print(stairs_status[-1] % 1000000007)

Solution (Python):


[N, M] = [int(i) for i in input().split()]
a_list = []
for m in range(M):
    a_list.append(int(input()))

stairs_status = [-1] * (N + 1)
stairs_status[0] = 1
for a in a_list:
    stairs_status[a] = 0

for n in range(1, N + 1):
    if n == 1:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1]
    else:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1] + stairs_status[n - 2]


print(stairs_status[-1] % 1000000007)

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):
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
pat = [0]*(N+1)
for i in range(N+1):
  if i == 0:
    pat[i] = 1
  else:
    element = a[0] if len(a) != 0 else -1
    pat[i] = pat[i-1] + pat[i-2] if i != element  else 0
    if i == element:
      a.pop(0)
print(pat[-1]%1000000007)

Solution (Python):

"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a and N>=2 :
    f[1] = 0
elif 1 not in a and N>=2:
    f[1] = 1

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

if N == 1:
    print(f[N-1])
else:       
    print((f[N-1]+f[N-2]) % mod)

Solution (Python):
import sys
import numpy as np
MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()

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

LARGE = 10**9 + 7

r_arr = [0]*(N+1)
r_arr[0] = 1
if a_dict.get(1, 0) == 1:
    r_arr[1] = 0
else:
    r_arr[1] = 1

for i in range(2, N+1):
    if a_dict.get(i, 0) == 1:
        pass
    else:
        r_arr[i] = (r_arr[i-1] + r_arr[i-2]) % LARGE

print(r_arr[-1])

Solution (Python):
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    num = 1000000007
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] = (ans[i - 2] + ans[i - 1]) % num
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    num = 1000000007
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] += (ans[i - 2] + ans[i - 1]) % num
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] += (ans[i - 2] + ans[i - 1]) % 1000000007
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    for _a in a:
        ans[_a] = -1
    ans[0] = 1
    ans[1] = 1 if ans[1] == 0 else 0
    for i in range(2, n + 1):
        if ans[i] == -1:
            ans[i] = 0
            continue
        ans[i] += ans[i - 2] % 1000000007
        ans[i] += ans[i - 1] % 1000000007
    return str(ans[-1] % 1000000007)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, M = map(int, input().split(" "))
	N += 1
	
	DP = [-1 for i in range(N)]
	DP[0] = 1
	DP[1] = 1
	
	for i in range(M):
		tmp = int(input())
		DP[tmp] = 0

	for i in range(2, N):
		if DP[i] == 0:
			continue
		else:
			DP[i] = (DP[i-1] + DP[i-2]) % 1000000007
		
	print(DP[-1])
	
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys
import numpy as np
MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()

Solution (Python):
import sys

n, m = map(int, input().split())
aaa = set()
if m != 0:
    for _ in range(m):
        aaa.add(int(input()))
    
    
dp = [0] * (n + 1) 
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0 
MOD = int(1e9) + 7

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

Solution (Python):
N, M = map(int, input().split())
MOD = 10**9 + 7
exist = [1 for _ in range(N+2)]
for _ in range(M):
    exist[int(input())] = 0
dp = [0 for _ in range(N+2)]
dp[0] = 1
for i in range(N):
    dp[i+1] = (dp[i+1] + dp[i] * exist[i+1]) % MOD
    dp[i+2] = (dp[i+2] + dp[i] * exist[i+2]) % MOD
print(dp[N])

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

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

lst = [0] * N
pre1 = 0
pre2 = 0
skips = set([int(input()) for _ in range(M)])
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = (lst[x - 1] + lst[x - 2]) % 1000000007

if N == 1:
    print(lst[-1])
else:
    print((lst[-1] + lst[-2]) % 1000000007)

Solution (Python):

N,M=map(int,input().split())
a=[]
broke={} 
broke[0]=0
for i in range(1,N+1):
    broke[i]=0

f={}
f[0]=0 
num=0 
check=0 

for i in range(M):
    a.append(int(input()))
    n=a[i]
    broke[n]=1 
    f[n]=0

for i in range(M-1): 
    dif=a[i+1]-a[i]
    if dif==1:
        check=1
        break
        
if (1 in a)==True: 
    f[1]=0
else:
    f[1]=1
if (2 in a)==True: 
    f[2]=0
elif f[1]==0: 
    f[2]=1
else:
    f[2]=2

if check==0:
    for i in range(1,N-1): 
        if broke[i+2]==1:
            continue
        f[i+2]=f[i+1]+f[i]
    num=f[N]


    
print(num%1000000007)

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

da = max([a[i+1] - a[i] for i in range(len(a)-1)])
b = [0 for i in range(da+1)]
b[0] = 1
b[1] = 1
for i in range(2, da + 1):
    b[i] = b[i-1] + b[i-2]

ans = 1
MOD = 1000000007
for j in range(1, M+2):
    index = a[j] - a[j-1] - 2
    if index == -1:
        ans = 0
        break
    ans = ans * b[index]
    ans = ans % MOD
print(ans)

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

for _ in range(n):
    b.append(b[-1] + b[-2])

if m == 0:
    ans = b[n + 1]
else:
    c.append(a[0])
    for i in range(m - 1):
        c.append(a[i + 1] - a[i] - 1)
    c.append(n - a[m - 1])

    for i in c:
        ans *= b[i]

print(ans % 1000000007)

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

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

print(ret[len(ret)-1]%mod)

Solution (Python):
from collections import deque

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

A = deque()
dp = [0] * N
for i in range(M):
  A.append(int(input()))
A.append(N+1)

if N == 1:
  print(1)

elif N == 2:
  if 1 in A:
    print(1)
  else:
    print(2)
    
else:
  a = A.popleft()
  if a != 1:
    dp[0] = 1
  else:
    a = A.popleft()
    
  if a != 2:
    dp[1] = dp[0] + 1
  else:
    a = A.popleft()
    
  for i in range(2,N):
    if a != i+1:
      dp[i] = dp[i-1] + dp[i-2]
    else:
      a = A.popleft()
  print(dp[-1]%1000000007)

Solution (Python):
n,m=map(int,input().split())
fall=[0]*(n+1)
for i in range(m):
    fall[int(input())]=1
dp=[0]*100010
dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if fall[next]==0:
            dp[next]+=dp[now]
            dp[next]%=1000000007
print(dp[n])

Solution (Python):
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[1]*100010
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]
print(dp[n]%1000000007)

Solution (Python):


n,m=map(int,raw_input().split())
a={int(raw_input()) for i in xrange(m)}

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

Solution (Python):



INF = 10**9+7

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    la = [False for _ in range(100001)]
    for _ in range(m):
        la[ri()] = True
    dp = [0 for _ in range(100001)]
    dp[0] = 1
    for i in range(1, n+1):
        if la[i]:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1]+dp[i-2]) % INF
    print(dp[n])


if __name__ == '__main__':
    main()

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

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

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

print(dp[N])

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

Solution (Python):
N,M = map(int,input().split())
A = set()
for i in range(M):
    A.add(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod
print(count[N])

Solution (Python):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))
if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])

Solution (Python):
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [0] * (N+1)
dp[0] = 1
a = set()
for _ in range(M):
    a.add(int(input()))
if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[N])

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

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

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

if 1 in a:
    if 2 in a:
        print(0)
        exit()
    dp[2] = 1
    start = 3
else:
    dp[1] = 1
    start = 2
for i in range(start, N+1):
    if i in a:
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD

print(dp[N])

Solution (Python):
def fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
if m != 0:
  a = [int(input()) for i in range(m)]
  ans = fib(a[0])
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
n,m = [int(i) for i in input().split()]
a = {int(input()) for i in range(m)}
dp = {}
def stairs(step):
  if step in a:
    return 0
  if step == 1:
    return 1
  if step == 2:
    return stairs(step-1) + 1
  if step in dp.keys():
    return dp[step]
  else:
    dp[step] = stairs(step-1) + stairs(step-2)
    return dp[step]
print(int(stairs(n)%1000000007))

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

MOD = 1000000007

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

broken_step = []
p_a = -1
for i in range(M):
    a = int(input())
    if (a - p_a == 1):
        print("0")
        exit()
    else:
        p_a = a
    broken_step.append(a-1)

count_0 = 0
count_1 = 1
next_broken = 0
pre_is_broken = False
for i in range(N):
    if (next_broken >= len(broken_step) or i != broken_step[next_broken]):
        if (pre_is_broken):
            count_0 = 0
            pre_is_broken = False
        else:
            count_0, count_1 = count_1, count_0 + count_1
            count_0 %= MOD
            count_1 %= MOD
    else:
        next_broken+=1
        count_0 = 0
        pre_is_broken = True

print(count_1)

Solution (Python):
n,m = list(map(int,input().split()))
L = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
for i in range(n):
    if i + 1 not in L:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 not in L and i+2 < n+1 :
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n])

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

for i in range(n):
    if i+1 not in aa:
        l[i+1]+=l[i]
        l[i+1]=l[i+1]%mod
    if i+2 not in aa and i+2<n+1:
        l[i+2]+=l[i]
        l[i+2]=l[i+2]%mod

print(l[n])

Solution (Python):
n,m = list(map(int,input().split()))
L = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
for i in range(n):
    if i + 1 not in L:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 not in L and i+2 < n+1 :
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n])

Solution (Python):
n,m = list(map(int,input().split()))
L = set(int(input()) for _ in range(m))
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
for i in range(n):
    if i + 1 not in L:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 not in L and i+2 < n+1 :
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n])

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

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
broken = [False] * (N + 1)
for aa in a:
    broken[aa] = True

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

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