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.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

a = [int(input()) for i in range(m)]
a.append(n+1)

ar = list(range(n+1))

tmp = 0
ans = 1
counter = 0

def fib1(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib1(n - 1) + fib1(n - 2)

for i in range(len(a)):
    cnt = len(ar[tmp:a[i]]) 
    ans = (ans*(fib1(cnt-1)%1000000007))%1000000007
    if i+1 < len(a):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
    tmp = a[i]+1

print(ans)

Submission status: Runtime Error

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

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0
        print(ans)
        exit()

SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(int(ans))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a=[]
for _ in range(M):
    a.append(int(input()))
    
kaidan = [1, 2]

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

ans = 1

if a[0] - 1 > 0:
    ans *= kaidan[a[0] - 2]
  
for i in range(M-1):
  if((a[i] + 1) > (a[i+1] - 1)):
    ans *= 0
  else:
    ans *= (kaidan[a[i+1] - a[i] - 3])

if N - (a[M - 1] + 1) > 0:
    ans *= kaidan[N - (a[M - 1] + 2)]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# def fibonacci(n):
#     if n == 0:
#         return 0
#     elif n == 1:
#         return 1
#     n+=2
#     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)

from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

N,M = map(int, input().split()) #1 2
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] + 2))
    fibsum %= 1000000007 
print(fibsum)

Submission status: Runtime Error

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

#連続する壊れていない階段の数を求める
li_new = [-1]*(m+1)
li_new[0] = li[0]
for i in range(1,m):
    li_new[i] = li[i] - (li[i-1]+1)
li_new[m] = n - li[m-1]
#print(li_new)

#必用な部分までのフィボナッチ数をリストに保存
fib = [0] * (max(max(li_new)+1,3))
fib[0] = 0
fib[1] = 1
fib[2] = 1
for i in range(3,max(li_new)+1):
    fib[i] = fib[i-2] + fib[i-1]
#print(fib)

#連続する壊れていない階段の数ごとのフィボナッチ数の積
ans = 1
for i in li_new:
    ans *= fib[i]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=10000)
def countPattern(s, cnt):
    if s > 1:
        cnt = countPattern(s-2, cnt)
        cnt = countPattern(s-1, cnt)
        return cnt
    else:
        return cnt + 1


ans = 1
a_pre = -1
for mi in range(m):
    a = int(input())
    if a == a_pre:
        break
    elif a == a_pre + 1:
        ans = 0
    ans = ans * countPattern(a-a_pre-2, 0) % 1000000007
    a_pre = a

a = n + 1
ans = ans * countPattern(a - a_pre - 2, 0) % 1000000007

print(ans)

# TLE

Submission status: Runtime Error

Solution code:
i = int(input(), 2)
s = 0

for x in range(i+1):
	s = s + 2**bin(x).count('1')

print(s % (10e8+7))

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
ans = 1
if M != 0:
    a = [int(input()) for _ in range(M)]
else:
   ans *= fib(N)
   print(ans) 

z = False

def fib(n):
    a1 = 2
    a2 = 1 
    if n==2:
        return 2
    elif n==1:
        return 1
    else:
        count = 1
        for i in range(n-2):
            count = a1 + a2
            a2 = a1
            a1 = count
        return count



for i in range(M):
    if i != 0:
        if a[i]-a[i-1] != 1:
            ans *= fib(a[i]-a[i-1]-2)
        else:
            z = True
            break
    else:
        ans *= fib(a[i]-1)

ans *= fib(N-a[-1]-1)

if z:
    print(0)
else:
    print(str(ans%1000000007))

Submission status: Runtime Error

Solution code:
N_M = [int(e) for e in input().split()]
div = 1000000007
a=[]
for i in range(N_M[1]):
  a.append(int(input()))

stair = []
for i in range(N_M[0]+1):
  stair.append(i)

stairs = [[]]
start=0
for i in range(len(a)+1):
  if(i==len(a)):
    stairs.append(stair[start:N_M[0]+1])
    break
  stairs.append(stair[start:a[i]])
  start=a[i]+1

stairs = [x for x in stairs if x]

def num(stair):
  number=0
  if(stair==0):
    return 1
  elif(stair==1):
    return 1
  elif(stair==2):
    return 2
  elif(stair>2):
    number += num(stair-1)
    number += num(stair-2)
    
  return number

answers = []
for i in range(len(stairs)):
  answers.append(num(len(stairs[i])-1))

answer=1
for i in range(len(answers)):
  answer *= answers[i]

print(answer%div)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(n)

list_a = []
for i in range(m):
    list_a.append(int(input()))
    
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)

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

if steps[0] == 0:
    steps[0] = 1

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

ans = 1
for k,v in dict_steps.items():
    ans *= countWays_memo(k)**v
    
if steps.count(0) == 0:
    print(ans% 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7
a = []
for i in range(m):
    a.append(int(input()))

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


def dfs(step):
    if dp[step] >= 0:
        return dp[step]
    if step - 1 in a and step - 2 in a:
        return 0
    cnt = 0
    if step <= 0:
        return 1
    if step - 1 >= 0 and step - 1 not in a:
        cnt += dfs(step - 1)
    if step - 2 >= 0 and step - 2 not in a:
        cnt += dfs(step - 2)
    dp[step] = cnt
    return cnt % mod


print(dfs(n))

Submission status: Runtime Error

Solution code:
import math
N,M = [int(x) for x in input().split()]
a = [int(input()) for j in range(M)]

def combinations_count(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))

def keisan(n,r):
    count = 0
    while n >= r:

        count += combinations_count(n,r)
        n -= 1
        r += 1

    return count
result = 1

for i in range(M):
    if a[i] - a[i-1] == 1:
        result = 0
        break
    elif i == 0:
        result *= keisan(a[i]-1,0)
    else:
        result *= keisan(a[i]-a[i-1]-2,0)

else:
    result *= keisan(N - a[M-1]-1,0)

print(int(result)%1000000007)

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]
AS = {}
for _ in range(M):
    i = int(input())
    AS[i] = 0
visited = {}

def dfs(i):
    if i == N:
        return 1
    if i > N:
        return 0
    if AS.get(i) == 0:
        return 0
    if i in visited:
        return visited[i]
    total = 0
    total += dfs(i + 1) % 1000000007
    total += dfs(i + 2) % 1000000007
    visited[i] = total
    return total

print(dfs(0))

Submission status: Runtime Error

Solution code:
def Fib(n):
    if n==0:
        return 1#F0
    elif n==1:
        return 1 #F1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 1 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo

n,m = map(int,input().split())
s =[]
ans = 1
for i in range(m):
    s.append(int(input()))
    if i == 0:
        ans*=Fib(s[0])
    else:
        if s[i]-s[i-1] == 1:
            print(0)
            exit()
        if  s[i]-s[i-1] == 0:
            continue
        ans *= Fib(s[i]-s[i-1]-1)
if s == []:
    ans *= Fib(n)
    print(ans)
    exit()
if s[-1] != n:
    ans *= Fib(n-s[-1])
    
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
phi = (1 + math.sqrt(5)) / 2
def counter(n):
    if n == 1:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = round(phi**(a[0]) / math.sqrt(5)) % (10**9+7)
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import math
def cmb(n, r):
    return math.factorial(n)// ( math.factorial(n-r) * math.factorial(r) )



N,M = input().split()

N = int(N)
M = int(M)

a = []
ans = 1

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


for k in range(M-1):
    if (a[k+1] - a[k] == 1):
        ans = 0
            
    
    
for i in range(M + 1):
    

    if (i == 0):
        dan = a[i] - 1
    elif (i == M):
        dan = N - a[i - 1] - 1
    else:
        dan = a[i] - a[i - 1] - 2

    abletwo = (dan - (dan % 2)) // 2
    now = 0

    if (dan != 0):

        for j in range(abletwo + 1):

            now += cmb (dan - j , j )

    else:
        now = 1
        
    ans *= now
    

ans = ans % 1000000007
print (ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
sum_move = 1
fact = [-1] * (N+1)
fact[0] = 1


def factorial(num, fact):
    if fact[num] > 0:
        return fact[num]
    else:
        fact[num] = factorial(num-1, fact) * num
        return fact[num]


step_begin = 0
for i in range(M+1):
    tmp_sum = 0
    step_end = a[i] - 1
    step_num = step_end - step_begin
    for j in range(step_num//2 + 1):
        tmp_sum += factorial(step_num - j, fact) \
            // factorial(j, fact) // factorial(step_num - 2 * j, fact)
    if tmp_sum != 0:
        sum_move *= tmp_sum
    else:
        sum_move = 0
        break
    step_begin = a[i] + 1

print(sum_move % 1000000007)

Submission status: Runtime Error

Solution code:
N_M = [int(e) for e in input().split()]
div = 1000000007
a=[]
for i in range(N_M[1]):
  a.append(int(input()))

stair = []
for i in range(N_M[0]+1):
  stair.append(i)

stairs = [[]]
start=0
for i in range(len(a)+1):
  if(i==len(a)):
    stairs.append(stair[start:N_M[0]+1])
    break
  stairs.append(stair[start:a[i]])
  start=a[i]+1

stairs = [x for x in stairs if x]
print(stairs)
def num(stair):
  number=0
  if(stair==0):
    return 1
  elif(stair==1):
    return 1
  elif(stair==2):
    return 2
  elif(stair>2):
    number += num(stair-1)
    number += num(stair-2)
    
  return number

answers = []
for i in range(len(stairs)):
  answers.append(num(len(stairs[i])-1))

answer=1
for i in range(len(answers)):
  answer *= answers[i]

print(stairs)
print(answer%div)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a_list=[]
result_list=[]
for i in range(m):
	a_list.append(int(input()))
if n ==1:
	print(1)
elif n ==2 and 1 not in a_list:
	print(2)
elif n==2 and 1 in a_list:
	print(1)
else:
	if 1 in a_list:
		result_list.append(0)
	else:
		result_list.append(1)
	if 2 in a_list:
		result_list.append(0)
	elif 2 not in a_list and 1 in a_list:
		result_list.append(1)
	else:
		result_list.append(2)
	for i in range(2,n):
		if i+1 in a_list:
			result_list.append(0)
		else:
			result_list.append(result_list[i-1]+result_list[i-2])
print(result_list[n-1]%1000000007)

Submission status: Runtime Error

Solution code:
mod = 1000000007

def feb(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    k = (n + 1) / 2 if n % 2 else n / 2
    fib_k = feb(k)
    fib_k_1 = feb(k - 1)
    return fib_k**2 + fib_k_1**2 if n % 2 else (2 * fib_k_1 + fib_k) * fib_k

    # if n==0:
    #     return 0
    # if n==1:
    #     return 1
    # else:
    #     return feb(n-1)+feb(n-2)
    # root = math.sqrt(5)
    # return int((1/root)*(((1+root)/2)**n - ((1-root)/2)**n))

def calculate(n, b):
    diff = [b[i+1] - b[i] - 1 for i in range(len(b)-1)]
    diff.insert(0, b[0])
    diff.append(n - b[-1])
    sum = 1
    for d in diff:
        if d == 0:
            return 0
        sum *= feb(d)%mod
        sum = sum%mod
    return sum


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

print(calculate(n, b))

Submission status: Runtime Error

Solution code:
def countStep(n):
    global S, b
    if n<0:
        return 0
    elif n==0:
        return 1
    elif str(n) in b:
        count = S[n]
        return count
    else:
        count1 = countStep(n-1)
        count2 = countStep(n-2)
        count = count1 + count2
        b.append(str(n))
        S[n] = count
        return count

N,M = map(int,input().split())
b = []
for _ in range(M):
  b.append(input())
S = [0] * (N+1)

print(countStep(N) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, input().split())
if n == 1:
    print('1')
    exit(0)
if n == 2 and m == 0:
    print('2')
    exit(0)
a = []
for i in range(m):
    a.append(int(input()))
if n == 2 and m == 1:
    print('1')
    exit(0)
fib = [0, 1, 2]
for i in range(3, n+1):
    fib.append(fib[i - 2] + fib[i - 1])
way = []
for i in range(m):
    way.append(fib[int(a[i])+1] - fib[int(a[i])])
    if i > 0:
        if a[i - 1] + 1 == a[i]:
            print('0')
            exit(0)
way.append(fib[n - int(a[m-1]) - 1])
ans = 1
for i in range(len(way)):
    ans *= way[i]
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
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())
if M == 0:
  print(FibRe(N+2))
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
if m > 0:
  a = set([int(input()) for i in range(m)])
else:
  a = set([])

if n == 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

pat = (pt[-1] % 1000000007)
print(pat)

Submission status: Runtime Error

Solution code:
def fib(n):
    n += 1
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

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

if M == 0:
    print(fib(N))
    exit()

A = [int(input()) for _ in range(M)]
L = [0] * (M+1)

ans = 1

L[0] = fib(A[0]-1) % (10**9 + 7)
L[M] = fib(N-(A[M-1]+1)) % (10**9 + 7)

for i in range(1,M):
    if A[i]-A[i-1] == 1:
        print(0)
        exit()
    L[i] = fib((A[i]-1)-(A[i-1]+1)) % (10**9 + 7)

for j in range(M+1):
    ans = (ans * L[j]) % (10**9 + 7)

print(ans)

Submission status: Runtime Error

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

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

if m!=0:
    a = [int(input()) for i in range(m)]
    if a[0]!=1:
       dp[1]=1
    else:
        dp[1]=0
        cnt+=1
 
    for i in range(n-1):
        if a[cnt]==i+2:
            dp[i+2]=0
            if cnt!=(m-1):
                cnt+=1
        else:
            dp[i+2]=dp[i+1]+dp[i]
 
else:
    for i in range(n-1):
        dp[i+2]=dp[i+1]+dp[i]


print(dp[n]%(1000000007))

Submission status: Runtime Error

Solution code:
import copy
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
if n == 1:
    if m == 1:
        print(0)
    else:
        print(1)
else:
    if 1 == a[0]:
        if 2 in a:
            a1 = 0
            a2 = 0
        else:
            a1 = 0
            a2 = 1
    else:
        if 2 in a:
            a1 = 1
            a2 = 0
        else:
            a1 = 1
            a2 = 2
    for i in range(3,n+1):
        if i in a:
            a1 = copy.copy(a2)
            a2 = 0
        else:
            an = a1 + a2
            a1 = copy.copy(a2)
            a2 = copy.copy(an)
    print(a2 % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [int(input())for i in range(0,m)]
div = 1000000007
pat = [1,1]
for i in range(2,n+1):
    pat.append(pat[i-2]+pat[i-1])
ans = pat[a[0]-1]
for i in range(1,m):
    ans *= pat[a[i] - a[i-1] -2]
ans *= pat[n- a[-1]-1]
ans %= div
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = [int(input()) for _ in range(m)]
count = 0
def dfs(pos):
    global count
    if pos >= n-1:
        count += 1
        return True
    for i in [1,2]:
        if pos+i in a_list:
            pass
        else:
            dfs(pos+i)
    return True

dfs(0)
print(count%1000000007)

Submission status: Runtime Error

Solution code:
def fio(x,y):
    return x+y

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

n = [0,1,2]

for i in range(1,100000):
    n.append(fio(n[i],n[i+1]))

last_break = 0
ans = 1
ans = ans * n[a[0]-last_break-1]
ans = ans % 1000000007
last_break = a[0]

if a[0] == 1:
    ans = 1
    
for i in range(1,m):
    ans = ans * n[max(0,a[i]-last_break-2)]
    ans = ans % 1000000007
    last_break = a[i]
    
ans = ans * n[n_a-last_break-1]
ans = ans % 1000000007
if m == 0:
    ans = n[n_a]
    ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
def fib2(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

inp = input()
n = int(inp.split()[0])
m = int(inp.split()[1])
a = []
for i in range(m):
  a.append(int(input()))
  
mul_list = []
nochance = False
for j in range(m+1):
  if j == 0:
    ss = a[0]
    if ss <= 0:
      p = 1
    else:
      p = fib2(ss)
    mul_list.append(p)
  elif j == m:
    step = n - a[-1]
    p = fib2(step)
    mul_list.append(p)
  else:
    step = a[j] - a[j-1] - 1
    if step == 0:
      nochance = True
      break
    p = fib2(step)
    mul_list.append(p)
    

if nochance:
  print(0)
else:
  ans = 1
  for b in mul_list:
    ans *= b
  print(ans%1000000007)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True





if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+1)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]
AS = {}
for _ in range(M):
    i = int(input())
    AS[i] = 0
visited = {}

def dfs(i):
    if i == N:
        return 1
    if i > N:
        return 0
    if AS.get(i) == 0:
        return 0
    if i in visited:
        return visited[i]
    total = 0
    total += dfs(i + 1) % 1_000_000_007
    total += dfs(i + 2) % 1_000_000_007
    visited[i] = total
    return total

print(dfs(0))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
if M == 0:
    print(pat[N] % MOD)
else:
    pat = [0] * (N+1)
    pat[1] = 1
    pat[2] = 2
    for i in range(3, N+1):
        pat[i] = (pat[i-1] + pat[i-2]) % MOD
    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)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1] and i != 0 and i != m:
    ans = 0
    break
  else:
    x = a[i+1]-a[i]-1
    ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

print(ans)

Submission status: Runtime Error

Solution code:

a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        answer%=1000000007
    print(answer)

Submission status: Runtime Error

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

inf=1000000007

l=[1,1]
for i in range(n+2):
    l.append((l[i]+l[i+1])%inf)

k=[a[0]]
for i in range(m-1):
    k.append(a[i+1]-a[i]-1)
k.append(n-a[m-1])

flag=True
for i in range(1,len(k)):
   if k[i]==0:
        flag=False
ans=1

for j in range(len(k)):
    ans=(ans*l[k[j]-1])%inf

if flag:
    print(ans%inf)
else:
    print(0)

Submission status: Runtime Error

Solution code:
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()]
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)
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)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
s =[0]*(b+1)
flag = 0
p = [0]*b
goukei = 0
for i in range(b):
  p[i] = int(input())
for k in range(1,b):
  if (p[k] - p[k-1]-1) == 0:
    flag = 1
for l in range(b+1):
  if l == 0:
    s[l] = p[l] -1
  elif l == b:
    s[l] = a - p[l-1]-1
  else:
    s[l] = p[l] - p[l-1]-1
counter = 0
def fib1(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib1(n - 1) + fib1(n - 2)
if flag == 0:
  for f in range(len(s)):
    goukei += fib1(s[f])
  print(goukei%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
import math
phi = (1 + math.sqrt(5)) / 2

def counter(n):
    if n == 1:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = round(phi**(a[0]) / math.sqrt(5)) % (10**9+7)
print(ans)
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)

ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
h = []
for i in range(0,m):
  h.append(int(input()))
now = 0
s = 1
def c(i):
  if 0 <= i <= 2:
    return i
  else:
    return c(i-2) + c(i-1)

def check(h):
  if m == 1:
    return 0
  if m == 2 and h[0]+1 == h[1]:
    return -1
  for i in range(0,m-2):
    if h[i] + 1 == h[i+1]:
      return -1
  return 0

if check(h) == 0:
  for i in h:
    b = i - now - 1
    if b > 0:
      s = (s * c(b)) % 1000000007
    now = i + 1
  s = (s * c(n-now)) % 1000000007
  print(s)
else:
  print(0)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    ind = 0
    steps[0] = 1
    steps[1] = 1
    if 1 == A[ind]:
        steps[1] = 0
        ind += 1
    for i in range(2, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if i == A[ind]:
            steps[i] = 0
            if ind < M-1:
                ind += 1
    return steps[n] % 1000000007
print(step(N))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [int(input())-1 for i in range(m)]
dp = [0]*n
if n==1:
    if 0 in a:
        print(0)
        exit()
    else:
        print(1)
        exit()
if 0 in a:
    if 1 in a:
        print(0)
        exit()
    else:
        dp[0]=0
        dp[1]=1
else:
    if 1 in a:
        dp[0]=1
        dp[1]=0
    else:
        dp[0]=1
        dp[1]=2
for i in range(2,n):
    if i in a:
        continue
    if i-1 in a and i-2 in a:
        print(0)
        exit()
    x = dp[i]
    y = dp[i-1]
    z = dp[i-2]
    elif i-1 in a:
        x=z
    elif i-2 in a:
        x=y
    else:
        x= y+z
        if x>=10**9+7:
            x-=(10**9+7)
print(dp[n-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = [int(input()) for _ in range(m)]
l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

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


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


cnt = [fib(i) for i in range(1, n)]
total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True





if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+1)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
if M == 0:
    print(pat[N] % MOD)
else:
    pat = [0] * (N+1)
    pat[1] = 1
    pat[2] = 2
    for i in range(3, N+1):
        pat[i] = (pat[i-1] + pat[i-2]) % MOD
    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)

Submission status: Runtime Error

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

if n == 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

pat = (pt[-1] % 1000000007)
print(pat)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
li = [int(input()) for i in range(m)]
p = 1000000007
ans = 0

steps = [0]*(n+1)
steps[1] = 1
steps[2] = 2
for i in range(3,n+1):
  steps[i] = (steps[i-1] + steps[i-2])%p

if li[0] == 1:
  ans += 1
else:
  ans += steps[li[0]-1]%p

for i in range(m-1):
  if li[i+1] == li[i]:
    continue
  elif li[i+1] - li[i] == 1:
    ans = 0
  elif li[i+1] - li[i] == 2:
    continue
  else:
    ans *= steps[li[i+1]-li[i]-2]
    ans %= p

if li[m-1] == n-1: 
  print(ans)
else:
  print((ans*steps[n-li[m-1]-1])%p)

Submission status: Runtime Error

Solution code:
n,m  = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
    
fib = [0,1,1,2]
for i in range(n):
    x = fib[i+3] + fib[i+2]
    fib.append(x)

a2 = [a[0],n-sum(a[-1:])]
for i in range(m-1):
    a2.append(a[i+1]-a[i]-1)
a3 = []
for i in range(len(a2)):
    a3.append(fib[a2[i]])
ans = 1
for i in range(len(a3)):
    ans = ans * a3[i]
ans = ans%1000000007
print(ans)