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 slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = dict([[int(input().rstrip('\n')), 0] for i in range(m)])
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in a else 0
    dp[1] = 1 if 1 not in a else 0
    for i in range(2, n + 1):
        if i not in a:
            dp[i] = (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)
        else:
            dp[i] = 0
    print(dp[-1])


if __name__ == '__main__':
    slove()

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

kaidan = [-1] * (n+1)

for i in range(m):
  a = int(input())
  kaidan[a] = 0
  
kaidan[0] = 1
if kaidan[1] == -1:
  kaidan[1] = kaidan[0]
  
for i in range(2,len(kaidan)):
  if kaidan[i] == -1:
    kaidan[i] = (kaidan[i-2] + kaidan[i-1]) % 1000000007

print(kaidan[-1])

Solution (Python):

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

print(dp[-1])

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

dp = []
for i in range(N + 1):
    dp.append(None)

for _ in range(M):
    a = int(input())
    A.add(a)

dp.append(0)
dp[N] = 1

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


print(dp[0] % 1000000007)

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

dp = []
for i in range(N + 1):
    dp.append(None)
    A.append(None)

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

dp.append(0)
dp[N] = 1

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


print(dp[0] % 1000000007)

Solution (Python):
MOD = 10**9 + 7
N,M = map(int,input().split(' '))
broken_list = set([int(input()) for i in range(M)])

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append((ans[-2]+ans[-1]) % MOD)

print(ans[-1] % MOD)

Solution (Python):
n,m=map(int,input().split())
mod=10**9+7

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])%mod
  if i in a:dp[i]=0
print(dp[n])

Solution (Python):
n, m = map(int, input().split(" "))
oks, dp = [True] * (n + 1), [0] * (n+1)

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

dp[0] = 1
for now in range(n):
    for next in range(now+1, min(n+1, now + 3)):
        if oks[next]:
            dp[next] += dp[now]
            dp[next] %= 10 ** 9 + 7
print(dp[n])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

from collections import defaultdict as dd
n,m=[int(i) for i in input().split()]
brkn = dd(int)
mod = 10**9+7
for i in range(m):
    num = int(input())
    brkn[num]+=1
dp = [-1]*(n+1)

def func(curr):
    if(curr==0):
        dp[0]=1
        return dp[0]
    if(curr>0 and (curr in brkn)):
        dp[curr]=0
        return dp[curr]%mod
    if(curr==1):
        dp[1]=1
        return dp[1]
    if(dp[curr]!=-1):
        return dp[curr]%mod
    else:
        dp[curr] =  (func(curr-1) + func(curr-2))%mod
        return dp[curr]%mod

print(func(n))

Solution (Python):
from collections import defaultdict as dd
n,m=[int(i) for i in input().split()]
brkn = dd(int)
mod = 10**9+7
for i in range(m):
    num = int(input())
    brkn[num]+=1
dp = [0]*(n+1)
dp[0]=1
if(1 in brkn):
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if(i in brkn):
        dp[i]=0
    else:
        dp[i] = (dp[i-1]+ dp[i-2])%mod
print(dp[n])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)

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

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


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)

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

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


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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

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


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

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

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


def f(x):
    
    
    
    
    
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    
    
    
    
    
    
    
    
    
    
    

    
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Solution (Python):

import sys
input = sys.stdin.readline

def resolve():
    n, m = map(int, input().split())
    aa = [False] * (n+1)

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

    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 0 if aa[1] else 1

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

    print(dp[n])



resolve()

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

a = [0 for _ in range(n + 2)]
dp = [0 for _ in range(n + 2)]

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

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

    dp[i + 1] %= 1000000007
    if a[i + 2] != 1:
        dp[i + 2] += dp[i]

    dp[i + 2] %= 1000000007

print(dp[n])

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

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1)%1000000007)
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)%1000000007
        print(m%1000000007)

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

p = [1] * (n+1)
ans = 1

for a in la:
	p[a] = 0

for i in range(n+1):
	if i == 0 and p[i] == 0:
		ans = 0
		break
	elif i > 1:
		if p[i] == 0 and p[i-1] == 0:
			ans = 0
			break
		elif p[i] > 0:
			ans = p[i-1] + p[i-2]
			p[i] = ans

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

Solution (Python):
nm=list(map(int,input().split()))
stair=[1]*(nm[0]+1)
for i in range(nm[1]):
    stair[int(input())]=0

i=0
b1=1
b2=0
while i <nm[0]:
    if stair[i+1]==1:
        i+=1
        b1+=b2
        b2=b1-b2
    elif stair[i+1]==0 and stair[i+2]==1:
        i+=2
        b2=0
    else:
        i=nm[0]
        b1=0
print(b1%(10**9+7))

Solution (Python):
N, M, *A = map(int, open(0).read().split())
MOD = 10**9 + 7
F = [1]*(N+1)
for j in A:
    F[j-1] = 0
 
a = 1; b = 0
for i in range(N):
    if not F[i]:    
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

Solution (Python):

N,M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
F = [1]*(N+1)
for j in A:
    F[j-1] = 0
 
a = 1; b = 0
for i in range(N):
    if not F[i]:    
        a, b = 0, a
    else:
        a, b = ((a+b) % MOD), a
print(a)

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

Solution (Python):
z=list(map(int,input().split()))
n,m,b,c=z[0],z[1],[1],0
a=[int(input()) for i in range(m)]
if len(a)>=1:
    if a[0]==1:
        b.append(0)
        c=1
    else:
        b.append(1)
        c=0
else:
    b.append(1)
for i in range(n-1):
    if c<len(a):
        if i+2==a[c]:
            b.append(0)
            c+=1
        else:
            b.append(b[i]+b[i+1])
    else:
        b.append(b[i]+b[i+1])
print(b[-1]%1000000007)

Solution (Python):




n,m=input().split()
n,m=int(n),int(m)
ax=[1]*(n+1)
for i in range(m):
    ax[int(input())]=0
bx=[1,1]
for i in range(2,n+1):
    if ax[i-1]==1:
        f1=bx[i-1]
    else:
        f1=0
    if ax[i-2]==1:
        f2=bx[i-2]
    else:
        f2=0
    bx.append((f1+f2)%(10**9+7))

print(bx[n])

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

n, m = map(int, input().split())
state = [1] * (n+1)

for _ in range(m):
  state[int(input())] = 0
  
f = [1, 1]

for i in range(2, n+1):
  f_nm1 = f[i-1] if state[i-1]==1 else 0
  f_nm2 = f[i-2] if state[i-2]==1 else 0
  f.append(f_nm1 + f_nm2)

print(f[-1]%1000000007)

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

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

ste = [0] *(n+1)
ste[0] = 1
if 1 not in aa:
    ste[1] = 1
else:
    ste[1] = 0
for i in range(2,n+1):
    if i in aa:
        continue
    ste[i] = (ste[i-1]+ste[i-2])%mod

print(ste[n])

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

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

Solution (Python):

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

def fib(x):
    a = 1
    b = 1
    if x == 0:
        return 0
    elif x == 1:
        return a
    elif x == 2:
        return b
    else:
        for i in range(x-2):
            c = a + b
            a = b
            b = c
        return b 

before_a=1
output=1
if M>=1:
    output = fib(A[0])
    for i in range(M-1):
        output *= fib(A[i+1]-A[i]-1)
    output *= fib(N-A[M-1])
else:
    output *= fib(N+1)
print(output%1000000007)

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


if 1 in a:
    n[1] = 0

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

print(n[N])

Solution (Python):
def fib(x):
  a = 1
  b = 1
  if x == 0:
    return 0
  elif x == 1:
    return a
  elif x == 2:
    return b
  else:
    for i in range(x-2):
      c = a + b
      a = b
      b = c
    return b 
n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m >= 1:
  c = fib(A[0])
  for i in range(m-1):
    c *= fib(A[i+1] - A[i] - 1)
  c*= fib(n - A[m-1])
  print(c%1000000007)
else:
  print(fib(n+1)%1000000007)

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

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

dp[0] = 1
mod = 1000000007

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

print(dp[-1] % mod)

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

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

dp[0] = 1
mod = 1000000007

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

print(dp[-1])

Solution (Python):
import sys
n,m=map(int,input().split())
if m > 0:
  a = set(map(int, sys.stdin))
else:
  a = set()

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

print(fibo[-1])

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

def main():
    n, m = 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
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()

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

flag = 0
for i in range(m-1):
    if a[i+1] - a[i] == 0:
        flag = 1
        print(0)
        break

if flag == 0:
    b = [1]
    if len(a) != 0 and a[0] == 1:
        b.append(0)
        a.pop(0)
    else:
        b.append(1)
    for i in range(2, n+1):
        if len(a) != 0 and a[0] == i:
            b.append(0)
            a.pop(0)
        else:
            b.append((b[i-1]+b[i-2])%1000000007)

    print(b[-1])

Solution (Python):
NUM = int(10**9 + 7)

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

if m > 0:
    split = [[0, nums[0] - 1]]
    for i in range(1, m):
        split.append([nums[i - 1] + 1, nums[i] - 1])
    split.append([nums[-1] + 1, n])
else:
    split = [[0, n]]

n_steps = [h - l for l, h in split]

counts = [1, 1]
for _ in range(max(n_steps) - 1):
    c = counts[-1] + counts[-2]
    counts.append(c)

if min(n_steps) < 0:
    print(0)
else:
    res = 1
    for s in n_steps:
        res *= counts[s]
        res %= NUM
    print(res)

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

dp = [1, 2]
A = [int(input()) for _ in range(M)]
if M != 0:
    if M >= 2 and A[0] == 1 and A[1] == 2:
        dp = [0, 0]
    elif A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]
else:
    A = [0]

MOD = 1000000007

if N == 1:
    print (1)
elif N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt < M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

    print (dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1


if dp[0] == -1 and dp[1] == -1:
    pass
else:
    if dp[0] == -1:
        dp[1] = 1
    elif N >= 2 and dp[1] == -1:
        dp[0] = 1
    elif N >= 2:
        dp[0] = 1
        dp[1] = 2
    else:
        dp[0] = 1


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)

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

traps = {}
for i in range(m):
    t = int(input())
    traps[t] = 1

mem = {}

def f(k):
    if k in mem:
        return mem[k]

    if k >= n:
        return 0
    if k == n - 1:
        return 1
    if k == n - 2:
        if n - 1 in traps:
            return 1
        else:
            return 2

    res = 0
    if k + 1 not in traps:
        res += f(k + 1)
    if k + 2 not in traps:
        res += f(k + 2)
    mem[k] = res

    return res % MOD

print(f(0))

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
a = [I() for _ in range(m)]
dp = [0]*(n+1)
dp[0],dp[1] = 1,1
for i in a:
    dp[i] = -1
for i in range(2,n+1):
    if dp[i] < 0:
        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]) % mod
if dp[-1] == -1:
    print(0)
else:
    print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
dq = [1]*(n+1)
for _ in range(m):
  dq[int(input())]=0
mod = 10**9+7
x, y = 0, 1
for i in range(1, n+1):
  x,y = y, dq[i] * (x+y) % mod
print(y)

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

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

print(dp[n] % mod)

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

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

def stepcmb(st):
    memo = [0]*(st+1)
    memo[0] = 1
    def _fib(st):
        if st <= 1:
            return 1
        if memo[st] != 0:
            return memo[st]
        memo[st] = _fib(st-1) + _fib(st-2)
        return memo[st]
    return _fib(st)

if m >= 2:
    for i in range(1, m):
        if steps[i] - steps[i-1] == 1:
            print(0)
            exit()

res = 1
nowstep = 0
for i in range(m):
    res *= stepcmb(steps[i]-nowstep-1) % (10**9+7)
    nowstep = steps[i] + 1
res = (res * stepcmb(n-nowstep)) % (10**9+7)

print(res)

Solution (Python):
N,M = (int(b) for b in input().split())
a = [0]*(N+1)
a[0] = 1
for i in range(M):
    x = int(input())
    a[x] = -1
for i in range(1,N+1):
    if a[i] == -1:
        continue
    a1 = max(a[i - 2], 0)
    a2 = max(a[i - 1], 0)
    a[i] = a1 + a2
print(a[N]%(1000000000+7))

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

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  


if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    print(1)
  else:
    print(2)
  exit()
  
if s[0]=="":
  s[0]=0
else:
  s[0]=1
  
if s[1]=="":
  s[1]=0
else:
  s[1]=1+s[0]

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

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

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

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

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

Solution (Python):
n,m = map(int,input().split())
a = [-1]
flag = True
 
if m>0:
  for i in range(m):
    a.append(int(input()))
    if a[i+1]==a[i]+1:
      flag = False
      break
  if not flag:
    print(0)
  else:
    a.append(n+1)
    step = [a[i+1]-a[i]-1 for i in range(m+1)]
    onestep = [1,1]
    if max(step)>=3:
      for i in range(3,max(step)+1):
        onestep.append(onestep[-2]+onestep[-1])
  
    ans = 1
    for i in range(m+1):
      ans *= onestep[step[i]-1]
    print(ans%1000000007)
else:
  onestep=[1,1]
  if n==1:
    print(1)
  else:
    for i in range(2,n+1):
      onestep.append(onestep[-2]+onestep[-1])
    print(onestep[-1]%1000000007)

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    p = [0] * (N+1)
    p[0] = 1

    for m in range(M-1):
        if a[m] + 1 == a[m + 1]:
            print(0)
            return

    a += [999999, 1999999]
    watch = 0
    if a[watch] == 1:
        watch += 1
        p[1] = 0
    else:
        p[1] = 1
    for n in range(2, N+1):
        if a[watch] == n:
            p[n] = 0
        elif a[watch] == n - 1:
            p[n] = p[n-2]
        elif a[watch] == n - 2:
            if a[watch+1] != n:
                p[n] = p[n-1]
            else:
                p[n] = 0
            watch += 1
        else:
            p[n] = p[n-1] + p[n-2]
    print(p[N] % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [ int(next(tokens)) for _ in range(M) ]  
    solve(N, M, a)

if __name__ == '__main__':
    main()

Solution (Python):
def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Solution (Python):
import math
import copy
import fractions
import numpy as np



def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList



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

broken = getSomeInputInt(m)

mod = 1000000007

dp = np.zeros(n+1)
dp[0] = 1

brokenArray = np.ones(n+1)
for i in range(len(broken)):
    brokenArray[broken[i]] = 0


for i in range(n+1):
    if brokenArray[i] == 1 and i+1 < n+1:
        dp[i+1] += dp[i]
        dp[i+1] %= mod

    if brokenArray[i] == 1 and i+2 < n+1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod

print(int(dp[n]))

Solution (Python):
N, M = map(int, input().split())
MOD = 10**9+7
a = set()
for i in range(M):
    a.add(int(input()))
step = [0]*(N+1)
step[0] = 1
for i in range(N+1):
    if i == 0:
        pass
    elif i in a:
        step[i] = 0
    elif i == 1:
        step[i] = step[0]
    else:
        step[i] = step[i-1]+step[i-2]
    step[i] %= MOD
print(step[N])

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

Solution (Python):
n, m = map(int, input().split())
a = list(int(input()) for i in range(m))

a.insert(0, -1)
a.append(n + 1)
total = 1

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

for i in range(1, m + 2):
    interim = a[i] - a[i - 1] - 1
    if interim <= 0:
        total = total * 0
    else:
        total = total * Fib(interim)

ans = total % 1000000007
print(ans)

Solution (Python):
import sys

mod = 1000000007

"""


    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 1)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

    L = [0] * (N + 1)
    L[0] = 1
    if not broken[1]:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)

Solution (Python):
def dp(n):
    d=[0]*(n+1)
    if n==1:
        return 1
    else:
         d[0]=1
         if a[1]==0:
            d[1]=1
         else:
            d[1]=0
         for i in range(2,n+1):
            if a[i]==0:
                d[i]=(d[i-1]+d[i-2])%1000000007
            else:
                d[i]=0
         return d[n]

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

Solution (Python):
def dp(n):
    d=[0]*(n+1)
    if n==1:
        return 1
    else:
         d[0]=1
         if a[1]==0:
            d[1]=1
         else:
            d[1]=0
         for i in range(2,n+1):
            if a[i]==0:
                d[i]=d[i-1]+d[i-2]
            else:
                d[i]=0
         return d[n]

n,m=map(int, input().split())
a=[0]*(n+1)
for i in range(0,m):
    k=int(input())
    a[k]=1
print(dp(n)%1000000007)

Solution (Python):
def main():
    n, m = map(int, input().split())
    a = [0] * n
    step = [0] * (n + 1)
    for i in range(m):
        step[int(input())] = -1
    step[0] = 1
    step[1] = 1 if step[1] != -1 else -1
    for i in range(2, n + 1):
        if step[i - 2] == -1 and step[i - 1] == -1:
            print(0)
            return
        if step[i] == -1:
            continue
        step[i] = (step[i - 2] if step[i - 2] != -1 else 0) + \
            (step[i - 1] if step[i - 1] != -1 else 0)
        step[i] %= 1000000007
    print(step[n])


if __name__ == '__main__':
    main()

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

  if a[0]==1:
    way=[1, 0]
    a.remove(1)
  else:
    way=[1, 1]
else:
  a=[]
  way=[1, 1]
  
for i in range(2, N+1):
  if len(a)>0:
    if i==a[0]:
      a.remove(i)
      way=[way[1], 0]
    else:
      way=[way[1], sum(way)]
  else:
    way=[way[1], sum(way)]
    
print(way[1]%1000000007)

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

mod = 10**9+7
n, m = map(int, input().split())
broken = set(int(input()) for i in range(m))

pattern = [0]*(n+1)
pattern[0] = 1
if 1 in broken:
    pattern[1] = 0
else:
    pattern[1] = 1

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

print(pattern[n])

Solution (Python):
import sys


input = sys.stdin.readline

n, m = map(int, input().split())
broken = set()
for i in range(m):
    a = int(input())
    broken.add(a)

pattern = [0]*(n+1)
pattern[0] = 1
if 1 in broken:
    pattern[1] = 0
else:
    pattern[1] = 1

for i in range(2, n+1):
    if i in broken:
        pattern[i] = 0
    else:
        pattern[i] = pattern[i-1] + pattern[i-2]

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

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

dp=[-1]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
if dp[1]==-1:dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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

def main(): 
    N,M=map(int,input().split())
    a=[int(input()) for _ in range(M)]
    a.sort(reverse=True)
    ans=[0]*(N+1)
    ans[0]=1
    if not(len(a) != 0 and a[-1] == 1):
        ans[1]=1
    else:
        a.pop()
    for i in range(2,N+1):
        if len(a) != 0 and a[-1] == i:
            a.pop()
        else:
            ans[i] = ans[i-1]+ans[i-2]
            
    print(ans[N]%1000000007)
if __name__ == "__main__":
    main()

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

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

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)