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
n, m = map(int, input().split())
bf = -1
way = [-1] * (n+1)
way[0] = 1
way[1] = 1
mod = 10 ** 9 + 7
for i in range(m):
    tmp = int(input())
    if bf + 1 == tmp:
        print(0)
        sys.exit()
    bf = tmp
    way[tmp] = 0
for i in range(2, n+1):
    if way[i] == -1:
        way[i] = way[i-2] + way[i-1]
print(way[n] % mod)

Solution (Python):
N,M = map(int, input().split())
A = [0]*M
for i in range(M):
    A[i] = int(input())
if M != 0:
    
    L = A[0]+1
    if L < N - A[M-1]:
        L = N - A[M-1]
    for i in range(M-1):
        L1 = A[i+1]-A[i]
        if L1 > L:
            L = L1
else:
    L = N +2
    
x = [0]*L
x.insert(0,0)
x.insert(1,1)
if L >2:
    for i in range(L-2):
        x[i+2] = x[i+1] + x[i]
if M != 0:
    S = x[A[0]] * x[N - A[M-1]]
    for i in range(M-1):
        S *= x[A[i+1]-A[i]-1]
else:
    S = x[N+1]
print(S%1000000007)

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

Solution (Python):

N, M = map(int, input().split())
dp = [-1] * (N+1)

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

for i in range(M):
    tmp = int(input())
    dp[tmp] = 0
    
for i in range(2, N+1, 1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
        
print(dp[N]%1000000007)

Solution (Python):

N, M = map(int, input().split())
dp = [-1] * (N+1)

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

for i in range(M):
    tmp = int(input())
    dp[tmp] = 0
    
for i in range(2, N+1, 1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007
print(dp[N])

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

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


MOD = 10**9 + 7

z = set(a)
 

x = [0 for _ in range(n + 1)]

x[0] = 1

x[1] = int(1 not in z)

for i in range(2, n + 1):

    if i not in z:

        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[n])

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

MOD = 10 ** 9 + 7

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

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

print(dp[N])

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

MOD = 10 ** 9 + 7

am = set()
for a in A:
	am |= {a}

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

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


print(dp[N])

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

MOD = 10 ** 9 + 7

am = {}
for a in A:
	am[a] = True

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

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


print(dp[N])

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

l = [0]*(N+10)
l[0] = 1
for a in A:
    l[a] = -1

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

print(l[N])

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

dp = [0 for _ in range(n+1)]
broken_id = 0

dp[0] = 1
if broken_id < m and a[broken_id] == 1:
  broken_id += 1
  dp[1] = 0
else:
  dp[1] = 1

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

Solution (Python):

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

MOD = 10**9 + 7
A = set(a)


dp = [0 for _ in range(N + 1)]
dp[0] = 1
dp[1] = int(1 not in A)
for i in range(2, N + 1):
    if i not in A:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]


print(ans)

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = (a1 + a2) % 1000000007
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

    ans = ans * fib(n - li[m-1]) % 1000000007
    print(ans)

else:
    print(fib(n+1))

Solution (Python):






import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

dp = [0] * (N + 1)

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

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

print(dp[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 = map(int, input().split(" "))
a = set()
for i in range(m):
    a.add(int(input()))

waysFrom = {}
waysFrom[n - 1] = 0 if n - 1 in a else 1
waysFrom[n - 2] = 0 if n - 2 in a else 1 + waysFrom[n - 1]

for i in reversed(range(n - 2)):
    if i in a:
        waysFrom[i] = 0
    else:
        waysFrom[i] = waysFrom[i + 1] + waysFrom[i + 2]
        if waysFrom[i] == 0:
            waysFrom[0] = 0
            break

print(waysFrom[0] % 1000000007)

Solution (Python):
from collections import deque

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

tmp = [0 for _ in range(N + 1)]

now = 0
if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if (2 not in A) and N >= 2:
    tmp[2] = tmp[1] + 1
    
else:
    now += 1

for i in range(3, N+1):
    
    try:
        if i != A[now]:
            tmp[i] = tmp[i-1] + tmp[i-2] 
            
        else:
            now += 1
        
    except:
        tmp[i] = tmp[i-1] + tmp[i-2] 

    
print(tmp[-1]%(10**9+7))

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

broken = [False] * (N + 1)
for ai in a:
  broken[ai] = True

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

idx = 0
for pos in range(1, N + 1):
    if broken[pos]:
        memo[pos] = 0
    elif pos < 2:
        memo[pos] = (memo[0]) % (10 ** 9 + 7)
    else:
        memo[pos] = (memo[pos - 2] + memo[pos - 1]) % (10 ** 9 + 7)


print(memo[-1])

Solution (Python):
N,M = map(int,input().split())
a_s = []
for _ in range(M):
  a_s.append(int(input()))
a_s.append('END')
  
dp = []
a_cursor = 0
for i in range(N+1):
  if i == a_s[a_cursor]:
    dp.append(0)
    a_cursor += 1
  else:
    if i == 0:
      dp.append(1)
    elif i == 1:
      dp.append(1)
    else:
      dp.append((dp[i-1]+dp[i-2])%1000000007)
      
print(dp[-1])

Solution (Python):


n, m = map(int, input().split())
MOD = 1000000007
if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []

a.append(-1) 
a_i = 0




step = [0] * (n+2)
step[-1] = -1 
step[0] = 1 

for i in range(1, n+1):
    if a[a_i] == i:
        step[i] = -1 
        a_i += 1
    else:
        if step[i-2] == step[i-1] == -1:
            print(0) 
            exit()
        elif step[i-2] == -1 or step[i-1] == -1:
            step[i] = max(step[i-2], step[i-1]) 
        else:
            step[i] = (step[i-2] + step[i-1]) % MOD 

print(step[n])

Solution (Python):
def fib(num_steps):
    xb = 0
    xa = 1
    if num_steps == 0:
        return xa
    else:
        for i in range(num_steps):
            tmp = xa
            xa = xa + xb
            xb = tmp
    
    return xa

N, M = map(int, input().split())
ways = 1
now = 0

for i in range(M):
    hole = int(input())
    diff = (hole - 1) - now

    if diff < 0:
        ways *= 0
    else:
        ways *= fib(diff)

    now = hole + 1

if now < N:
    ways *= fib(N - now)

print(ways % 1000000007)

Solution (Python):

n, m = map(int, input().split())
MOD = 1000000007
if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []

a.append(-1)
a_i = 0

step = [0] * (n+2)
step[-1] = -1
step[0] = 1
for i in range(1, n+1):
    if a[a_i] == i:
        step[i] = -1
        a_i += 1
    else:
        if step[i-2] == step[i-1] == -1:
            print(0)
            exit()
        elif step[i-2] == -1 or step[i-1] == -1:
            step[i] = max(step[i-2], step[i-1])
        else:
            step[i] = (step[i-2] + step[i-1]) % MOD
            
print(step[n])

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

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

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

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

if step[1] == -1:
    step[1] = 1
for i in range(2, N+1):
    if step[i] == 0:
        continue
    else:
        step[i] = step[i-2]+step[i-1]
print(step[-1]%num)

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

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,M = na()
MOD=1000000007

a=[]
dp = [0]*(N+1)
dp[0]=1
a = [ni() for i in range(M)]
isbro = [1]*(N+1)
for i in range(M):
    isbro[a[i]]=0

for i in range(N):
    if(i-1>=0):
        dp[i+1] = dp[i]*isbro[i] + dp[i-1]*isbro[i-1]
    else:
        dp[i+1] = dp[i]*isbro[i]
    dp[i+1]%=MOD

print(dp[N])

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,M = na()
MOD=1000000007

a=[]
dp = [0]*(N+1)
dp[0]=1
a = [ni() for i in range(M)]
isbro = [1]*(N+1)
for i in range(M):
    isbro[a[i]]=0

for i in range(N):
    if(i-1>=0):
        dp[i+1] = dp[i]*isbro[i] + dp[i-1]*isbro[i-1]
    else:
        dp[i+1] = dp[i]*isbro[i]
    dp[i+1]%=MOD

print(dp[N])

Solution (Python):
n, m = map(int, input().split())
if m > 0:
    a = [int(input()) for i in range(m)]
    interval_max = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()
        interval_max = max(interval_max, a[i+1] - a[i])
else:
    a = []
    interval_max = n
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

fibb = [0]*(max(interval_max+2, 3))
fibb[0] = fibb[1] = fibb[2] = 1
for i in range(3,interval_max+2):
    fibb[i] = (fibb[i-2] + fibb[i-1]) % 1000000007
sum_step = 1

if m == 0:
    sum_step = fibb[n+1]
else:
    for i in range(len(a)-1):
        if i == 0 or i == len(a)-2:
            sum_step *= fibb[a[i+1] - a[i]]
            
        else:
            sum_step *= fibb[a[i+1] - a[i] - 1]
            
        sum_step = sum_step % 1000000007
print(sum_step)

Solution (Python):

import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM
 
 
STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0
 
 
listM={int(input()) for i in range(M)}
dp[0] = 1
 
for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        
    
        
print(dp[N] % 1000000007)

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

if N==1:
  print(1)
  exit()

A = [0]*N
a_prev = None
for i in range(M):
  a_i = int(input())
  if a_prev == a_i:
    print(0)
    exit()
  A[a_i] = 1  
  a_prev = a_i

N_2 = 1
N_1 = 1  
ans = 0
for i in range(1, N):
  if A[i]==1:
    N_1 = 0
  ans = (N_1 + N_2)%1000000007
  N_2 = N_1
  N_1 = ans
print(ans)

Solution (Python):
N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(A)):
  steps=A[i]-A[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
  res*=patern_nmu
  res%=1000000007
print(res)

Solution (Python):
import sys
N, M = map(int, input().split())
 
dp_f = [None] * (10**5 + 2)
dp_f[1] = 1
dp_f[2] = 1
for i in range(3, 10**5 + 1):
    dp_f[i] = dp_f[i-1] + dp_f[i-2]
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]
 
if M == 0:
    m = f(N+1)
    m %= 1000000007
    print(m)
    sys.exit(0)
 
A = [int(input()) for i in range(M)]
 
S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])
 
m = 1
for s in S:
    m *= f(s)
    m %= 1000000007
 
print(m)

Solution (Python):
import sys
N, M = map(int, input().split())
 
dp_f = [None] * (10**5 + 2)
dp_f[1] = 1
dp_f[2] = 1
for i in range(3, 10**5 + 1):
    dp_f[i] = dp_f[i-1] + dp_f[i-2]
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]
 
if M == 0:
    m = f(N+1)
    m %= 1000000007
    print(m)
    sys.exit(0)
 
A = [int(input()) for i in range(M)]
 
S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])
 
m = 1
for s in S:
    m *= f(s)
    m %= 1000000007
 
print(m)

Solution (Python):
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

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

Solution (Python):
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

if n==1:
    print(1)
    exit()

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

Solution (Python):
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

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

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)

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

f = [0] * (N + 1)

f[0] = 1
f[1] = int(1 not in broken_set)

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

print(f[N])

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

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

for i in range(N):
    if (i + 1) <= N and A[i + 1] == 0:
        dp[i + 1] += dp[i]
    if (i + 2) <= N and A[i + 2] == 0:
        dp[i + 2] += dp[i]


print str(dp[N]%1000000007)

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    else:
        p, q = 1, 0
        for j in range(steps):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

Solution (Python):

N,M = list(map(int,input().split(" ")))
NUM = 1000000007
ans = 1
f = [-1] * (N+1)
f[0] = 1
f[1] = 1
for _ in range(M):
    now = int(input())
    f[now] = 0

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

ans = f[N]
print(ans )

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

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

def main_nondp():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    D = [0] * (M+1)
    if M == 0:
        D[0] = N
    else:
        D[0] = A[0] - 1
        for i in range(1, M):
            t = A[i] - A[i-1] - 2
            if t <= -1:
                print(0)
                return
            D[i] = t
        D[M] = N - A[M-1] - 1
    n = 1
    memo = fib_memo(max(D))
    for d in D:
        n = (n * memo[d]) % MOD
    print(n)

def main():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    AS = set(A)
    dp = [0] * (N+9)  
    dp[0] = 1
    for i in range(1, N+1):
        if i in AS:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    print(dp[N])

main()

Solution (Python):
N,M=map(int, input().split())
a=[True for _ in range(N+10)]
for _ in range(M):
  a[int(input())]=False
D=1000000007

DP=[0 for _ in range(N+10)]
DP[0]=1
for i in range(N):
  for j in [1,2]:
    if a[i+j]:
      DP[i+j]+=DP[i]
      
print(DP[N]%D)

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

A = [False] * (N + 1)

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

step = [0] * (N + 1)

step[0] = 1

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

print(step[N])

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

for i, x in enumerate(z):
     if i == 0:
          z[i] = 1
     elif i == 1 and z[i] != 0:
          z[i] = 1
     elif z[i] == 0:
          continue
     elif z[i-1] == 0 and z[i-2] == 0:
          print(0)
          exit()
     else:
          z[i] = z[i-1] + z[i-2]
print(z[-1] % 1000000007)

Solution (Python):
mod=10**9+7
def f(a,r):
    s=[[0,0],[0,0]]
    s[0][0]=(a[0][0]*r[0][0]+a[0][1]*r[1][0])%mod
    s[0][1]=(a[0][0]*r[0][1]+a[0][1]*r[1][1])%mod
    s[1][0]=(a[1][0]*r[0][0]+a[1][1]*r[1][0])%mod
    s[1][1]=(a[1][0]*r[0][1]+a[1][1]*r[1][1])%mod
    return s
b=[[1,1],[1,0]]
k=[b]
for i in range(20):
    k.append(f(k[-1],k[-1]))
n,m=map(int,input().split())
t=0
ans=1
if m==0:
    s=bin(n-t)[2:]
    s="0"*(21-len(s))+s
    s=s[::-1]
    p=[[1,0],[0,1]]
    for j in range(21):
        if s[j]=="1":
            p=f(p,k[j])
    ans=(ans*p[0][0])%mod
    print(ans)
else:
    for i in range(m):
        a=int(input())
        if t==a:
            print(0)
            break
        else:
            s=bin(a-1-t)[2:]
            s="0"*(21-len(s))+s
            s=s[::-1]
            p=[[1,0],[0,1]]
            for j in range(21):
                if s[j]=="1":
                    p=f(p,k[j])
            ans=(ans*p[0][0])%mod
            t=a+1
            if i==m-1:
                s=bin(n-t)[2:]
                s="0"*(21-len(s))+s
                s=s[::-1]
                p=[[1,0],[0,1]]
                for j in range(21):
                    if s[j]=="1":
                        p=f(p,k[j])
                ans=(ans*p[0][0])%mod
    else:
        print(ans)

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

Solution (Python):

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





def getPatternNum(num):
    pattern = [0] * num
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern


def solve():
    

    if M > 0:
        stepsList = [0] * (M + 1)
        maxSteps = 0
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N + 1]

    
    pattern = getPatternNum(max(stepsList) + 1)

    
    for k in range(len(stepsList)):
        if k == 0:
            
            total = pattern[stepsList[k] - 1]

        else:
            total = (total * (pattern[stepsList[k] - 1])) % MOD

    return total


print(solve())

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

s_flag = [True] * (N+1)

for m in xrange(M):
    a = int(raw_input())
    s_flag[a] = False

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

print dp[N]

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

hole = [False]*(N+1)
a = [int(input()) for _ in range(M)]
for i in a:
  hole[i] = True
  
dp = [0]*(N+1)
dp[0] = 1


for i in range(1,N+1):
  if i == 1:
    if hole[i] == True:
      dp[i] = 0
    else:
      dp[i] = dp[0]
  else:
    if hole[i] == True:
      dp[i] = 0
    else:
      dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%num)

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

cnt = [1, 2]

for i in range(1, n - 1):
    cnt.append(cnt[i] + cnt[i - 1])

if m == 0:
    print(cnt[n - 1] % 1000000007)
    exit()

l = [int(input()) for _ in range(m)]

l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

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

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

Solution (Python):
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = {}
    for b in map(lambda x: int(x), inputs[1:]):
        broke_steps[b] = True

    SSSS = 1000000007

    patterns = [1]
    for step in range(1, N + 1):
        if step in broke_steps:
            ap = 0
        elif step == 1:
            ap = 1
        else:
            ap = (patterns[step - 1] + patterns[step - 2]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

Solution (Python):
import sys
n,m = map(int,input().split())
a = list(map(int,sys.stdin))
a.append(0)
prev=0
cur=1
m=0
for i in range(1,n+1):
  if a[m]==i:
    prev,cur = cur,0
    m += 1
  else:
    prev,cur = cur,(cur+prev)%1000000007
print(cur)

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

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

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

if M == 0:
    ans = fib(N) % (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

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

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

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

if M == 0:
    ans = fib(N) % (10**9+7)


elif M == 1:
    ans = fib(a[0]-1) * fib(N-a[0]-1)
    ans %= (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

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

MOD = 1000000007
n, m = map(int, input().split())
hole = [0]*(n+1)

for i in range(m): hole[int(input())] = 1

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

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

print(dp[n])

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

MOD = 1000000007
n, m = map(int, input().split())
hole = [0]*(n+1)

for i in range(m): hole[int(input())] = 1

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

for i in range(1, n+1):
    if hole[i]: dp[i] = 0
    else:
        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 i in range(M)]
MOD = 10**9+7
A = set(A)
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        continue
    if i == 1:
        dp[1] = dp[0]
    else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[N])

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

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

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

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

Solution (Python):
mods = 1000000007
n, m = [int(x) for x in input().split()]
bads = [True] * (n + 1)
for i in range(m):
    bads[int(input())] = False
dp = [0] * (n + 1)
dp[0] = 1
for curr in range(n):
    for next in range(curr + 1, min(n, curr + 2) + 1):
        if bads[next]:
            dp[next] += dp[curr]
            dp[next] %= mods
print(dp[n])

Solution (Python):
def reads():
    return list(map(int, input().split()))

MOD = 10**9 + 7

N, M = reads()
proh = set()
for _ in range(M):
    a, = reads()
    proh.add(a)

res = [0] * (N + 2)
res[0] = 1
for i in range(1, N+1):
    if i not in proh:
        res[i] = (res[i-1] + res[i-2]) % MOD
print(res[N])

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


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

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

Solution (Python):
N,M = (int(i) for i in input().split())
a = set([int(input()) for i in range(M)])
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

print(hoge[N-1] % (10**9 + 7))

Solution (Python):
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
rd=[True for i in range(n+1)]
mod=1000000007
for i in a:
    rd[i]=False
dp=[1]+[0 for i in range(n)]
for i in range(n):
    for j in range(i+1,min(i+3,n+1)):
        if rd[j]:
            dp[j]+=dp[i]
            dp[j]%=mod
print(dp[n])

Solution (Python):
N,M = (int(i) for i in input().split())
a = set([int(input()) for i in range(M)])
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a and N >= 2:
    hoge[1] = hoge[0] + 1

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

print(hoge[N-1] % (10**9 + 7))

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    elif steps <= 1:
        patern_nmu = 1
    elif steps <= 2:
        patern_nmu = 2
    else:
        p, q = 2, 1
        for j in range(1, steps-1):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

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

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

print(dp[N] % mod)

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

res = 1
for i in range(1, len(a)):
    if a[i] == 1:
        continue
    tmp = a[i] - a[i-1] - 2
    if tmp < 0:
        tmp2 = 0
    elif tmp <= 1:
        tmp2 = 1
    elif tmp <= 2:
        tmp2 = 2
    else:
        p, q = 2, 1
        for j in range(1, tmp-1):
            p, q = p+q, p
        tmp2 = p
    res *= tmp2
    res %= 1000000007

print(res)

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