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

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):
from functools import lru_cache
import sys
sys.setrecursionlimit(30000)

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

MOD = pow(10, 9) + 7

isOk = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        isOk = False
    
funcb = [-1] * 100001
def func(n):
    if n <= 0:
        return 1
    cnt = funcb[n]
    if cnt > 0:
        return cnt
    cnt = 0
    if n >= 2:
        cnt += func(n-2)
    if n >= 1:
        cnt += func(n-1)
    funcb[n] = cnt % MOD
    return funcb[n]

func(30000)
func(50000)
func(80000)
func(100000)

if not isOk:
    print(0)
else:
    ans = 1
    s = 0
    for i in range(M+1):
        if i >= M:
            e = N
        else:
            e = a[i] - 1

        ans = ans * func(e-s) % MOD

        if i >= M:
            break

        s = a[i] + 1

    print(ans)

Solution (Python):



import sys

input = sys.stdin.readline

cnt = 0

def main():
    N, M = map(int, input().split())
    m = {}
    for l in sys.stdin:
        m[int(l.strip())] = True

    
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    dp[1] = 1 if 1 not in m else 0

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

main()

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

m = 10**9+7

memo = [1]*(N+3)
for i in range(3,N+3):
    memo[i] = memo[i-1] + memo[i-2]

memo[0] = 0

A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    ans *= memo[A[i]-p-1]
    p = A[i]

print(ans%m)

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

N, M = map(int, input().split())
ai = -1
ans = 1


for _ in range(M):
    af = int(input())
    L = af - ai - 2
    if L == -1:
        ans = 0
        break
    else:
        ans *= Fib(L)
        ai = af
ans *= Fib(N - ai - 1)

ans = ans % 1000000007

print(ans)

Solution (Python):
N ,M= map(int, input().split())
memo =[1]*(N + 2)
memo[N+1] = 0 
impossible = False
back2 = 0
start_step =0
for i in range(M):
    a = int(input())
    memo[a] = 0 
  
def one_step(step):
    memo[step] = (memo[step+1] + memo[step+2])*memo[step]

for step in range(N-1 ,-1,-1):
    one_step(step)

print(memo[0]%1000000007)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = 10**9+7
nots = [int(input()) for i in range(m)]
leng = len(nots)
cnt = 0
dp = [0]*(n+1)
dp[0] = 1
if leng > 0 and nots[0] == 1:
  dp[1] = 0
  nots.pop(0)
  leng -= 1
else:
  dp[1] = 1
if n == 1:
  print(1)
  exit()

for i in range(2,n+1):
  if leng > 0 and nots[cnt] == i:
    dp[i] = 0
    if cnt < leng - 1:
      cnt += 1
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % num
print(dp[n] % num)

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

combination = [1,1,2]
for i in range(3,N+1):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []

if M > 0:
    next_a = int(input())
    lst.append(combination[next_a-a-1])
    a = next_a
    for i in range(M-1):
        next_a = int(input())
        if next_a-a == 1:
            ans = 0
            break
        elif next_a-a == 0:
            continue
        lst.append(combination[next_a-a-2])
        a = next_a

    next_a = N
    lst.append(combination[next_a-a-1])
else:
    lst.append(combination[N])
    
for tmp in lst:
    ans *= tmp
print(ans%1000000007)

Solution (Python):
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

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

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

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

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [1, 1] + [0] * (total - 1)
for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) % (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)

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

lis = [1,1,2]
def num(n):
    if len(lis) >= n+1:
        return lis[n]
    else:
        res = num(n-2) + num(n-1)
        lis.append(res)
        return res

N,M = map(int,input().split())
count = 1
pre = 0
for i in range(M+1):
    if i == M:
        cur = N+1
    else:
        cur = int(input())
    number = cur-1-pre
    if number >= 0:
        count = count * num(number) % 1000000007
    else:
        count = 0
        break
    pre = cur + 1
print(count%1000000007)

Solution (Python):


def fb(num):
    fblist = []
    x, y = 1, 0
    for _ in range(num):
        fblist.append(x)
        x, y = x + y, x
    return fblist

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

l = fb(n + 1)

now = 0
p_cnt = []
for i in range(m):
    a = int(input())
    if now == a:
        print(0)
        exit()
    p_cnt.append(l[a - 1 - now])
    now = a + 1




p_cnt.append(l[n - now])


ans = 1
for j in range(len(p_cnt)):
    
    ans *= p_cnt[j]
    
    
print(ans %  1000000007)

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

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
ans = 1
a = []
al = 0
for i in range(2,N+1):
    c[i] = c[i-1]+c[i-2]
    c[i] %= mod
for i in range(M):
    ai = int(input())
    if i == 0:
        a.append(ai)
    else:
        if ai - al == 1:
            print(0)
            exit()
        else:
            a.append(ai)
    al = ai
if M == 0:
    print(c[N])
    exit()
for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        if a[i+1] != a[i]:
            ans *= c[a[i+1]-a[i]-2]
            ans %= mod
print(ans)

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

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

x = [0] * (N+1)
x[0] = 1
ai = 0
if ai >= M or 1 != a[ai]:
    x[1] = x[0]
else:
    ai += 1
for i in range(2, (N+1)):
    if ai >= M or i != a[ai]:
        x[i] = (x[i-1] + x[i-2]) % base
    else:
        ai += 1
print(x[N])

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

p = [0]*(n+1)
for i in bk:
    p[i] = -100
if n == 1 and m == 0:
    print(1)
elif n == 1 and m == 1:
    print(0)
else:
    p[0] = 1
    if 1 in bk:
        p[1] = 0
    else:
        p[1] = 1
    for i in range(n-1):
        if p[i+2] < 0:
            p[i+2] = 0
        else:
            p[i+2] = p[i]+p[i+1]
            if p[i+2] >= 1000000007:
                p[i+2] -= 1000000007

    print(p[n])

Solution (Python):

import sys

MOD = 1000000007  

def solve(N: int, M: int, a: "List[int]"):
    if(len(a) >= 2):
        l = [a[i+1]-a[i] for i in range(M-1)]
        if(len(l) and min(l)<=1):
            print(0)
            exit()

    dp = [1] * (N+1)
    dp[1] = 1
    if(N >= 2):
        dp[2] = 2
    x = 0
    
    
    
    for i in range(2,N+1):
        if(len(a) and a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            
        elif(len(a) and a[x] == i-2):
            dp[i] = dp[i-1] % MOD
            x = min(x+1,M-1)
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
    print(dp[N])
    
    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):
import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Solution (Python):
R = lambda: map(int, input().split())
M = 10**9 + 7
n, m = R()
a = [-1] + [int(input()) for _ in range(m)]
s, t = 0, 1
for i in range(n - 1, -1, -1):
    if i == a[-1]:
        a.pop()
        s, t = t, 0
    else:
        s, t = t, (s + t) % M
print(t)

Solution (Python):
N,M=map(int,input().split())
a = -1
List = []
for i in range(M):
    k = int(input())
    List.append(k-a)
    a = k
List.append(N - a + 1)
m = max(List)
mm = min(List)
LL = [0,1]
for i in range(2,m):
    k = LL[i-1] + LL[i-2]
    LL.append(k)
s = 1
for i in range(M+1):
    s = s * LL[List[i]-1]
print(s % 1000000007)

Solution (Python):

"""
AtCoder A
"""

import sys, math, random
import numpy as np







 
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N,M=LI()
    A=[]
    for i in range(M):
        A.append(I())

    tmp1=0
    tmp2=0
    tmp3=0
    out=1
    for n in range(N+1):
        
        
        if A:
            if n==1 and A[0]==n:
                tmp1=0
                tmp2=0
                tmp3=0
                del A[0]
                if A:
                    if A[0]==n+1:
                        print("0")
                        exit()
                continue
            elif n!=0 and A[0]==n:
                out*=tmp3
                tmp1=0
                tmp2=0
                tmp3=0
                del A[0]
                if A:
                    if A[0]==n+1:
                        print("0")
                        exit()
                continue
        if tmp3==0:
            tmp3=1
        else:
            tmp1=tmp2
            tmp2=tmp3
            tmp3=tmp1+tmp2
        
    if tmp3>0:
        out*=tmp3
    print(out%1000000007)
if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
dif = []
cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
for i in range(100000):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % 1000000007)
print(ans % 1000000007)

Solution (Python):
def sol(inp=input):
    mod=10**9+7
    n,m=map(int,inp().split())
    invalids=set(int(inp()) for _ in range(m))
    nums=[0 for _ in range(n+1)]
    nums[0]=1
    for i in range(n-1):
        if i+1 not in invalids:
            nums[i+1]+=nums[i]
        if i+2 not in invalids:
            nums[i+2]+=nums[i]
            nums[i+2]%=mod
    return str((nums[n-1]+nums[n])%mod)
print(sol())

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

a.append(N+1)    

step=[]

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

for i in range(2,N+1):
    if i <a[j]:
        step.append(i)
    else:
        step.append(0)
        j+=1

stepsum=[1]   
if a[0]==1:   
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in step:
    if i==0:stepsum.append(0)
    else:stepsum.append(((stepsum[i-1]+stepsum[i-2]))%1000000007)


ans=stepsum[N]%1000000007
print(ans)

Solution (Python):
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
pre = 0
for i in range(M):
    broken = int(input())
    if pre == broken:
        continue
    pre = broken
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        ans %= 1000000007
        cur = broken + 1
else:
    if N > cur:
        ans *= F[N - cur - 1]
    print(ans % 1000000007)

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

mod = 1000000007
def mul(a, b):
  return ((a % mod) * (b % mod)) % mod


N, M = map(int, input().split())
if M != 0:
  a = int(input())
  ret = mul(1, Fib(a))
  pre_a = a

for i in range(M-1):
  a = int(input())
  if a - pre_a <= 1:
    ret = 0
    break
  else:
    num_step = a - pre_a - 1
    ret = mul(ret, Fib(num_step))
  pre_a = a
    
if M != 0:
  num_step = N - a
  ret = mul(ret, Fib(num_step))
else:
  ret = mul(1, Fib(N+1))
print(ret)

Solution (Python):
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]





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

a= []

for i in range(M):
    a.append(int(input()))

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)



if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))

        if result > 1000000007:
            result = result % 1000000007

    result = result % 1000000007

    print(result)

Solution (Python):
n,m=map(int,input().split())
a=[-1]+[int(input())for i in range(m)]+[n+1]
l=[1,2]+[0]*n+[1]
for i in range(n):
    l[i+2]=l[i]+l[i+1]
c=1    
for i in range(m+1):
    if a[i+1]-a[i]==1:
        c*=0
    else:
        c*=l[a[i+1]-a[i]-3]
print(c%1000000007)

Solution (Python):
class TypicalStairs:
    def __init__(self):
        self.N, self.M = map(int, input().split())
        self.a = []
        for i in range(self.M):
            self.a.append(int(input()))

    def combination(self):
        consecSteps = self.__consecSteps()
        fibs = self.__fibonacci(max(consecSteps))
        comb = 1

        if not self.__canClear():
            print(0)
            return

        
        
        for n in consecSteps:
            comb *= fibs[n]

        print(comb % 1000000007)

    
    def __consecSteps(self):
        consecSteps = []
        
        preNum = -1
        for a in self.a:
            consecSteps.append((a - 1) - preNum)
            preNum = a

        
        consecSteps.append(self.N - preNum)

        return consecSteps

    
    def __canClear(self):
        result = True
        preNum = -1
        
        for a in self.a:
            if a - preNum != 1:
                preNum = a
            else:
                result = False
                break

        return result

    
    def __fibonacci(self, n):
        fibs = [0, 1, 1]

        if n < 3:
            return fibs
        else:
            for i in range(2, n):
                fibs.append(fibs[i - 1] + fibs[i])

        return fibs


typicalStairs = TypicalStairs()
typicalStairs.combination()

Solution (Python):


import sys
import math
import collections


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




def fib(n):
    return fib_list[n-1]





N, M = map(int, sys.stdin.readline().rstrip().split(" "))
As = []
for i in range(M):
    a, = map(int, sys.stdin.readline().rstrip().split(" "))
    As.append(a)
As.append(N+1)
result = 1
current = 0
for a in As:
    diff = a - current - 1
    if diff < 0:
        print(0)
        exit(0)
    
    
    
    
    
    
    
    
    result *= fib(diff+1)
    result %= 1000000007
    
    current = a + 1
print(result)
exit(0)

Solution (Python):
N, M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())
    
cnt_1 = 1
cnt_2 = 0
for i in range(1,N+1):
    tmp = cnt_1
    if a != [] and a[0] == i:
        cnt_1 = 0
        a.pop(0)
    else:
        cnt_1 += cnt_2
    cnt_2 = tmp

print(cnt_1 % 1000000007)

Solution (Python):

"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import bisect

N, M = list(map(int, input().split()))
a = [0]*M
for m in range(M):
    a[m] = int(input())
a = set(a)
MOD = 10**9 + 7

def main(): 
    dp = [0]*(N+2)
    dp[0] = 1
    for n in range(1,N+1):
        if n ==1:
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-1]
                
        else:                        
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-2] + dp[n-1]
                
    
    print(dp[N]%MOD)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Solution (Python):
mod=1000000007
def Fib(n):
  a, b = 1, 2
  if n == 1 or n==0:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a, b = b%mod, (a+b)%mod
    return b
n,m=map(int,input().split())
al=[]
zeroflag=0
fa=-1
cnt=0
for iii in range(m):
  a=int(input())
  cnt+=1
  al.append(a)
  if abs(fa-a)==1:
    zeroflag=1
  fa=a

if zeroflag==1:
  print(0)
else:
  ans=1
  if m==0:
    print(Fib(n))
  else:
    for iii in range(m):
      if iii==0:
        ans=Fib(al[iii]-1)
      if iii==m-1:
        break
      if len(al)>1:  
        num=Fib(al[iii+1]-al[iii]-2)
        ans*=num%mod
    ans*=Fib(n-al[-1]-1)%mod
    print(ans%mod)

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

li = []
lia = [-1]
ans = 1
mod = 1000000007

for i in range(n+10):
    if i == 0 or i == 1:
        li.append(1)
    else:
        li.append((li[i-1] + li[i-2]) % mod)

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        ans = 0
    ans %= mod

print(ans%mod)

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
import itertools
import bisect

INF = 10 ** 10

MODN = 1000000007



N, M = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(stdin.readline().rstrip()) for _ in range(M)]


dp =[0] * (N+10)

for ai in a:
    dp[ai] = -1 

dp[0] = 1

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

    one_step = i + 1
    two_step = i + 2

    if dp[one_step] != -1:
        dp[one_step] += dp[i]
        
    if dp[two_step] != -1:
        dp[two_step] += dp[i]

print(dp[N] % MODN)

Solution (Python):
def fib(n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return b


nm = input().split()
n = ["o"] * (int(nm[0])+1)
for i in range(int(nm[1])):
    this_index = int(input())
    n[this_index] = "x"
n_str = "".join(n)
if "xx" in n_str:
    print(0)
    exit()

n_list = n_str.split("x")
res = 1
for i in n_list:
    res *= fib(len(i)-2)
print(res % 1000000007)

Solution (Python):
n , m = map(int, input().split())
a = []
p = 0
max_wid = 0
if m == 0:
    max_wid = n
else:
    for i in range(m):
      b = int(input())
      a.append(b)
      if i > 0:
          max_wid = max(max_wid, b)
    max_wid = max(max_wid, n - a[m-1])

fib = [1, 1]
for i in range(max_wid):
    l = len(fib)
    fib.append(fib[l-2] + fib[l-1])
ans = 1
if m == 0:
  print(fib[n]%1000000007)
else:
  
  if a[0] == 0:
      ans *= 0
  else:
      ans *= fib[a[0]-1]
  for i in range(m-1):
      if a[i+1] == a[i] + 1:
          ans *= 0
      else:
          ans *= fib[a[i+1]-a[i]-2]
  ans *= fib[n - a[m-1]-1]
  ans %= 1000000007
  print(ans)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")



N, M = l_inpl()
a = { i_inpl(): True for _ in range(M)}




dp = [None] * (N+1)

dp[N] = 1

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

print(dp[0] % 1000000007)

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

memo = {
    0: 1
}
queue = [0]
counter = 0
def step(height, n):
    if height + n not in memo:
        memo[height + n] = memo[height]
        queue.append(height + n)
    else:
        memo[height + n] += memo[height]


while counter < len(queue):
    
    item = queue[counter]
    counter += 1
    if item + 1 not in a and item + 1 <= N:
        step(item, 1)
    if item + 2 not in a and item + 2 <= N:
        step(item, 2)

if N not in memo:
    print(0)
else:
    print(memo[N] % 1000000007)

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


sum1 = 0
sum2 = 0
for i in range(n+1):
    if i == 0:
        sum1 = 1
        continue
    else:
        if A[i]==1 and i != 1:
            sum1 = sum2
            sum2 = 0
        elif i == 1:
            if A[i] == 1:
                sum1 = 1
                sum2 = 0
            else:
                sum2 = 1
        else:
            sum3 = sum1
            sum1 = sum2
            sum2 = sum3 + sum2
            
print(sum2%1000000007)

Solution (Python):
N, M = (int(x) for x in input().split())
F = [0,1]
for i in range(N):
    F.append(F[i]+F[i+1])

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

a.append(N+1)
ans = 1
for i in range(M+1):
    length = a[i+1] - a[i] - 1
    if length == 0:
        print(0)
        exit()
    else:
        ans *= F[length]

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

Solution (Python):



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

memo = {1: 1, 0: 1}
for i in range(2, int(10**5) + 1):
  memo[i] = memo[i-1] + memo[i-2]


stairs = [False for _ in range(N + 1)]
pattern = 1
prev = 0
for _ in range(M):
  a = int(input())
  sub = a - prev - 1
  if sub == -1:
    print(0)
    break
  pattern *= memo[sub]
  prev = a + 1
else:
  sub = N - prev
  pattern *= memo[sub]
  print(pattern % 1000000007)

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

Solution (Python):



def fib(p):
    lst = [1, 2]
    if p >= 1:
        for i in range(p - 2):
            lst.append(lst[i + 1] + lst[i])
        return lst[p - 1]
    elif p == 0:
        return 1
    else:
        print(0)
        exit()


n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
broken.insert(0, -1)
broken.append(n + 1)
ans = 1
for i in range(1, m + 2):
    ans *= fib(broken[i] - broken[i - 1] - 2)
    ans %= 1000000007


print(ans)

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

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

for i in range(N+1):
    if A:
        a = A[0]
    else:
        a = 0
    if len(A) >= 2:
        b = A[1]
    else:
        b = 0

    dp[i] = dp[i] % (10**9 + 7)
    if not i+1 == a:
        dp[i+1] += dp[i]
    else:
        A.popleft()
    if not i+2 == b and not i+2 == a:
        dp[i+2] += dp[i]
print(dp[N])

Solution (Python):


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


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

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

print(dp[N] % 1000000007)

Solution (Python):
n,m=map(int,input().split())
b=[]
b_clone=[]

for i in range(m):
    t=int(input())
    b.append(t)
    b_clone.append(t)


ans_list=[1]

if len(b)!=0 and b[0]==1:
    b.pop(0)
    ans_list.append(0)
else:
    ans_list.append(1)

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

print(ans_list[n])

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

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
for i in range(1,N+5):
    dp[i+2] = dp[i+1] + dp[i]
    dp[i+2] %= MOD
    
if M == 0:
    print(dp[N+1])
    sys.exit()
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= MOD
print(ans)

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

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

Solution (Python):
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] * M
for _ in range(M):
    data[_] = (int(stdin.readline().rstrip()))
 
ans = [1] + [0] * (N)
for i in (set(range(1,N+1)) - set(data)):
    ans[i] = ans[i-1] + ans[i-2]
print(ans[-1] % 1000000007)

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

now = 0
ans = 1
j = 0
for i in range(M):
    if now == a[i] - 1:
       now = a[i] + 1 
    elif now == a[i]:
        ans = 0
        break
    else:
        j = (a[i] - 1) - now
        k1 = 0
        k2 = 1
        k3 = 1
        for n in range(j):
            k3 = k2
            k2 += k1
            k1 = k3
        ans *= k2
        now = a[i] + 1
if ans > 0:
  j = N - now
  k1 = 0
  k2 = 1
  k3 = 1
  for n in range(j):
      k3 = k2
      k2 += k1
      k1 = k3
  ans *= k2
print(ans % 1000000007)

Solution (Python):
N,M = map(int,input().split())
a = list(int(input())for i in range(M))
a= [-1]+a+[N+1]
r = []
for i in range(M+1):
    r.append(a[i+1]-a[i]-1)
fi = [0,1,1]
for i in range(max(r)):
    fi.append(fi[-1]+fi[-2])
ans = 1
for i in r:
    ans = (ans*fi[i])%(10**9+7)
print(ans)

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

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


a.append(N+1)



diff = []
diffmax = 0
for i, v in enumerate(a):
  if i != len(a)-1:
    steps = a[i+1] - a[i]
    diff.append(steps)
    if diffmax < steps:
      diffmax = steps


      
actptn = [0,1]
for i in range(2,diffmax):
  actptn.append(actptn[i-1] + actptn[i-2])


ans = 1
for i in diff:
  ans = (ans* actptn[i-1]) % 1000000007
print(ans)

Solution (Python):
import math
from fractions import Fraction
import sys


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a;
        self.b = b;
        self.c = c;
        self.d = d;
    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)
    
def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a



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

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:

        count *= fib(x)
print(int(count)%1000000007)