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())
memo = [0]*(N+1)
memo[0] = 1
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] != None:
    memo[1] = 1

for i in range(2, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp % mod

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Solution (Python):
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[0] = 1
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] != None:
    memo[1] = 1

for i in range(2, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Solution (Python):
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
mod = 10**9+7

if N > 1:
    memo[2] = 2

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if N > 1 and memo[1] == None and memo[2] != None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)

Solution (Python):
n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007
table = [1,1]
for step in range(2, n+1):
    ans = 0
    if step - 1 not in out:
        ans += table[step-1]
    if step - 2 not in out:
        ans += table[step-2]
    ans %= mod
    table.append(ans)

print(table[n])

Solution (Python):
import sys
sys.setrecursionlimit(200000)
def num_steps(steps, cache={}):
    if steps in out or steps < 0 :
        return 0
    elif steps == 0:
        return 1

    if steps in cache:
        return cache[steps]
    else:
        one = num_steps(steps-1, cache)
        two = num_steps(steps-2, cache)
        ans = one + two
        cache[steps] = ans

        return ans%mod

n, m = map(int, input().split())
out = set(int(input()) for _ in range(m))
mod = 1000000007

print(num_steps(n))

Solution (Python):
n,m=map(int,input().split())
a = set([])
for i in range(m):
	a.add(int(input()))
"""
壊れてるが2回以上続く→0
壊れてるが1回続く→そこは2段限定,RESET.

let Bn = [n段目に登る通り数]
Ex.1
1 2 3 4 5 6
1 2 
結局はDPかな？
"""
dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = 10**9+7
for i in range(1,n+1):
	if i in a:
		pass
	elif i==1:
		dp[i] = dp[i-1] % mod
	else:
		dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n] % mod)

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=1000000007
n,m=mp()
dp=[0]*(n+2)
dp[0]=1
for i in range(m):
    a=int(input())
    dp[a]=-1
for i in range(n):
    if dp[i]==-1:
        continue
    if dp[i+1]>=0:
        dp[i+1]+=dp[i]
        dp[i+1]=dp[i+1]%mod
    if dp[i+2]>=0:
        dp[i+2]+=dp[i]
        dp[i+2]=dp[i+2]%mod
print(dp[-2]%mod)

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

MOD = 10 ** 9 + 7

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


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



print(dp[n])

Solution (Python):
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 1000000007


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


def patterns(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    elif (n < 3):
        return n
    ret = [0]*(n+1)
    ret[1] = 1
    ret[2] = 2
    for i in range(3, n+1):
        ret[i] = ret[i-2] + ret[i-1]
    
    return ret[n]


N, M = list(map(int, input().split()))
a = [0]*M
for i in range(M):
    a[i] = int(input())
a.append(N+1)
start = 0
ans = 1
for lack in a:
    steps = (lack - 1) - start
    
    
    
    ans = (ans * patterns(steps)) % mod
    
    start = lack + 1
print(ans % mod)

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

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

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

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

Solution (Python):

stairs, broken = map(int, input().split())
conditions = [1] * (stairs + 1)
for i in range(broken):
  tmp = int(input())
  conditions[tmp] = 0
  

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

print(conditions[stairs])

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

MOD = 10**9 + 7
res = [0] * (n+1)
res[0] = 1
res[1] = 0 if a[1] == -1 else 1

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

    
    if res[i-1] == 0 and res[i-2] == 0:
        break

    res[i] = (res[i-1] + res[i-2]) % MOD

print(res[-1])

Solution (Python):

"""
Created on Sun May 31 13:40:00 2020

@author: NEC-PCuser
"""
def fibonatch(a, N):
    
    n1, n2 = 1, 1
    if N == 0:
        return 1
    elif N == 1:
        return 1
    else:
        for i in range(N - 1):
            if a[i] == 1:
                n1 = 0
            if a[i + 1] == 1:
                n2 = 0
            n1, n2 = n1 + n2, n1
        return (n1) % 1000000007



if __name__ == "__main__":
    N, M = map(int, input().split())
    a = [0] * N
    for i in range(M):
        a[int(input()) - 1] = 1
    
    print(fibonatch(a, N))

Solution (Python):
n,m=[int(x) for x in input().rstrip().split()]
a=[int(input()) for i in range(m)]
oks=[True for i in range(n+1)]

mod=10**9+7
dp=[0 for i in range(n+1)]
for i in a:
  oks[i]=False

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

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

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

Solution (Python):
import sys
import numpy as np
mod = 1000000007
INF = float("inf")
n,m = map(int,input().split())
dp = [0]*(n+2)
goods = [True] * (n+2)
for _ in range(m):
     x = int(input())
     goods[x] = False

dp[0] = 1
for i in range(n):
    if goods[i]:
        dp[i + 1] += dp[i]
        dp[i + 2] += dp[i]
print(dp[n]%mod)

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

Solution (Python):
fib = [0 for i in range(10**5+1)]
fib[0] = 1
fib[1] = 1
for i in range(2,10**5+1):
    fib[i] = fib[i-1] + fib[i-2] % (10**9+7)
n,m = map(int,input().split())
a = [-1]
for i in range(m):
    ai = int(input())
    if ai - a[i] == 1:
        print(0)
        exit()
    a.append(ai)
a.append(n+1)
ans = 1
for i in range(1,m+2):
    ans = (ans * fib[a[i]-a[i-1]-2]) % (10**9 + 7)
print(ans)

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

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

ok = sorted(set(i for i in range(1, N + 1)) - set(A))

for i in ok:
  if i == 1:
    ans[i] = 1
  else:
    ans[i] = ans[i - 2] + ans[i - 1]
print(ans[-1]%(10**9+7))

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, m, *a = map(int, read().split())
    MOD = 10**9 + 7
 
    if n == 1:
        print(1)
        exit()
 
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    is_broken = [False] * (n+1)
    for i in a:
        is_broken[i] = True
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1
 
    for i in range(2, n + 1):
        if is_broken[i]:
            continue
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
 
    print(dp[-1])
 
if __name__ == '__main__':
    main()

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

mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0

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

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

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

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

Solution (Python):



import sys
 
N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(0, N + 1):
    brake.append(False)
for i in range(1 , M+1) :
    a = int(input())
    brake[a] = True

for i in range(1, N+1) :
    if brake[i] :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
A = deque([int(input()) for _ in range(m)])
memo = [1, 2] + [0] * (n - 2)
if len(A) > 0:
    if A[0] == 1:
        memo[0] = 0
        memo[1] = 1
        A.popleft()
if len(A) > 0:
    if A[0] == 2:
        memo[1] = 0
        A.popleft()
for i in range(2, n):
    if len(A) > 0:
        if A[0] == i + 1:
            A.popleft()
        else:
            memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007
    else:
        memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007
print(memo[n-1])

Solution (Python):
import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [1 for i in range(n)]
for x in a:
    ans[x-1] = 0
for i in range(n):
    if i == 0 and ans[i] == 0:
        ans[0] = 0
    elif i == 1:
        if ans[i] == 1:
            ans[1] += ans[0]
        elif ans[i] == 0:
            ans[1] = 0
    elif i >= 2 and ans[i] == 1:
        ans[i] = (ans[i-1] + ans[i-2])%MOD

print(ans[-1])

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

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

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

print(dp[N])

Solution (Python):


def stairs(n, a):
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, n+1):
        if i in a:
            continue
        dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Solution (Python):


def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, n+1):
        if i in a:
            continue
        dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Solution (Python):


def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, n+1):
        if i not in a:
            dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

Solution (Python):


def stairs(n, a):
    num_list = set(i for i in range(n+1) if i not in a)
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in num_list:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]
            
    result = dp[n] % 1000000007

    print(result)

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


if __name__ == '__main__':
    stairs(n, a)

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

"""
DPを考える
"""

result = [0] * (N+1)
result[0] = 1
if 1 not in A:
    result[1] = 1
mod = 10**9 + 7
for i in range(2,N+1):
    if i not in A:
        result[i] = (result[i-1] + result[i-2])

print(result[N]%mod)

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

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue



ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = set(iln(M))
    dp = [0]*(N+1)
    dp[0] = 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue



ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    A = set(iln(M))
    dp = [0]*(N+1)
    dp[0] = 1

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


if __name__ == '__main__':
    main()

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

flag=[True]*(n+1)
for i in range(m):
    flag[a[i]]=False

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

print(dp[n]%1000000007)

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

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

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]
a.append(0)

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

k = 0

if a[0] == 1:
	dp[1] = 0
	k += 1

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

print(dp[N])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

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

check = [0]*(N+1)
for i in a:
	check[i] = 1

if check[1] == 1:
	dp[1] = 0

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

print(dp[N])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

check = [0]*(N+1)
for i in a:
	check[i] = 1

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
	for j in range(1, 3):
		if not check[i-j]:
			dp[i] = (dp[i] + dp[i-j])%mod

print(dp[N])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = deque([INT() for _ in range(M)])
a.append(0)

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

if a[0] == 1:
	dp[1] = 0
	a.popleft()

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

print(dp[N])

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

print(dp[n])

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

dp = [0]*(N+1)
dp[0] = 1
A = []
for _ in range(M):
    k = int(input())
    A.append(k)
A = sorted(A,reverse = True)

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

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

dp = [0]*(N+1)
dp[0] = 1
A = []
for _ in range(M):
    k = int(input())
    A.append(k)
A = sorted(A,reverse = True)

if len(A)>0:
    a = A.pop()
else: a = -1
        
if a == 1:
    dp[1] = 0
    if len(A)>0:
        a = A.pop()
    if a == 2:
        dp[2] == 0
else:
    dp[1] = 1
    
for i in range(2,N+1):
    if i == a:
        if len(A)>0:
            a = A.pop()
        
    else:
        if dp[i-1] != 0 and dp[i-2] != 0:
            dp[i] = (dp[i-1] + dp[i-2])%mod
        elif dp[i-1] != 0:
            dp[i] = dp[i-1]%mod
        elif dp[i-2] != 0:
            dp[i] = dp[i-2]%mod
        else:
            dp[i] = 0
        
print(dp[-1])

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n,m=n1()
A=n2(m)
A.append(n+1)
b=0
d=[0]*(n+1)
d[0]=1
d[1]=1
for i in range(2,n+1):
    d[i]=d[i-1]+d[i-2]

ans=1
for a in A:
    c=a-1-b
    if a==b:
        print(0)
        break
    else:
        ans*=d[c]
        b=a+1
else:
    print(ans%(10**9+7))

Solution (Python):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)
dp = [0] * (N + 1)
dp[0] = 1
if len(a) > 0:
    A = a.pop()
else:
    A = -1

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]

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

def fib(n):
	if n < 2:
		return fib_list[n]
	elif fib_list[n] != 0:
		return fib_list[n]
	else:
		fib_list[n] = fib(n-1) + fib(n-2)
		return fib_list[n]

tmp = -1
ans = 1

for x in a:
	
	if x == tmp+1:
		print(0)
		exit()
	else:
		ans = ans*fib(x-tmp-2)%mod
		tmp = x

ans = ans*fib(N-tmp-1)%mod
print(ans)

Solution (Python):


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

if m != 0:
    a = [int(input()) for _ in range(m)]
else:
    a = [-1]

mod = 1000000007

if n == 1:
    print(1)
    exit()
elif n == 2:
    if a[0] == 1:
        print(1)
    else:
        print(2)
    exit()


if a[0] == 1:
    a_2, a_1 = 1, 0
    index = 1
else:
    a_2, a_1 = 1, 1
    index = 0

for i in range(2, n+1):
    if index < len(a):
        if i == a[index]:
            a_now = 0
            index += 1
            a_1, a_2 = a_now, a_1
            continue

    a_now = (a_1+a_2) % mod
    
    a_1, a_2 = a_now, a_1
    
print(a_now % mod)

Solution (Python):
mod = 1e9+7
n, m = [int(i) for i in input().strip().split()]

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


dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
  if oks[i-1]:
    dp[i] += dp[i-1]
    dp[i] %= mod
  if i-2>-1 and oks[i-2]:
    dp[i] += dp[i-2]
    dp[i] %= mod
print(int(dp[n]))

Solution (Python):

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    
    As = set(map(int, readlines()))
    
    
    
    
 
    p1, p2 = 1, 1
    if 1 in As:
        p1 = 0

    for i in range(2, n + 1):
        if i in As:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()

Solution (Python):

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    
    As = list(map(int, readlines()))
    
    
    
    
    broken = [False] * (n + 1)
    for a in As:
        broken[a] = True
    p1, p2 = 1, 1
    if broken[1]:
        p1 = 0

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

    print(p1)


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


if __name__ == "__main__":
    print(solve())

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


if __name__ == "__main__":
    print(solve())

Solution (Python):
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a=set(a)
dp=[0]*(N+1)
dp[0]=1
anlist=[]
inf=10**9+7
if 1 not in a:
  dp[1]=1
else:
  dp[1]=0
for i in range(2,N+1):
  if i in a:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[N]%inf
print(ans)