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):
mod = 1000000007
N, M = map(int, input().split())
A = list(set([int(input()) for _ in range(M)]))
M = len(A)
for i in range(M-1):
    if A[i] + 1 == A[i+1]:
        print(0)
        exit()

check = [0]*(N+2)
for i in range(M):
    check[A[i]] = 1
    check[A[i]+1] = 1
    check[A[i]+2] = 1

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
i = 2
while i <= N:
    if check[i]:
        dp[i] = dp[i-1]    
        i += 1
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
        i += 1
print(dp[N])

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1

    elif i+1 == last_broken:
        pass

    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7


    if i + 2 == next_broken:
        flug = 1

    else:
        if i == 0 and len(broken_lst) != 0:
            if broken_lst[0] == 2 and next_broken == 1:
                continue
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7

    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**7)
lst = dict({0: 1, 1: 1, 2: 2})
def calc(n):
    if (n in lst):
        return lst[n]
    else:
        lst[n] = calc(n-1) + calc(n-2)
        return lst[n]

N, M = [int(x) for x in input().split()]
if (M != 0):
    a_list = [int(input()) for _ in range(M)]
    span_list = [a_list[0]-1]
    for i, a in enumerate(a_list[:-1]):
        if (a_list[i+1] - a) == 1:
            print(0)
            exit()
        else:
            span_list.append(a_list[i+1] - 2 - a)
    span_list.append(N - a_list[-1] -1)
else:
    span_list = [N]
max_span = max(span_list)
for i in range(max_span+1):
    calc(i)
ans = 1
for span in span_list:
    ans = (ans * lst[span]) % (10**9+7)
print(ans)

Solution (Python):
N, M = map(int, input().split())
broken = [int(input()) for i in range(M)]
broken.append(N+1)
safe = []
i = 0
j = 0
temp = 0

def fb(num):
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

while i != N+2:
    if i < broken[j]:
        temp += 1
        i += 1
    else:
        safe.append(temp)
        temp = 0
        i += 1
        if j < len(broken)-1:
            j += 1
        else:
            break
     

ans = 1
i = 0
for i in range(len(safe)):
    ans = ans * fb(safe[i])

safe2 = [str(i) for i in safe]

if safe2.count('0') != 0:
    print(0)
else:
    print(ans%1000000007)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]+[n+1]
mod=1000000007
ms=[0]*(n+1)

def dd(n):
    if ms[n]>0:
        return ms[n]
    if n==1:
        ms[n]=1
        return 1
    if n==2:
        ms[n]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n]=m
    return m

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

print(ans)

Solution (Python):
import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

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

a.append(n+1)
a = np.array(a)


if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*110000
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    

    if m == 0:
        print(dp[n+1])
    else:
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)

Solution (Python):



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

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib_memo(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib_memo(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)

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

def fibonacci(n):
    if n == 0:
        return 0 
    elif n == 1:
        return 1 
    return fibonacci_sub2(n-2, 1, 0) 

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
a.append(N+1)
anser = 1
start = 0
for i in range(M+1):
    Bre = a.pop(0)
    if Bre == start:
        anser = 0
        break
    anser = anser * fibonacci(Bre - start + 1)
    start = Bre + 1

print(anser % 1000000007)

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

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

def memoize(f):
  table = {}
  def func(*args):
    if not args in table:
      table[args] = f(*args)
    return table[args]
  return func

@memoize

def step(n):
  if n==0:
    return(1)
  elif n==1:
    return(1)
  else:
    return((step(n-1)+step(n-2))%1000000007)

if M==0:
  print(step(N))
else:
  b = [0]*(M+1)
  b[0] = step(a[0]-1)
  if M>=2:
    for i in range(M-1):
      if a[i+1]-a[i] == 1:
        b[i+1] = 0
      else:
        b[i+1] = step(a[i+1]-a[i]-2)
  b[M] = step(N-a[M-1]-1)

  answer = 1
  for i in range(M+1):
    answer = answer*b[i]%1000000007
  print(answer)

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

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


def count_steps(NN):

    steps = [0] * (NN + 3)
    steps[1] = 1
    steps[2] = 2
    for i in range(3, NN + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
    return steps[NN]

if m == 0:
    ans = count_steps(n)
else:
    if a[0] == 1:
        ans = 1
    else:
        ans = count_steps(a[0] - 1)

    for i in range(1, len(a)):
        temp = a[i] - a[i - 1] - 2
        if temp < 0:
            ans = 0
        elif temp == 0:
            ans *= 1
        else:
            ans *= count_steps(temp)

    temp = n - a[-1] - 1
    if temp > 0:
        ans *= count_steps(temp)
print(ans%1000000007)

Solution (Python):
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

results = []

flag = True

for m in range(1, M):
    if a[m] - a[m - 1] == 1:
        flag = False
        break

flag_end = True
if M == 0:
    flag_end = False

def Fib(n):
    a, b = 0, 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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result % mod)
elif not flag:
    print(0)
else:
    print(Fib(N + 2) % mod)

Solution (Python):
import re
import math

def fib(n):
    a, b = 0, 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())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('000*', steps)
b = len(re.findall('11', steps))

count = 1
for i in a:
    count *= fib(len(i)+1) % 1000000007

if b != 0:
    print(0)
else:
    print(count % 1000000007)

Solution (Python):

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

inf=float("inf")

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

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if fib_memo[cur_fib_i]==0:
            pass
        else:
            fib_memo[cur_fib_i] = fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2]
        cur_fib_i += 1
print(fib_memo[n]%1000000007)

Solution (Python):
import sys

N, M = list(map(int, input().split()))
A = set()

sys.setrecursionlimit(N * 10)

Z = 1000000007

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


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


def d(n):
    if n < 1:
        return 0
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]
    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Solution (Python):
def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)

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

import sys

sys.setrecursionlimit(10**9)

def countWays_memo(n):
    memo = [-1]*(n+1)
    def _countWays(n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        else:
            if memo[n] > -1:
                return memo[n]
            else:
                memo[n] = _countWays(n-1) + _countWays(n-2) 
                return memo[n]
    return _countWays(n)
    
if m == 0:
    print(countWays_memo(n)% 1000000007)
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

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

mod = 10 ** 9 + 7

def Fib(n):
    a, b = 0, 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


if m > 0:
    ans = Fib(A[0] + 1) % mod
    for i in range(m - 1):
        if A[i] == A[i + 1]:
            continue
        ans *= Fib(A[i + 1] - A[i])
        ans %= mod
    ans *= Fib(n - A[-1] + 1)
    ans %= mod
else:
    ans = Fib(n + 2) % mod
print(ans)

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  if M == 0:
    max_dis = N
    a.append(-1)
  else:
    max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append((fib[-1] + fib[-2]) % MOD)
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1] % MOD
  
  print(ans % MOD)

Solution (Python):

stair, bre_num = list(map(int,input().split()))
bre_stairs = []
mae = -1
dekiru = True
for _ in range(bre_num):
	b = int(input())
	if b-mae==1:
		dekiru = False
	bre_stairs.append(b)
	mae = b

bre_stairs.insert(0,-1)
bre_stairs.append(stair+1)

sosu = 1

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

if dekiru:
	for saki,ato in zip(bre_stairs[1:],bre_stairs[:-1]):
		pat = saki-ato-1
		sosu = sosu * Fib(pat)
	print(sosu % 1000000007)

else:
	print(0)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
aa = [False]*(N+1)
for _ in range(M):
    a = int(input())
    aa[a] = True

dp = [1]*(N+1)
if aa[1]:
    dp[1] = 0

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

print(dp[-1]%mod)

Solution (Python):
import sys

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

steps = [0, 1, 2]
for i in range(3, N+1):
    steps.append(steps[i-1] + steps[i-2])
  
if M == 0:
    print(steps[N] % 1000000007)
    sys.exit()
    
As = []
for i in range(M):
    As.append(int(input()))
    
deffs = []

if As[0] != 1:
    deffs.append(As[0] - 1)
else:
    deffs.append(1)

for i in range(1, M):
    d = As[i] - As[i-1] -2
    if d == 0:
        deffs.append(1)
    elif d == -1:
        deffs.append(0)
    else:
        deffs.append(d)

if N - As[M-1] - 1 != 0:
    deffs.append(N - As[M-1] - 1)
else:
    deffs.append(1)

ans = 1

for i in range(len(deffs)):
    ans *= steps[deffs[i]]
    
print(ans % 1000000007)

Solution (Python):
"""
F = [1,1]
def fibo(n):
    if n <= len(F):
        return F[n-1]
    while len(F) < n:
        F.append(F[-1] + F[-2])
    return F[n-1]
"""

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

if M == 0:
    B = []
    B.append(N+1)
elif M == 1:
    B = []
    B.append(A[0])
    B.append(N - A[0])

else:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])


ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)

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

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

def is_enabled():
    _a = -1
    for a in A:
        if _a + 1 == a:
            return False
        _a = a
        
    return True


X =[1, 2]
BAD = [-1] + A + [N+1]

def pattern(a, b):
    a_b = b-a
    if a_b == 0:
        return 1
    if len(X) >= a_b:
        return X[a_b-1]
    else:
        while len(X) <= a_b:
            X.append(X[-1]+X[-2])
        return X[a_b-1]


if is_enabled() == False:
    print(0)
else:
    ans = 1
    for a, b in zip(BAD[:-1], BAD[1:]):
        ans *= pattern(a+1, b-1)
        
    ans = ans %  1000000007
    print(ans)

Solution (Python):
from itertools import product

INF = 1000000007

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

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

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


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

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

for k in a:
	tmp.append(fib(k - start) % INF)
	start = k + 1

for j in tmp:
	ans *= j
	ans %= INF

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

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

amari = 1000000007
cnt = [0]*(N+2)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+2):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
def calc(ans):
    if M == 0:
        return cnt[N+1]

    for i in range(M): 
        if i == 0:
            ans*= cnt[A[i]]
        elif i > 0 and i < M:
            ans*=cnt[A[i] - A[i-1]-1]

        if i == M-1:
            ans*= cnt[N - A[i]]
        
        if ans == 0:
            break
    
        ans %= amari
        
    return ans

print(calc(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10000001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)%1000000007

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1%1000000007 if n==0 else fibonacci_sub2(n-1, (fibo_minus1+fibo_minus2)%1000000007, fibo_minus1%1000000007)%1000000007


N,M = map(int, input().split()) 
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum)

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

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

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

l = [-1] * (n + 1)
l[n] = 1
l[n-1] = a[n-1]

num = n - 2
while num >= 0:
    if a[num] == 1:
        l[num] = (l[num+1] + l[num+2]) % mod
    else:
        l[num] = 0
    num -= 1

print(l[0])

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


def func(n):
    """メモ化フィボナッチ"""
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1)%1000000007 + _fib(n-2)%1000000007
        return memo[n]

    return _fib(n)

a_p = 0
result = 1
for i in range(M):
  a_c = int(input()) - 1
  
  if a_c + 1 == a_p: 
    print(0)
    quit()
  result = ((func(a_c - a_p + 1)%1000000007) * (result%1000000007))%1000000007
  a_p = a_c + 2
  
result = ((func(N - a_p + 1)%1000000007) * (result%1000000007))%1000000007
print(result)

Solution (Python):
def calcPatt(steps):
    if steps <= 1:
        return 1
    elif steps == 2:
        return 2
    ll = {}
    
    for i in range(steps)[::-1]:
        if i + 1 == steps:
           ll[i] = 1
        elif i + 2 ==steps:
            ll[i] = 2
        else:
            ll[i] = ll[i+1] + ll[i+2]
    
    return ll[0]

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

before = 0
f = True
ll = []
ax = {}
for i in range(M):
    
    a = int(input())
    ax[i] = a
    limit = a - 1
    stepRenge = limit  - before
    
    if not f and stepRenge == -1:
        ll.append(0)
        break
    ll.append(calcPatt(stepRenge))
    before = limit + 2
    f = False
    


stepRenge = N  - before
ll.append(calcPatt(stepRenge))

pro = 1
for i in ll:
    pro = (pro * i) % 1000000007
 
print(pro)

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

cur_step = 0
steps = []
ans = 1
for a in A:
	if a-cur_step == 0:
		ans = -1
		break
	if a == 1:
		steps.append(1)
		cur_step = 2
		continue
	steps.append(a-1-cur_step)
	cur_step = a+1

pat = [1,2]
inf = 10**9+7
while len(pat) < max(steps):
	pat.append((pat[-1]+pat[-2])%inf)

if ans == -1:
	print(0)
else:
	for step in steps:
		if step == 0:
			continue
		ans = (ans*pat[step-1])%inf
	print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n,m = list(map(int, input().split()))
s = [0 for i in range(n+1)]
t = [-1 for i in range(n+1)]
for i in range(m):
    x = int(input())
    s[x] = 1

def dx(r):
    global t
    if t[r]>=0:
        return t[r]
    x=0
    y=0
    
    if s[r+1]==0 and r==n-2:
        return 2
    if s[r+1]==1 and r==n-2:
        return 1
    if r==n-1:
        return 1
    if r==n:
        return 0
    if s[r+1] == 0:
        x=dx(r+1)
    if s[r+2] == 0:
        y=dx(r+2)
    
    t[r]=(x+y)%1000000007
    return (x+y)%1000000007

ans=dx(0)

print(ans)

Solution (Python):
def fibonacci(n):
    dp = [1 for i in range(n)]
    for i in range(2,n):
        dp[i] = dp[i-2]+dp[i-1]
    return dp[n-1]

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

b = -1

ans = 1
for i in range(m+1):
    a = b
    if i==m:
        b = n+1
    else:
        b = int(input())
    c = b-a-2
    if c == -1:
        print(0)
        exit()
    ans *=fibonacci(c+1)
    ans %= 10**9+7

print(ans)

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

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

B = ['.'] * (N + 1) 
for a in A:
    B[a] = '
    
dp = [0] * (N + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '
    dp[2] = 1
elif B[1] == '.' and B[2] == '
    dp[1] = 1
    
for i in range(3, N + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(dp[N])

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

mm = 1000000007
n, m = na()
ai = [-1]
for i in range(m):
    ai.append(int(input()))
ai.append(n+1)
li = [1, 1]
for i in range(n+4):
    li.append(li[i] + li[i+1])
ans = 1

if m == 0:
    print(li[n] % mm)
else:
    for i in range(len(ai) - 1):
        if ai[i+1] - ai[i] == 1:
            ans = 0
            break
        else:
            ans *= li[(ai[i+1] - ai[i]) - 2]
            ans = ans % mm
    print(ans)

Solution (Python):
n, m = [int(_) for _ in input().split(' ')]
b = [False] * (n + 1)
for _ in range(m):
    b[int(input())] = True

M = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if not(b[1]):
    dp[1] = 1
for i in range(2, n + 1):
    if b[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % M
print(dp[n])

Solution (Python):
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
A = []
for _ in range(M):
    A.append(int(input()))
A.append(0)

prev = 1
prev_prev = 0
m = 0
for i in range(1,N+1):
    if A[m] == i:
        prev, prev_prev = 0, prev
        m += 1
    else:
        prev, prev_prev = (prev + prev_prev) % MOD, prev
print(prev)

Solution (Python):
NM = list(map(int,input().split()))
N = NM[0]
M = NM[1]

A =[]
while True:
    try:
        A.append(int(input()))
    except:
        break;

countlist = [1,1,2]
if N >3:
    for i in range(3,N+1):
        a = countlist[i-2]+countlist[i-1]
        if a>1000000007:
            a = a%1000000007
        countlist.append(a)

t = 0
count = 0
out = []

if N >1:
    for i in range(1,N+1):
        count+=1
        if ((t<len(A))and(i==A[t])):
            t+= 1
            while ((t<len(A))and(i==A[t])):
                t+=1
            if count > 0:
                out.append(countlist[count-1])
            else:
                out.append(0)
                break
            count = -1


if count>=0:
    out.append(countlist[count])

output = 1

for i in range(len(out)):
    output = output*out[i]
    if output > 1000000007:
        output = output%1000000007

print(output)

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

now_step = 0
ans = 1
N, M = map(int, input().split(" "))
for i in range(M):
    a = int(input())
    if now_step == a:
        ans *= 0
        break
    elif now_step == (a - 1):
        now_step = a + 1
        continue
    else:
        ans *= Fib((a - 1) - now_step)
        now_step = a + 1
if now_step != N:
    ans *= Fib(N - now_step)
print(ans % 1000000007)

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

mod=1000000007

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


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

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

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



a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  

print(dp[n])

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

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    li.append(n+1)
    if len(li)>0:
        for i in range(len(li)):
            
            if i>0:
                li2.append(li[i]-li[i-1]-1)
                if li[i]-li[i-1]==1 and i<len(li):
                    return 0
            else:
                li2.append(li[i])
                
    
    return convi(li2)
                

print(count(li,n)%1000000007)

Solution (Python):
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
pat = [0] * (N+3)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = []
    if len(A) > 1:
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

Solution (Python):
patterns_dictionary = {}
patterns_dictionary[1] = 1
patterns_dictionary[2] = 1


def patterns(start_n, broken_n):
    
    diff = broken_n - start_n
    if diff in patterns_dictionary:
        return patterns_dictionary[diff]
    for ii in range(len(patterns_dictionary)+1, diff+1):
        patterns_dictionary[ii] = patterns_dictionary[ii-1] + patterns_dictionary[ii-2]
    ans = patterns(start_n, broken_n - 1) + patterns(start_n, broken_n - 2)
    patterns_dictionary[diff] = ans
    return ans


inp = input()
split_input = inp.split()
n = int(split_input[0])
m = int(split_input[1])
start = 0
patterns_count = 1

for i in range(m+1):
    if i == m:
        broken = n + 1
    else:
        inp = input()
        broken = int(inp)
    if broken == start:
        
        print(0)
        exit()
    
    p = patterns(start, broken)
    patterns_count = (patterns_count * p) % 1000000007
    start = broken + 1

print(patterns_count)

Solution (Python):
mod=1000000007
n,m=map(int,input().split())
d=set([])
w=[0]*(n+2)

for i in range(m):
    a=int(input())
    d.add(a)
for i in range(n):
    if i==0 and 1 not in d:
        w[1]=1
    elif i==0 and 1 in d:
        w[1]=0
    if i==0 and 2 not in d:
        w[2]=1
    elif i==0 and 2 in d:
        w[2]=0
    if i>0:
        if i+1 not in d:
            w[i+1]=(w[i+1]+w[i])%mod
        if i+2 not in d:
            w[i+2]=w[i]
print(w[-2]%mod)

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

def dfs(x):
  if x == N:
    return 1
  if x > N:
    return 0
  if memo[x] >= 0:
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

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



memo = [-1]*(N+1)
for ai in a:
  memo[ai] = 0
count = dfs(0)
print(count%1000000007)

Solution (Python):


import math

base = 1000000007

def main():
    n,m = map(int,raw_input().split())
    ms = []
    for i in range(m):
        ms.append(int(raw_input()))
    prev = -1
    for i in ms:
        if i - prev <= 1:
            print 0
            return
        prev = i
    prev = 0
    fib = 1
    fib1 = 0
    fib2 = 1
    cur = 0
    total = 1
    for i in range(0,n+1):
        if len(ms) > cur:
            curM = ms[cur]
            if i < curM:
                if cur >= 1 and i == ms[cur-1]:
                    continue
                fib = fib1 + fib2
                fib1 = fib2
                fib2 = fib
            else:
                total = (total * fib1) % base
                fib = 1
                fib1 = 0
                fib2 = 1
                cur += 1
        else:
            if cur >= 1 and i == ms[cur-1]:
                continue
            if i != n:
                fib = fib1 + fib2
                fib1 = fib2
                fib2 = fib
            else:
                total = (total * fib) % base
    print total

if __name__ == "__main__":
    main()