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

import sys
from operator import itemgetter






















input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr)


MOD = 1000000007  

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    
    
    
    

    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)



if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = {int(next(tokens)) for _ in range(M)}  

    
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if 1 not in a:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if n - 1 not in a:
            dp[n] += dp[n - 1]
            debug(n, "!")
        if n - 2 not in a:
            dp[n] += dp[n - 2]
            debug(n, "?")
    print(dp[N])

Solution (Python):
N, M = map(int, input().split())
MOD = 1000000007
s = [int(input()) for i in range(M)]
s.append(N+1)

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

r = 1

for j in range(1,M):
  if s[j-1] +1 == s[j]:r = 0

if M == 1:
  r = fiv(s[0]-1)*fiv(N-s[0]-1)
else:
  r = r*fiv(s[0]-1)
  for j in range(1,M+1):
      r = r*fiv(s[j]-s[j-1]-2)

print(r%MOD)

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

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

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

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

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

Solution (Python):
def generate_range_combinations(n):
    C = [1] * n
    for i in range(2, n):
        C[i] = (C[i - 1] + C[i - 2]) % DIV
    return C


def solve(n, m, A):
    from collections import defaultdict

    if m == 0:
        C = generate_range_combinations(n + 1)
        return C[-1]

    D = defaultdict(lambda: 0)
    for i in range(m - 1):
        d = A[i + 1] - A[i] - 1
        if d == 0:
            return 0
        D[d] += 1
    D[A[0]] += 1
    D[n - A[-1]] += 1

    ans = 1
    C = generate_range_combinations(max(D.keys()))
    for k, v in D.items():
        ans *= C[k - 1] ** v
        ans %= DIV
    return ans


DIV = 1000000007
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
print(solve(n, m, A))

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

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

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

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

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

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

bs = [1] * (N+1)
for i in range(1, N+1):
    if ngs[i]:
        bs[i] = 0
    elif i == 1:
        bs[i] = 1
    else:
        bs[i] = (bs[i-1] + bs[i-2]) % 1000000007

print(bs[N])

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())
As = [int(input()) for i in range(M)]
"""
100 5
1
23
45
67
89
"""





import numpy as np
import sys





As = np.array(As)
oAs = As[1:]-As[:-1]
if 1 in oAs:
    print(0)
    sys.exit()





stairs = [0]*(N+3)
stairs[0] = 1


start_stage = 0
for i in range(M):
    collapsed_stage = As[i]
    finish_stage = collapsed_stage - 1
    
    continuous_stairs = finish_stage - start_stage
    if continuous_stairs < 2:
        stairs[finish_stage+2] = stairs[start_stage]
        start_stage = finish_stage+2
    else:
        stairs[start_stage+1] = stairs[start_stage]
        for i in range(continuous_stairs-1):
            stairs[start_stage+i+2] = stairs[start_stage+i] + stairs[start_stage+i+1]
        stairs[finish_stage+2] = stairs[finish_stage]
        start_stage = finish_stage+2

if N-start_stage < 2:
    stairs[N] = stairs[start_stage]
else:
    continuous_stairs = N - start_stage
    stairs[start_stage+1] = stairs[start_stage]
    for i in range(continuous_stairs-1):
        stairs[start_stage+i+2] = stairs[start_stage+i] + stairs[start_stage+i+1]
        
        


print(stairs[N]%1000000007)

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

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

Solution (Python):
N, M = map(int, input().split())
rs = [-1] * (N+1)
rs[0] = 1
rs[1] = 1
for m in range(M):
  am = int(input())
  rs[am] = 0
for n in range(1, N):
  rs[n+1] = 0 if rs[n+1] == 0 else rs[n]+rs[n-1]

print(rs[N]%1000000007)

Solution (Python):

n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])

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

if 1 not in aa:
    dp[1] = 1

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

print(dp[-1] % 1000000007)

Solution (Python):
n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*n
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and 1 in s:l[1]=0
else:l[1]=1
for i in range(2,n+1):
    if i in s: l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])

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):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
print(dp[N])

Solution (Python):
MOD = 1000000007

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

T = [-1]*(N+1)

T[0] = 1
T[1] = 1

for i in (A):
    T[i] = 0

    


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

Solution (Python):
n,m = map(int,input().split())
broken = [True] * (n+1)
for _ in range(m):
    broken[int(input())] = False

mod = 10 ** 9 + 7

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

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

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

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

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

print(dp[-1])

Solution (Python):

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

for i in range(m):
    ai.setdefault(int(input()), 0)


dp={}
for i in range(n+1):
    dp.setdefault(i, 0)

dp[0]=1
if 1 in ai:
    dp[1]=0
else:
    dp[1]=1

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


print(dp[n])

Solution (Python):
N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(int(input()))
def fib(n):
  if n==-1:
    return 0
  elif n==0:
    return 1
  else:
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
if len(S)==0:
  c=fib(N)
  print(c%1000000007)
else:
  if S[0]==1:
    c=1
  else:
    c=fib(S[0]-1)
  for i in range(M-1):
    c=c*fib(S[i+1]-S[i]-2)
  c=c*fib(N-S[M-1]-1)
  c=c%1000000007
  print(c)

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


ans = [0] * (N+1)
ans[0] = 1
ans[1] = 1
for a in A: ans[a] = -1
for i in range(2,N+1):
    if ans[i] == -1: continue
    else:
        a1 = ans[i-1]
        a2 = ans[i-2]
        if a1 == a2 == -1: break
        else:
            if a1 == -1: a1 = 0
            if a2 == -1: a2 = 0
            ans[i] = (a1+a2) % div

print(ans[N])

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

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

Solution (Python):
G, N = [int(_) for _ in input().split(" ")]
ret = ()
T = [-1]*(G+1)
T[0] = 1
T[1] = 1
for i in range(N):
  t = int(input())
  T[t] = 0

for i in range(2, G+1):
	if T[i] == -1:
		T[i] = (T[i-1] + T[i-2]) % 1000000007

print (T[G])

Solution (Python):
MOD = 1000000007
n, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
A = set(A)
dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in A:
    dp[1] = 0

step = 2
while True:
    if step == n+1:
        break
    
    if step in A:
        dp[step] = 0
    else:
        dp[step] = (dp[step-1] + dp[step-2]) % MOD
        
    step += 1
    
print(dp[n])

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

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

Solution (Python):
import sys
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=list(map(int,sys.stdin))
danger.append(0)
m=0
if 1 == danger[0]:
  arr[0]=0
  arr[1]=1
  m=1
for i in range(n):
  if i+1 == danger[m]:
    arr[i]=0
    m+=1
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))

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

x=[0]*(N+1)
j=0
if N!=0:
    x[0]=1
if N>1 and M!= 0 and a[0]==1:
    j+=1
else:
    x[1]=1

for i in range(2,N+1): 
    if j==M or i!=a[j]:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0
        j+=1
print(int(x[N]%(1000000007)))

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline

MOD = 1000000007

n, m = map(int, input().split())
f = defaultdict(lambda : 1)
dp = [0] * (n + 1)
for i in range(m):
    a = int(input())
    f[a] = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 1
    else:
        if f[i]:
            dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] % MOD)

Solution (Python):
def LI(): return [int(x) for x in input().split()];
def I(): return int(input());
def S(): return input();
def LS(): return S().split();

dp = [0] * 100010;
ch = [True] * 100010;
n, m = LI();
for _ in range(m):
    ch[I()] = False;
dp[0] = 1;

for i in range(n):
    if ch[i+1]:
        dp[i+1] += dp[i];
    if ch[i+2]:
        dp[i+2] += dp[i];

print(dp[n]%1000000007);

Solution (Python):
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

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

flag = False
for i in range(M-1):
  if (A[i]+1 == A[i+1]):
    flag = True

if flag:
  print(0)
elif M != 0:
  parts = []  
  for i in range(M):
    if i == 0:
      a_list = [x for x in range(0, A[i])]
      parts.append(a_list)
    else:
      a_list = [x for x in range(A[i-1]+1, A[i])]
      parts.append(a_list)
  a_list = [x for x in range(A[M-1]+1, N+1)]
  parts.append(a_list)
  ans = 1
  for part in parts:
    part_ans = fib(len(part))
    ans *= part_ans
  print(ans % 1000000007)
else:
  ans = fib(N+1)
  print(ans % 1000000007)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  dp=[0]*100010

  n,m=LI()

  dp[0]=1
  dp[1]=1

  for _ in range(m):
    dp[I()]=-1

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

    if dp[i-2]!=-1:
      dp[i]+=dp[i-2]
    if dp[i-1]!=-1:
      dp[i]+=dp[i-1]

    dp[i]%=mod

  return dp[n]%mod

print(main())

Solution (Python):
import sys
from fractions import gcd
from functools import reduce
from itertools import combinations

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    mod = 1000000007
    N, M = il()
    a = [True] * (N+1)
    for b in imi(M):
        a[b] = False
    dp = [0] * (N + 1)
    dp[0] = 1
    for now in range(N):
        for next in range(now + 1, min(N, now + 2)+1):
            if a[next]:
                dp[next] += dp[now]
                dp[next] %= mod
    return dp[N]


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

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

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

DIVISOR = 1000000007

for i in range(1,N+1):
    
    back1 = i-1
    back2 = i-2
    sum = 0
    
    if back2 >= 0 and back2 not in S:
        sum += dp[back2]
        sum %= DIVISOR
    if back1 >= 0 and back1 not in S:
        sum += dp[back1]
        sum %= DIVISOR
    
    sum %= DIVISOR
    dp[i] = sum

print(dp[N])

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

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

dp = [0, 1]

for i in range(1, N+1):
    if i in A:
        dp.append(0)
    else:
        dp.append((dp[-2] + dp[-1]) % 1000000007)

print(dp[-1] % 1000000007)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, M = map(int, input().split())
    ng = [0] * 100100
    for _ in range(M):
        a = int(input())
        ng[a] = 1

    MOD = 1000000007

    dp = [0] * 100100
    dp[0] = 1
    for i in range(N):
        if not ng[i + 1]:
            dp[i + 1] += dp[i]
            dp[i + 1] %= MOD
        if not ng[i + 2]:
            dp[i + 2] += dp[i]
            dp[i + 2] %= MOD

    print(dp[N])


if __name__ == '__main__':
    main()

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

mod = 10**9 + 7

u = [0]*(n+1)
F = [0]*(n+1)
for i in range(m):
	x=int(input())
	u[x]=1

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

print(F[n]%mod)

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 next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = (dp[next-1] + dp[next-2])%1000000007

print(dp[N])

Solution (Python):
n, m = map(int, input().split())
ok_step = [1] * (n+1)
for i in range(m):
    ok_step[int(input())] = 0
dp = [0] * (n+1)
dp[0] = 1
for now_s in range(n+1):
    for next_s in range(now_s+1, min(n+1, now_s+3)):
        if ok_step[next_s]:
            dp[next_s] += dp[now_s]
            dp[next_s] %= 1000000007
print(dp[n])

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

dp = [1]*(n+1)

for a in a_list:
    dp[a] = 0

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

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

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

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):
    if i in A:
        dp[i] = 0
    else:
        if i == 1:
            dp[1] = dp[0]
        else:
            dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= mod

ans = dp[N]
print(ans)

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

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

for i in a:
    dp[i] = 0

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

print(dp[N] % MOD)

Solution (Python):
import sys

input = sys.stdin.readline

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

a = {int(input()) for _ in range(m)}

count = 0

stair = [0] * (n + 1)

for index, value in enumerate(stair):
    if index == 0:
        stair[index] = 1
        continue
    if index == 1:
        if index - 1 not in a:
            stair[index] += stair[index-1]
        continue

    if index - 1 not in a:
        stair[index] += stair[index - 1]
        stair[index] %= 1000000007
    if index - 2 not in a:
        stair[index] += stair[index - 2]
        stair[index] %= 1000000007

print(stair[len(stair) - 1])

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

a=set()
for i in range(m):
    tmp=int(input())
    a.add(tmp)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
j=0
for i in range(1,n+1):
  if i in a:
    
    continue
  if i==1:
    dp[1] = dp[0]
    continue
  dp[i] = dp[i-1]+dp[i-2]
  dp[i]%=mod
print(dp[n])

Solution (Python):
from sys import stdin

def main():
  N, M = map(int, stdin.readline().rstrip().split())
  beforeA=-1
  Mlist=[]

  for i in range(M):
    a = int(stdin.readline().rstrip())
    if (a-beforeA)==1:
      print("0")
      exit()
    Mlist.append(a)
    beforeA = a

  Mindex=0
  broken=-2
  if len(Mlist) >0:
    broken = Mlist[Mindex]
  an2=0
  an1=1
  patern=1
  brokenNext=False
  for i in range(1,N+1):
    if broken == i:
      Mindex+=1
      if len(Mlist) > Mindex:
        broken = Mlist[Mindex]
      brokenNext=True
      continue
    if brokenNext:
      brokenNext=False
      an2=0
      continue
    patern=(an1+an2)%1000000007
    an2=an1
    an1=patern
    
  print(patern%1000000007 )

main()

Solution (Python):
from sys import stdin

def main():
  N, M = map(int, stdin.readline().rstrip().split())
  beforeA=-1
  Mlist=[]

  for i in range(M):
    a = int(stdin.readline().rstrip())
    if (a-beforeA)==1:
      print("0")
      exit()
    Mlist.append(a)
    beforeA = a
      
  if N == 1 or (N == 2 and M==1):
    print("1")
    exit()
  if N == 2:
    print("2")
    exit()

  Mindex=0
  broken=-2
  if len(Mlist) >0:
    broken = Mlist[Mindex]
  an2=0
  an1=1
  patern=1
  brokenNext=False
  for i in range(1,N+1):
    if broken == i:
      Mindex+=1
      if len(Mlist) > Mindex:
        broken = Mlist[Mindex]
      brokenNext=True
      continue
    if brokenNext:
      brokenNext=False
      an2=0
      continue
    patern=(an1+an2)%1000000007
    an2=an1
    an1=patern
    
  print(patern%1000000007 )

main()

Solution (Python):
mod = 1000000007
def add(a, b):
    return (a + b) % mod

N, M = map(int, input().split())
Broken_set = set([])
for _ in range(M):
    Broken_set.add(int(input()))

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

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

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 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] %= INF

print(dp[N])

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

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

Solution (Python):
line = input().split()
N = int(line[0])
M = int(line[1])
broken = []
count = 0
step = []
def check(value):
  if count < M:
    return broken[count]==value
  else:
    return False
for i in range(M):
  a = int(input())
  broken += [a]
if check(1):
  step+=[0]
  count += 1
else:
  step +=[1]
if check(2):
  step += [0]
  count += 1
else:
  step += [1+step[0]]
for j in range(2, N):
  if check(j+1):
    step += [0]
    count += 1
  else:
    step += [step[j-2]+step[j-1]]
ans = step[N-1]%(10**9+7)
print(ans)

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

a = set()
for i in range(m):
    a_tmp = int(input())  
    a.add(a_tmp)



dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            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_tmp = int(input())
    a.add(a_tmp)



dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            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 = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

Solution (Python):


N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

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

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007)

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

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

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

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

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

    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%Num)

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

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

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

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


dp[0] = 1
if flag[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1;

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

print(dp[N])

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

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

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


dp[0] = 1
if flag[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1;

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

print(dp[N])