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 math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n,m = map(int, input().split())
    dp = [0]*(n+1)
    dp[0] = 1
    a = [int(input()) for _ in range(m)]
    b = [1]*(n+1)

    for i in range(m):
        b[a[i]] = 0
    for i in range(n):
        if i - 1 >= 0:
            dp[i+1] = dp[i]*b[i]+dp[i-1]*b[i-1]
        else:
            dp[i+1] = dp[i]*b[i]
        dp[i+1] %= 10**9+7
    print(dp[n])

if __name__=="__main__":
    main()

Solution (Python):
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
a_complement = list((set(list(range(N+1))) ^ set(a)))
cnt = {s: 0 for s in range(-2,N+1)}
cnt[0] = 1

for i in a_complement:
  cnt[i] += cnt[i-1] + cnt[i-2]

print(cnt[N] % 1000000007)

Solution (Python):
N, M = list(map(lambda n: int(n), input().split(" ")))

fibonacci = [1, 1, 2]
for i in range(1, N + 1):
  fibonacci.append((fibonacci[i] + fibonacci[i + 1]) % 1000000007)

fibonacci.append(1)
fibonacci.append(0)

A = [-1]
for i in range(M):
  A.append(int(input()))
A.append(N + 1)

ans = 1







for i in range(len(A) - 1):
  ans *= fibonacci[A[i+1]-A[i]-2] % 1000000007
  ans = ans % 1000000007
print(ans)

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

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

def main():
    mod=10**9+7
    N,M=MI()
    dp=[0]*(N+1)
    dp[0]=1
    a=[0]*M
    for i in range(M):
        a[i]=I()
        
    a.append(10**6)
    cur=0
    
    for i in range(1,N+1):
        if i==a[cur]:
            cur+=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
            
    print(dp[-1])
    

main()

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

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

print(dp[n])

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
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

Solution (Python):
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    A = [0] * M
    for i in range(M):
        A[i] = int(input())

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

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

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

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


if __name__ == "__main__":
    main()

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

broken_list = []
if M > 0:
    for i in range(M):
        broken_list.append(int(input()))
        
broken_set =set(broken_list)
nums = [0] * (N + 1)
nums[0] = 1

if 1 not in broken_set:
    nums[1] = 1

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

print(nums[N] % 1000000007)

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

broken_list = []
if M > 0:
    for i in range(M):
        broken_list.append(int(input()))
        
broken_set =set(broken_list)
nums = [0] * (N + 1)
nums[0] = 1

if 1 not in broken_set:
    nums[1] = 1

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

print(nums[N] % 1000000007)

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

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

stime = time.time()
F=[0]*(n+1)
F[0]=1
F[1]=2
for i in range(2,n):
    F[i]=(F[i-1]+F[i-2])%MOD

etime =time.time()


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

io=-1
for i in range(n-1):
      if 0!=a[i] :
            io=i+1
            if 0!=a[i+1]:
                  print("0")
                  exit()
      else:
            if a[i+1] and i-io>1 :
                  ans*=F[i-io-1]%MOD
                  s=0
i=n-1
if i-io>0 :
      ans*=F[i-io-1]%MOD
print(ans%MOD)

Solution (Python):
from collections import defaultdict

stairs = []
steps = []
MOD = 1000000007

n, m = map(int, input().split())
stairs = {int(input()):True for _ in range(m)}

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

for i in range(n):
    if i in stairs.keys():
        step[i] = 0
    else:
        step[i+1] = (step[i] + step[i+1]) % MOD
        step[i+2] = (step[i] + step[i+2]) % MOD

print(step[n])

Solution (Python):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
one_or_two = [0] + [1] + [2] + [-1] * n
for i in range(3, n + 3):
    one_or_two[i] = (one_or_two[i-1] + one_or_two[i-2]) % mod
if m == 0:
    print(one_or_two[n])
    exit()
ans = 1
if a[0] > 1:
    ans *= one_or_two[a[0]-1]
for i in range(1, m):
    if a[i] - a[i-1] == 2:
        continue
    if a[i] - a[i-1] == 1:
        ans = 0
        break
    ans *= one_or_two[a[i] - a[i-1] - 2]
    ans %= mod
if n - a[-1] > 1:
    ans *= one_or_two[n - a[-1] - 1]
print(ans % mod)

Solution (Python):
import math
def fib(q):
   fibonacci = [0,1]
   for i in range(2,q):
       fibonacci.append(fibonacci[i-2]+fibonacci[i-1])
   return fibonacci[q-1]
n,m = list(map(int, input("").split()))
a=[]
a.append(-1)
for i in range(m):   
    a.append(int(input()))
a.append(n+1)
out=1
c=10**9+7
for i in range(m+1):
    out*=int(fib(a[i+1]-a[i]))
    out%=c
print(out)

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

Solution (Python):
n,m=map(int,input().split())
a=[0]*(m+1)
mod=1000000007
for i in range(m):
    a[i]=int(input())
s=[1,1]
j=0
for i in range(2,n+1):
    if i-1==a[j]:
        s[i-1]=0
        j+=1
    s.append(s[i-1]+s[i-2])

print(s[n]%mod)

Solution (Python):


MOD = 10**9 + 7
n, m = map(int, input().split())
a_l = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
k = 0
if m > 0 and a_l[0] == 1:
    k = min(k+1, m-1)
else:
    dp[1] = 1

for i in range(2, n+1):
    if m > 0 and i == a_l[k]:
        k = min(k+1, m-1)
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
print(dp[n])

Solution (Python):
N,M=map(int,input().split())
ans=[0 for i in range(N+1)]
true=[True for i in range(N+1)]
for i in range(M):
  a=int(input())
  true[a]=False
mod=10**9+7
ans[0]=1
ans[1]=1
for i in range(2,N+1):
  for j in range(i-2,i):
    if true[j]:
      ans[i]+=ans[j]%mod
print(ans[N]%mod)

Solution (Python):
import math
def fib(q):
   fibonacci = [0,1]
   for i in range(2,q):
       fibonacci.append(fibonacci[i-2]+fibonacci[i-1])
   return fibonacci[q-1]
n,m = list(map(int, input("").split()))
a=[]
a.append(-1)
for i in range(m):   
    a.append(int(input()))
a.append(n+1)
out=1
c=10**9+7
for i in range(m+1):
    out*=int(fib(a[i+1]-a[i]))
out%=c
print(out)

Solution (Python):
if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])
   broken = [False] * (n+1)
   for i in range(n+1):
      if i in a:
         broken[i] = True

   MOD = 1000000007


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

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

   print(dp[n])

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

MOD = 1000000007

state = [-1 for i in range(100010)]

def step_state(n, broken):
    if state[n] != -1:
        return state[n]

    if n == 0:
        state[0]=1
        return 1
    elif n == 1:
        if broken[1]:
            state[1]=0
            return 0
        else:
            state[1]=1
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            state[n]=0
            return 0
        elif broken[n - 1]:
            state[n]=step_state(n-2, broken) % MOD
            return state[n]
        elif broken[n-2]:
            state[n] = step_state(n-1, broken) % MOD
            return state[n]
        else:
            state[n] = (step_state(n-1, broken)+step_state(n-2, broken)) % MOD
            return state[n]


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

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

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


def solve(k):
    if(b[k] == 1):
        return 0
    if(dp[k] != -1):
        return dp[k]
    if(k < 0):
        return 0
    tmp = solve(k-1)+solve(k-2)
    dp[k] = tmp % 1000000007
    return tmp


print(solve(n) % (1000000007))

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

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

MOD = pow(10, 9) + 7

dp = [0] * (n+1)

dp[0] = 1

broken = [False] * (n+1)
for i in range(m):
    broken[int(input())] = True

c = 1

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

print(dp[-1] % MOD)

Solution (Python):
import sys
 
sys.setrecursionlimit(1000000)
n, m, *a = map(int, open(0).read().split())
dp = [1] + [-1] * n
dp[1] = 1
for i in a:
    dp[i] = 0
 
def count(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = (count(n - 1) + count(n - 2)) % (10**9 + 7)
    return dp[n]
 
 
print(count(n))

Solution (Python):
import sys
 
sys.setrecursionlimit(1000000)
n, m, *a = map(int, open(0).read().split())
dp = [1] + [-1] * n
dp[1] = 1
for i in a:
    dp[i] = 0
 
def count(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = (count(n - 1) + count(n - 2)) % (10**9 + 7)
    return dp[n]
 
 
print(count(n))

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

Solution (Python):
import sys

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

a,b=0,1
for i in range(1,N+1):
    if i in bad:
        a,b=b,0
        if a==0:
            break
    else:
        a,b=b,(a+b)%MOD

print(b)

Solution (Python):
import sys

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

a,b=0,1
for i in range(1,N+1):
    if i in bad:
        a,b=b,0
        if a==0:
            break
    else:
        a,b=b,(a+b)%MOD

print(b)

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

a,b=0,1
for i in range(1,N+1):
    if i in S:
        a,b=b,0
    else:
        a,b=b,a+b

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

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

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

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

if dp[-1]==-1:
    print(0)
else:
    print(dp[-1]%(10**9+7))

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

Solution (Python):
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if len(ais)>0 and ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

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

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

for i in lis:
    ans[i] = 0


for i in range(2, 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 = set(int(input()) for _ in range(m))
mod = 10 ** 9 + 7

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

print(dp[-1] % mod)

Solution (Python):
import bisect, copy, heapq, math
from math import inf
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(m):
    dic[a[i]]=1
dp=[0]*(n+2)

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

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

dp=[1]+['']*n

for i in a:
  dp[i]=0

if dp[1]=='':
  dp[1]=1
  

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

print(dp[-1])

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

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

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

memo = [-1] * (n + 1)
memo[0] = 1
memo[1] = 1
for i in range(m):
  memo[int(input())] = 0

def fib(x):
  if memo[x] == -1:
    memo[x] = fib(x-1) + fib(x-2)
  return memo[x]

def fib2(x):
  if x <= 1:
    return memo[x]
  else:
    for i in range(x - 1):
      if memo[i + 2] == 0:
        continue
      memo[i + 2] = memo[i] + memo[i + 1]
    return memo[x]



print(fib2(n) % 1000000007)

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

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

N, M = LI()
A = [int(input()) for _ in range(M)]

MOD = 10 ** 9 + 7


def main():
    s = set(A)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(1, N + 1):
        if i in s:
            continue
        v = dp[i - 1]
        if i >= 2:
            v += dp[i - 2]
        dp[i] = v % MOD
    
    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
n,m=map(int,input().split())
a=[]
d=0
for i in range(m):
    a.append(int(input()))
a.append(0)
a.append(0)
a.append(0)
ans=[]
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        sys.exit()
ans=[0 for i in range(n+5)]
ans[1]=1
ans[2]=2

if a[0]==1:
    ans[1]=0
    ans[2]=1
    d+=1
if a[0]==2 or a[1]==2:
    ans[2]=0
    d+=1

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)
d = {0:1, 1:1, 2:2}
def countcombi(n):
    if n in d:
        return d[n]
    else:
        d[n] = countcombi(n-1)+countcombi(n-2)
        return d[n]
N, M = list(map(int,input().rstrip().split()))
a_now = 0
a_before = 0
ans = 1
for _ in range(M):
    a_now = int(input().rstrip())
    if a_now-a_before == 0 and a_before != 0:
        print(0)
        break
    ans = (ans * countcombi(a_now-a_before-1)) % 1_000_000_007
    a_before = a_now + 1
else:
    a_now = N
    ans = (ans * countcombi(a_now-a_before)) % 1_000_000_007
    print(ans)

Solution (Python):
N,M=map(int,input().split())
br=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
if not 1 in br:
    dp[1]=1

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

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

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

dp[0]=1

dp[1]=1

for i in a:
  dp[i]=0
  

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

Solution (Python):
n,m,*a=map(int,open(0).read().split())
a=set(a)
mod=10**9+7

dp=[0]*(n+1)

dp[0]=1
dp[1]=0 if 1 in a else 1

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

print(dp[n])

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

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

for i in range(len(a)-1):
    if a[i+1] == a[i]+1:
        print(0)
        exit()
x = []
temp=0
for i in range(m):
    x.append(a[i]-temp-1)
    temp = a[i]+1
x.append(n-temp)

temp = 1
div = 1000000007

for i in x:
    temp = (temp*Fib(i+1))%div

print(temp)

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

modx=10**9+7

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

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

print(dp[n])

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

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

for i in li:
    dp[i] = 0

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

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

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

Solution (Python):




mod = 1000000007
N, M = map(int, input().strip().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)

def fibonacci(x):
    a = 1
    b = 1
    if x <= 2:
        return a
    else:
        for _ in range(x-2):
            tmp = a
            a = b
            b = tmp + b
        return b

res = 1
prev_a = -1
for cur_a in a:
    if  cur_a - prev_a == 1:
        res = 0
        break
    res *= fibonacci(cur_a - prev_a - 1) % mod
    res %= mod
    prev_a = cur_a
    continue

print(res)

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

p = 10**9 +7
ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1

broken = [0]*(n+1)
for i in a:
    broken[i]= -1

for i in range(1,n):
    if broken[i] == -1:
        ans[i] = 0
        ans[i+1] = ans[i-1]%p
    else:
        ans[i+1] = (ans[i-1] + ans[i])%p

print(ans[-1])

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

p = 10**9 +7
ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1

broken = [0]*(n+1)
for i in a:
    broken[i]= -1

for i in range(1,n):
    if broken[i] == -1:
        ans[i] = 0
        ans[i+1] = ans[i-1]%p
    else:
        ans[i+1] = (ans[i-1] + ans[i])%p

print(ans[-1])

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

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

print(dp[n] % 1000000007)

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

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

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD=10**9+7
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
if 1 in a:
  ans=[1,0]
else:
  ans=[1,1]

@lru_cache(maxsize=None)
def cnt(x):
  if x<2:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(n))

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

Solution (Python):
MOD=10**9+7
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,1]
elif 2 in a:
  ans=[1,0]
else:
  ans=[1,2]

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

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD=10**9+7
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
if n==1:
  print(1)
  exit()
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,0,1]
elif 2 in a:
  ans=[0,1,0]
else:
  ans=[0,1,2]

@lru_cache(maxsize=None)
def cnt(x):
  if x<3:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(n))

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

Solution (Python):
n,m=map(int, input().split())
alist=[0]*(n+10)
for i in range(m):
  alist[int(input())]=-1
ans=True
alist[0]=1
for i in range(n):
  if alist[i]!=-1:
    if alist[i+1]!=-1 and alist[i+2]!=-1:
      alist[i+1]+=alist[i]
      alist[i+2]+=alist[i]
    elif alist[i+2]!=-1:
      alist[i+2]+=alist[i]
    elif alist[i+1]!=-1:
      alist[i+1]+=alist[i]
    else:
      ans=False
if ans:
  print(alist[n]%(10**9+7))
else:
  print(0)

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

if N == 1:
    print(1)
else:
    s = [-1] * N
    s[0] = 1
    s[1] = 1

    for m in range(0, M):
        i = int(input())
        s[i] = 0

    for n in range(2, N):
        if s[n] == 0:
            continue
        s[n] = s[n - 1] + s[n - 2]

    print((s[N-1] + s[N-2]) % 1000000007)

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

a = [0] * (n+2)
dp = [0] * (n+2)
mod = 1000000007

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

dp[0]=1

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

print(dp[n]%mod)

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

a = [0] * (n+1)
dp = [0] * (n+1)
mod = 1000000007

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

dp[0]=1

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

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

	dp[i] = dp[i] % mod

print(dp[n]%mod)

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

a = []
dp = []
mod = 1000000007

for i in range(100100):
	a.append(0)
	dp.append(0)

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

dp[0]=1

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

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

	dp[i] = dp[i] % mod

print(dp[n]%mod)

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

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
not_wet = [True] * (n + 1)
for a in A:
    not_wet[a] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if not_wet[i]:
        if i == 1:
            dp[i] = dp[i - 1] % mod
        else:
            dp[i] = dp[i - 1] + dp[i - 2] % mod
print(dp[n] % mod)

Solution (Python):
patterns = [None] * (10**5 + 10)
patterns[0] = 1
patterns[1] = 1
calcurated_until = 1
MOD = 10**9+7
def get_patterns(n):
  global calcurated_until, patterns
  if patterns[n] is None:
    for i in range(calcurated_until + 1, n + 1):
      patterns[i] = (patterns[i-1] + patterns[i-2])%MOD
    calcurated_until = n
  
  return patterns[n]

def solve():
  N, M = map(int, input().split())
  A = [-1]
  for _ in range(M):
    A.append(int(input()))
  A.append(N+1)
  
  
  ans = 1
  for a1, a2 in zip(A[:-1], A[1:]):
    
    if a2 == a1+1:
      print('0')
      return
    
    
    ans *= get_patterns(a2 - a1 - 2)
    
    ans %= MOD
    
  print(ans)
solve()

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

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

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

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

K=10**9+7

X=[0]*(N+1)
X[0]=1
X[1]=1*(1 not in A)

for i in range(2,N+1):
    if i not in  A:
        X[i]=(X[i-1]+X[i-2])%K
print(X[-1])

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

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

dp[1] = 1
if N >= 2:
    dp[2] = 2

if 1 in skip:
    dp[1] = 0
    if N >= 2:
        dp[2] = 1
if 2 in skip:
    if N >= 2:
        dp[2] = 0

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

print(dp[N])

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

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

dp[0] = 1
if 1 not in skip:
    dp[1] = 1

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

print(dp[N])

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

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

dp[0] = 1
if 1 not in skip:
    dp[1] = 1

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

print(dp[N])

Solution (Python):

N,M = map(int,input().split())
dp = [[] for i in range(N)]
for i in range(M):
    dp[int(input())-1] = 0

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

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

for i in range(N):
  if i + 1 not in ng:
    dp[i + 1] += dp[i]
    dp[i + 1] %= 1000000007
  if i + 2 not in ng:
    dp[i + 2] += dp[i]
    dp[i + 2] %= 1000000007

print(dp[N])

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

for i in range(N):
  for j in range(1, 3):
    if (i + j) not in ng:
      dp[i + j] += dp[i]
      dp[i + j] %= 1000000007

print(dp[N])

Solution (Python):
N,M = map(int, input().split())
ng = set()
for i in range(M):
  ng.add(int(input()))
  
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in ng:
  dp[1] = 1

for i in range(2, len(dp)):
  if i in ng:
    continue
  dp[i] += (dp[i - 2] + dp[i - 1])
  dp[i] %= 1000000007
  
print(dp[N])

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

def fib(n):
    if n == 0:
        return 0
    one = 1
    two = 1
    for _ in range(n-2):
        two,one = one + two,two
    return two

ans,now = 1,0
for i in range(M):
    a = int(input())
    ans *= fib(a - now)
    now = a+1
    if ans > 10**9+7:
        ans %= 10**9 + 7
ans *= fib(N - now + 1)
ans %= 10**9 + 7

print(ans)

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

dp = [0]*(n+1)
dp[0] = 1
if 1 not 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]
  dp[i] = dp[i] % 1000000007
print(dp[n])

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

for i in range(m):
    a = int(input())
    kep[a] = 0
keep[0] = 1
keep[1] = 0 if kep[1] == 0 else 1
for j in range(0, n - 1):
    keep[j + 2] = [0, keep[j] + keep[j + 1]][kep[j + 2]] % 1000000007
print(keep[n])