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):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
broke = []
for j in range(m):
    broke.append(ii())
if n > 1:
    num = [1]
    if len(broke) and broke[0] == 1:
        num.append(0)
        broke.pop(0)
    else:
        num.append(1)

    for i in range(2,n+1):
        if len(broke) and broke[0] == i:
            num.append(0)
            broke.pop(0)
        else:
            num.append((num[-1]+num[-2])%1000000007)
    print(num[-1])
else:
    print(1)

Solution (Python):
def main():
    n, m = map(int, input().split())
    a = set([int(input()) for _ in range(m)])
    if 1 < n:
        dp = [0 for _ in range(n + 1)]
        dp[1] = 0 if 1 in a else 1
        dp[2] = 0 if 2 in a else 1
        dp[2] += dp[1]
        for i in range(3, n + 1):
            if i - 1 not in a:
                dp[i] += dp[i - 1]
            if i - 2 not in a:
                dp[i] += dp[i - 2]
        print(dp[-1] % (10 ** 9 + 7))
    else:
        print(1 if 1 not in a else 0)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))


n, m = load_list()
A = []
for _ in range(m):
    A.append(load())
A = set(A)

dp = dict()

s = list()
s.append(0)

def f(now, goal, A):
    if now > goal:
        return 0
    if now == goal:
        return 1
    
    cnt = 0
    if now + 1 in A:
        pass
    elif now + 1 in dp:
        cnt += dp[now+1]
    else: 
        dp[now+1] = f(now+1, goal, A) 
        cnt += dp[now+1]

    if now + 2 in A:
        pass
    elif now + 2 in dp:
        cnt += dp[now+2]
    else:
        dp[now+2] = f(now+2, goal, A) 
        cnt += dp[now+2]
    return cnt
sys.setrecursionlimit(1000000) 
cnt = f(0, n, A)
print(cnt % 1000000007)

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

if m>=2:
    pre = A[0]
    for i in range(1,m):
        if pre+1 == A[i]:
            print(0)
            exit()
        pre = A[i]
if m==0:
    for i in range(1,n+1):
        if i==1:
            dp[i]=1
        else:
            dp[i] = (dp[i-1]+dp[i-2])%mod
    print(dp[-1])
    exit()


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

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

mod = 10**9+7

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

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

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

mod = 10**9+7

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

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

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect




from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().split())
  A = list(int(readline()) for i in range(m))
  A.append(INF)
  dp = [0]*(n+1)
  dp[0] = 0
  j = 0
  if A[j] == 1:
    dp[1] = 0
    j += 1
  else:
    dp[1] = 1
  
  if n>=2:
    if A[j] == 2:
      dp[2] = 0
      j += 1
    else:
      dp[2] = dp[1] + 1
  
  if n>=3:
    for i in range(3, n+1):
      if A[j] == i:
        dp[i] = 0
        j += 1
      else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
  print(dp[n])
  
if __name__ == '__main__':
  main()

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

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

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

print(dp[0])

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

Solution (Python):
n, m = map(int,input().split())
hole = [int(input()) for _ in range(m)]
k = 0
a, b = 0, 0
x = (10 ** 9 + 7)
for i in range(n):
    if m >= 1:
        if i + 1 == hole[k]:
            a, b = 0, a
        else:
            if i == 0:
                a = 1
            elif i == 1:
                a, b = (a + 1) % x, a % x
            else:
                a, b = (a + b) % x, a % x
        if i + 1 >= hole[k] and k < m - 1:
            k += 1
    else:
        if i == 0:
                a = 1
        elif i == 1:
            a, b = (a + 1) % x, a % x
        else:
            a, b = (a + b) % x, a % x
    
print(a)

Solution (Python):
import math
import sys
sys.setrecursionlimit(100000)
f = math.factorial
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += cmb(k-b, b, p)
        count *= work
print(count%p)

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

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

dp = [0] * (N + 1)
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

print(dp[N])

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

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

dp = [0] * (N + 1)
dp[0] = 1
if issafe[1]:
    dp[1] = 1

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

mod = 1000000007
print(dp[N] % mod)

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

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m+1):
    ans=(ans*x[b[i]])%p
print(ans)

Solution (Python):
import sys

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

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

if n == 1:
    print(1)
    sys.exit()
dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
if m == 0:
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n]%(10**9+7))
else:
    c = 0
    for i in range(1,n+1):
        if i == a[c]:
            dp[i] = 0
            if c < m-1:
                c += 1
        else:
            dp[i] = dp[i-1] + dp[i-2]

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

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

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

Solution (Python):

n, m = map(int, input().split())
a = [1] * (n + 1)
mod=1e9+7
for i in range(m):
    a[int(input())] = 0
b = [1] * (n + 1)
if a[1] == 0:
    b[1] = 0
for i in range(2, n + 1):
    b[i] = int(a[i] * (b[i - 2] + b[i - 1]) % mod)
print(b[n])

Solution (Python):
n,m = map(int, input().split())
break_stair = [False for i in range(n)]
for i in range(m):
    break_stair[int(input())-1] = True
mod = 10**9+7

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

Solution (Python):
import sys


input = sys.stdin.readline

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

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

print(dp[N]%MOD)

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

Solution (Python):
N,M=map(int,input().split())
DP=[100]*(N+1)
DP[0]=1
DP[1]=1
for i in range(M):
	x=int(input())
	DP[x]=0
for i in range(2,N+1):
	if DP[i]!=0:
		if DP[i-1]==0:
			DP[i]=DP[i-2]
		if DP[i-2]==0:
			DP[i]=DP[i-1]
		else:
			DP[i]=DP[i-1]+DP[i-2]
	else:
		continue
print(DP[N]%(10**9+7))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

lst=[None]*(N+1)
def func(n):
    
    
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp



a=[-1]+a+[N+1]
answer=1
for i in range(M+1):
    if a[i+1]-a[i]==1:
        print(0)
        break
    answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
else:
    print(answer)

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

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

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

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

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    N,M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    res = [0]*(N+1)
    res[0] = 1
    k = 0
    for i in range(1,N+1):
        if k<M:
            if i==a[k]:
                k += 1
                continue
        res[i] = (res[i-1]+res[i-2]) % mod
    print(res[-1])


if __name__ == '__main__':
    main()

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


def binary_search(list,target): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)//2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return False
	else:
		return True

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

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

print(dp[n])

Solution (Python):

import sys
input = sys.stdin.readline




'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

fibo = [1, 1]
for i in range(1, 10**5+2):
    fibo.append(fibo[i]+fibo[i-1])

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

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

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break

if not flg:
    print(0)

else:
    ans=1
    if m==1:
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))

    elif m==0:
        print((fibo[n]) % (10**9+7))

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

Solution (Python):
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
S=[]
now=0
for i in range(m):
    a=int(input())
    if i==0 and a==1:
        now=a
        continue
    elif i==0:
        S.append(a-now)
        now=a
        continue
    elif i!=0 and a-now==1:
        print(0)
        sys.exit()
    S.append(a-now-1)
    now=a

if m==0:
    S.append(n-now+1)
else:
    S.append(n-now)

mod=10**9+7
N=10**5+10
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

def cmb(n,r):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


ans=1

for s in S:
    cnt=0
    for i in range((s-1)//2+1):
        cnt+=cmb(s-i-1,i)
        cnt%=mod
    ans=ans*cnt%mod

print(ans%mod)

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

Solution (Python):
n, m = map(int, input().split())
l = {int(input()) for _ in range(m)}
if (n == 1):
    print(1)
else:
    p = 10**9+7
    f = [0] * (n + 1)
    f[0], f[1] = 1, 0 if 1 in l else 1
    for i in range(1, n+1):
        if not i in l:
            f[i] = (f[i - 1] + f[i - 2]) % p

    print(f[n])

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

mod = 1000000007

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

for n in range(N):
    if broken_step[n+1] == 0:
        dp[n+1] += dp[n]*1
    else:
        dp[n+1] = 0
    if broken_step[n+2] == 0:
        dp[n+2] += dp[n]*1
    else:
        dp[n+2] = 0
print(dp[N]%mod)

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


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

print(dp[-1])

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):
N,M =map(int,input().rstrip().split(" "))
ans = [0 for _ in range(N + 3)]
ans[0] = 1
m = []
mc = 0
for _ in range(M):
  m.append(int(input()))
m.append(0)
for i in range(1,N + 1):
  if m[mc] != i:
    ans[i] += ans[i - 1]
    ans[i] += ans[i - 2]
    ans[i] %= 1000000007
  else:
    mc += 1
print(ans[N])

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

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

pat = [0]*(N+2)
pat[0] = 1
if unreachable:
    print(0)
else:
    for i in range(N):
        if i in broken:
            continue
        pat[i+1] = (pat[i+1] + pat[i]) % mod
        pat[i+2] = (pat[i+2] + pat[i]) % mod
    print(pat[N])

Solution (Python):
import sys
input = sys.stdin.readline

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

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

check = set(a)
if 1 in check:
    dp = [0, 0, 1]
elif 2 in check:
    dp = [0, 1, 0]
else:
    dp = [0, 1, 2]
if N < 3:
    print(dp[N])
    exit()
for i in range(3, N+1):
    if i in check:
        dp.append(0)
    else:
        dp.append((dp[-1] + dp[-2])%1000000007)

print(dp[-1])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
n,m=[int(i) for i in input().split()]
dp=[1,1] ;a=set() ; mod=(10**9+7)
for i in range(m):
    a.add(int(input()))
if 1 in a: dp[1]=0
for i in range(2,n+1):
    if i not in a:
        dp.append((dp[-1]+dp[-2])%mod)
    else:
        dp.append(0)
print(dp[-1])

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

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

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

print(dp[N] % MOD)

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

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

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

print(step[-1])

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

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

print(dp[-1])

Solution (Python):
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  n, m = input_list()
  falls = [False]*(n+1)
  for i in range(m):
    falls[int(input())] = True
  
  if n == 1:
    print(1)
    exit(0)

  dp = [0]*(n+1)
  dp[0] = 1
  dp[1] = 0 if falls[1] else 1
  for i in range(2, n+1):
    if falls[i]:
      continue
    dp[i] = dp[i-1] + dp[i-2]
  
  mod = 1000000007
  print(dp[-1]%mod)
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Solution (Python):
import sys
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
a.sort()
for i in range(m-1):
  if a[i+1]-a[i]==1:
    print(0)
    sys.exit()
p=10**9+7  
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
lst=set(list(range(1,n+1)))
A=set(a)
Lst=lst-A
Lst=list(Lst)
if 1 in Lst:
  Lst.remove(1)
for i in Lst:
  dp[i]=dp[i-1]+dp[i-2]
  if p<=dp[i]:
    dp[i]=dp[i]%p
print(dp[n]%p)

Solution (Python):
n,m=map(int,input().split())
a=list(int(input()) for _ in range(m))
a.append(n+1)
key=0
ways = list(0 for _ in range(n))
if a[key] == 1:
    key += 1
else:
    ways[0] = 1

if a[key] == 2:
    key += 1
else:
    ways[1] = ways[0] + 1

for i in range(3, n+1, 1):
    if a[key] == i:
        key += 1
    else:
        ways[i-1] = (ways[i-2] + ways[i-3])%1000000007

print(ways[-1])

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


F = [None] * (N+1)
F[0] = 1
F[1] = 1
for i in range(2, N+1):
  if i-1 in a:
    tmp1 = 0
  else:
    tmp1 = F[i-1]
    
  if i-2 in a:
    tmp2 = 0
  else:
    tmp2 = F[i-2]
    
  F[i] = (tmp1 + tmp2) % p




print(F[N])

Solution (Python):
I=lambda : list(map(int,input().split()))

n,m = I();md=10**9+7;p=0;a=1
dp=[0,1];l=[0]*(10**5+2)
for _ in range(m):
    x=int(input())
    l[x]=1
for i in range(1,n+1):
    if l[i]:
        dp.append(0)
    else:
        dp.append((dp[-1]+dp[-2])%md)
print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N,m=map(int,input().split())
s = set()
for i in range(m):
    s.add(int(input()))
memo={0:1}
mod=1000000007
def climb_stairs(n):
    if memo.__contains__(n):
        return memo[n]
    else:
        if s.__contains__(n):
            return 0
        elif n==1:
            return 1
        else:
            memo[n]=(climb_stairs(n-1)%mod + climb_stairs(n-2)%mod)%mod
            return memo[n]
print(climb_stairs(N))

Solution (Python):
I=lambda:list(map(int,input().split()))
n,m=I()
b=[int(input()) for i in range(m)]
b=list(set(b))
f={}
for i in b:
    f[i]=1
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if not f.get(i,0):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m = I()
broken = [0] * (n + 1)
for i in range(m):
    x, = I()
    broken[x] = 1

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

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

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

Solution (Python):
N, M = map(int, input().split())
a = []
mod = int(1e9 +7)

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

def main():
    is_no_ans = False
    for i in range(M):
        a_i = int(input())
        a.append(a_i)
        if i != 0 and a[i-1]+1 == a_i:
            is_no_ans = True
    if is_no_ans:
        print(0)
        return

    ans = 1
    left = 0
    a.append(N+1)
    for x in a:
        ans = ans* Fib(x - left) %mod
        left = x + 1
    print(ans)
main()

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

if M == 0:
    a = [-1]

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

ans = 1
for j in range(M):
    if a[j] == N or (j + 1 < M and a[j] + 1 == a[j + 1]):
        ans = 0
        break

    if j == 0:
        ans = fib[a[j] - 1]
    else:
        ans *= fib[a[j] - 1 - (a[j - 1] + 1)]
        ans %= p
else:
    ans *= fib[N - a[M - 1] - 1]
    ans %= p

print(ans)

Solution (Python):
N,M = map(int,input().split())
steps = [1,1,2]
for i in range(3,N+1):
    steps.append(steps[i-1]+steps[i-2])
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    if(b<a):
        print(0)
        exit()
    else:
        ans = ans*steps[b-a]%mod
    a = b+2
ans = ans*steps[N-a]%mod
print(ans)

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

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

ban = [False] * (n + 1)

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

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

for i in range(n):
    dp[i] %= MOD
    if ban[i]:dp[i] = 0
    
    if i + 1 <= n:
        dp[i + 1] += dp[i]
    if i + 2 <= n:
        dp[i + 2] += dp[i]

print(dp[n] % MOD)

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


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    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())
a=[0]*(n+3)
mod=10**9+7
for _ in range(m):
    aa=int(input())
    a[aa]=1
dp=[0]*(n+3)
dp[0]=1
for i in range(1,n+1):
    if a[i]==1:
        dp[i]=0
    else:
        if i>=2:
            dp[i]=(dp[i-1]+dp[i-2])%mod
        elif i>=1:
            dp[i]=dp[i-1]
print(dp[n])

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

Solution (Python):
N,M=map(int,input().split())
mod=1000000007
f=[False]*(N+1)
for _ in range(M):
    i=int(input())
    f[i]=True
dp=[0 for _ in range(N+1)]

if N==1:
    if f[1]:
        print(0)
    else:
        print(1)
else:
    if f[1] and f[2]:
        print(0)
        exit()
    elif f[1]:
        dp[1]=0;dp[2]=1
    elif f[2]:
        dp[1]=1;dp[2]=0
    else:
        dp[1]=1;dp[2]=2

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