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 fib_memo(n,broken):
    memo = [0]*(n+1)
    memo[0] = 1
    for x in range(1,n+1):
        if x < 1:
            continue
        if broken[x]==1:
            continue
        memo[x] = (memo[x-1] + memo[x-2])%1000000007

    return memo[n]

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
broken = [0]*(n+1)
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)
    broken[x] = 1

result = fib_memo(n,broken)

print(result)

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


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


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


cnt = 0


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


if a[1] == 0:  
    s[1] = 1
else:
    s[1] = 0   

for ni in range(2,N+1):  
    if a[ni] == 0:  
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else: 
        s[ni] = 0


print(s[N])

Solution (Python):
import sys

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

if M == 0:
    alist = set()
else:
    
    alist = set(map(int, sys.stdin))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

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

print(dp[N])

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

mod_num = 10 ** 9 + 7
a = [0] * N

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

val = [0,1]
j = 0
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[j]:
            val[1] = 0
            if len(a) - 1 != j:
                j += 1
 
print(ans)

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

if M == 0:
    alist = set()
else:
    alist = set(int(input()) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

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

print(dp[N])

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

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

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

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


dp = [-1]*(n+1)
dp[0] = 1
for i in para :
    dp[i] = 0
import sys
sys.setrecursionlimit(200000)
def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if dp[cnt] != 0 :  
                dp[cnt] = (dp[cnt-1] + dp[cnt-2]) % mod
                cnt += 1
            else :
                cnt += 1
        return dps(cnt,cantvisit)

dps(1,para)
print("{}".format(dp[-1]%mod))

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

if M == 0:
    alist = set()
else:
    alist = set(int(input()) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

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

print(dp[N])

Solution (Python):
n, m = map(int, input().split())
howmany_list = [-1] * (n+1)
howmany_list[0] = 1
howmany_list[1] = 1

for i in range(m):
  howmany_list[int(input())] = 0

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

print(howmany_list[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()
a = [1] * (n+1)
for i in range(m):
    a[int(input())] = 0
k = [0] * (n+1)
k[0] = 1
for i in range(1,n+1):
    if i == 1 and a[1]:
        k[1] = 1
    elif i >= 2 and a[i]:
        k[i] = k[i-1] + k[i-2]
        k[i] %= 10 ** 9 + 7

print(k[n])

Solution (Python):
def func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
import sys
sys.setrecursionlimit(1000000)
n,m = map(int, input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n))

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

mod_num = 10 ** 9 + 7
a = [0] * N

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

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)
 
print(ans)

Solution (Python):



def main():
    mod = 1000000007
    N, M = map(int, input().split())
    
    a = [0 for i in range(0, N+2)]

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

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

        if a[i-1] != -1:
            a[i] += a[i-1]

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

        a[i] %= mod

    print(a[-1])


if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
a=set(a)
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:
    dp[i]=0
  else:
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n]%1000000007)

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

mod_num = 10 ** 9 + 7
a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)
 
print(ans)

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

if 1 in A:
    ans[1]=0
else:
    ans[1]=1

for n in range(N+1):
    if n>1:
        if n-1 in A and n in A:
            print(0)
            break
        elif n in A:
            ans[n]=0
        else:
            ans[n]=(ans[n-1]+ans[n-2]) % 1000000007
else:
    print(ans[N])

Solution (Python):
import sys
 
n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Solution (Python):

N, M = input().split()

N = int(N)
M = int(M)
a = []
c = []

for i in range(M):

    anew = int(input())
    a.append(anew)

now_a = 0
a.append(-1)
ans = 0

for i in range( N + 1 ):

    if (i == 0):
        c.append(1)
        
    elif (i == 1):

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append(1)

    else:

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append( c[i - 1] + c[i - 2])
        

ans = c[N] % 1000000007

print (ans)

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

patterns = [1]
if stairs[1]:
    patterns.append(0)
else:
    patterns.append(1)

for i in range(2, n + 1):
    if stairs[i]:
        patterns.append(0)
    else:
        patterns.append(patterns[i - 1] + patterns[i - 2])

print(patterns[-1] % 1000000007)

Solution (Python):
NM = [int(i) for i in input().split()]
a = [0] * NM[0]
for _ in range(NM[1]):
    a[int(input()) - 1] = -1

for i in range(NM[0]):
    if (i == 0):
        if(a[i] != -1):
            a[i] = 1
        else:
            a[i] = 0
    elif(i == 1):
        if(a[i] != -1):
            a[i] = a[i - 1] + 1
        else:
            a[i] = 0
    else:
        if(a[i] != -1):
            a[i] = a[i-1] + a[i - 2]
        else:
            a[i] = 0

print(a[NM[0]-1] % (10**9 + 7))

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())
from collections import defaultdict
f = defaultdict(lambda:1)

mod=10**9+7

for i in range(M):
    f[int(input())]=0

b = defaultdict(int)
b[0]=1

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

print(b[N])

Solution (Python):
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_set = set([int(input()) for _ in range(m)])
comb_list = [1, 1]
if 1 in a_set:
    comb_list[1] = 0
for i in range(2, n+1):
    if i in a_set:
        comb_list.append(0)
    else:
        comb_list.append((comb_list[-2]+comb_list[-1])%(10**9+7))
print(comb_list[n])

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

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

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

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])

Solution (Python):
import sys

mod = 10**9 + 7

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []
 
if M == 0:
    print(fibo(N) % mod)
    sys.exit()
 
for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1
 
for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % mod)

Solution (Python):
N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

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

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))

Solution (Python):
from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(999999)
@lru_cache(maxsize=None)
def calc(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    return calc(n - 1) + calc(n - 2)


K = 10 ** 9 + 7

n, m = map(int, input().split())
broken = []
no_reachable = False
for _ in range(m):
    a = int(input())
    if len(broken) and a == broken[-1] + 1:
        no_reachable = True
        break
    broken.append(a)

if not no_reachable:
    a = 0
    cb = 1
    for b in broken:
        stairs = b - a - 1
        cb *= calc(stairs)
        a = b + 1
    cb *= calc(n - a)
    print(cb % K)
else:
    print(0)

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

MOD = 1000000007

def fib(n):
    dp_list = [0] * n
    dp_list[0] = 1
    if n == 1:
        return 1
    dp_list[1] = 2
    
    for i in range(2, n):
        dp_list[i] = dp_list[i - 1] + dp_list[i - 2]
    return dp_list[n - 1]

if M == 0:
    print(fib(N) % MOD)
    sys.exit()

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        
print(count)

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

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % (10**9 +7)
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

print(ans)

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

  s=[0]*n
  if a[0]==1 and a[1] == 1:
    s[0] = 0
    s[1] = 0
  elif a[0] == 1:
    s[0] = 0
    s[1] = 1
  elif a[1] == 1:
    s[0] = 1
    s[1] = 0
  else:
    s[0] = 1
    s[1] = 2

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

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = val[0] + val[1]
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

print(ans % (10**9 +7))

Solution (Python):
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0

for k in a:
	ans *= fib(k - start)
	ans %= INF
	start = k + 1

ans *= fib(N - start + 1)
print(ans % INF)

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

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

Solution (Python):
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

for k in a:
	ans *= fib(k - start)
	ans %= INF
	start = k + 1

ans *= fib(N - start + 1)
print(ans % INF)

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

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

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))

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



print("{}".format(dp[-1]))

Solution (Python):
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

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

for k in a:
	ans *= fib(k - start)
	ans %= INF
	start = k + 1

ans *= fib(N - start + 1)
print(ans % INF)

Solution (Python):
def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]


dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)

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

for i in range(N):
    if i == 0:
        if a[i] != '!':
            a[i] = 1
        else:
            a[i] = 0
    elif i == 1:
        if a[i] != '!':
            a[i] = a[i-1] + 1
        else:
            a[i] = 0
    else:
        if a[i] != '!':
            a[i] = (a[i-1] + a[i-2]) % 1000000007
        else:
            a[i] = 0

print(a[N-1] % 1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib={0:0,1:1,2:1}
for i in range(3,100003):
    fib[i]=fib[i-1]+fib[i-2]
  

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
if m!=0:
    l=[a[0]]
    for i in range(len(a)-1):
        l.append(a[i+1]-a[i]-1)
    l.append(n-a[-1])
    k=1
    for i in l:
        k=fib[i]*k%mod
    print(k%mod)
else:
    print(fib[n+1]%mod)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

Solution (Python):
n,b,*a=map(int,open(0).read().split())
a=set(a)
d=i=0
c=1
while i<n:i+=1;b=(c+d)%(10**9+7)*(not{i}&a);c,d=b,c
print(b)

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


K = 10 ** 9 + 7

n, m = map(int, input().split())
broken = []
no_reachable = False
for _ in range(m):
    a = int(input())
    if len(broken) and a == broken[-1] + 1:
        no_reachable = True
        break
    broken.append(a)

if not no_reachable:
    a = 0
    cb = 1
    for b in broken:
        stairs = b - a - 1
        cb *= calc(stairs)
        a = b + 1
    cb *= calc(n - a)
    print(cb % K)
else:
    print(0)

Solution (Python):
def fib(n):
  a, b = 0, 1
  for i in range(n):
    a, b = b, a + b
    if b > 1000000007:
      b -= 1000000007
  return b

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

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

if 1 in danger:
    steps[1]=0
else:
    steps[1]=1

for this_step in range(2,n+1):
    if this_step in danger:
        ap=0
    else:
        steps[this_step]=steps[this_step-1]+steps[this_step-2]

print(steps[-1]%1000000007)

Solution (Python):
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
a=set(a)
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:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Solution (Python):
n,b,*a=map(int,open(0).read().split())
a=set(a)
d=i=0
c=1
while i<n:i+=1;b=(c+d)%(10**9+7)*(not i in a);c,d=b,c
print(b)

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

Solution (Python):

n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

k = list()
last_ana = -1
for _ in range(m):
    ana = int(input())
    k.append(ana - last_ana - 1)
    last_ana = ana
k.append(n - last_ana)

if 0 in k:
    ans = 0
else:
    k_max = max(k)
    c = [1, 1]
    for i in range(2, k_max):
        c_tmp = c[i - 1] + c[i - 2]
        c.append(c_tmp % BIGNUM)

    ans = 1
    for num in k:
        ans *= c[num - 1]
        ans %= BIGNUM
        if ans == 0:
            break

print(ans)

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)
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]
print(dp[-1]%mod)

Solution (Python):

from math import factorial

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

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan)) % 1000000007
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))

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

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

Solution (Python):

from math import factorial

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

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))

Solution (Python):
n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)

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

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

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

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n-1):
    if step[i]==-1:
        continue
    if step[i+1]!=-1:
        step[i+1]+=step[i]
    if step[i+2]!=-1:
        step[i+2]+=step[i]
print(step[n-1]%c_mod)

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

b = [0 for i in range(n+1)]

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])

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


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

        if i != n-1 and dp[i+2] != -1:
            dp[i+2] += dp[i] % mod

print(dp[-1] % mod)

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

for i in range(N + 1):
  if dp[i] != 'broken':
    dp[i] += dp[i - 1] if (i - 1 >= 0) and dp[i - 1] != 'broken' else 0
    dp[i] += dp[i - 2] if i - 2 >= 0 and dp[i - 2] != 'broken' else 0

BASE = 10**9 + 7
print(dp[-1] % BASE)

Solution (Python):
n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)

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

dp = [1] * (N+1)
for broken in broken_list:
    dp[broken] = 0
for i in range(2, len(dp)):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print (dp[N] % 1000000007)

Solution (Python):
n,m = map(int, input().split())
listA = [int(input()) for i in range(m)]
listB = [0]*(n+2)
for k in range(m):
    listB[listA[k]] = 1
if(n==1 and listB[1]==0):
    a,b = 1,1
elif(n==1 and listB[1]==1):
    a,b = 0,0
elif(listB[1]==1 and listB[2]==1):
    a,b = 0,0
elif(listB[1]==1):
    a,b = 0,1
elif(listB[2]==1):
    a,b = 1,0
else:
    a,b = 1,2

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

print(b%1000000007)

Solution (Python):

N, M = map(int, input().split())
MOD = 10 ** 9 + 7

arrs = set([int(input()) for _ in range(M)])
anss = [0, 1]
for i in range(1, N+1):
    if i in arrs:
        anss.append(0)
    else:
        anss.append((anss[-2] + anss[-1]) % MOD)
print(anss[-1] % MOD)

Solution (Python):
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]:
        Block=Block[1:]+[sum(Block)%mod]
    else:
        Block=Block[1:]+[0]
print(Block[-1])

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

Solution (Python):
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = (al[i-1] + al[i-2])%mod
    if al[i] == 0:
        print(0)
        exit()

print(al[-1])

Solution (Python):
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]==1:
        Block=Block[1:]+[sum(Block)%mod]
        
    else:
        Block=Block[1:]+[0]
print(Block[-1])

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

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

print(dp[N]%mod)

Solution (Python):
def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1)%1000000007)
else:
    pstart = [-1]+start+[n+1] 
    newlist = [] 
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) 
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: 
        ans = 1
        
        for w in newlist:
            
            
            ans = (ans*Fib(w-1))%1000000007
        print(ans)

Solution (Python):
def culc(m):
    a1=0
    a2=1
    for i in range(m):
        a2_=a2
        a2=a1+a2
        a1=a2_
    return a2

N,M=map(int,input().split())
a=[-1]
b=[]
for i in range(M):
    a+=[int(input())]
    b+=[a[-1]-a[-2]-2]
    if a[-1]-a[-2]==1:
        b=[]
        break
else:
    b+=[N-a[-1]-1]
if b==[]:
    sm=0
else:
    sm=culc(b[0])
for i in b[1:]:
    sm=sm*culc(i)
print(sm%1000000007)