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:
import math
n,m = map(int,input().split())
before = -1
alls = 1
for i in range(m):
        a = int(input())
        b = (a - before - 2) // 2
        c = a - before - 2
        ptr = 0
        for j in range(b + 1):
                ptr += math.factorial(c - j) / (math.factorial(j) * math.factorial(c - 2 * j))
        alls = alls * ptr
        before = a
ptr = 0
b = (n - a - 1) // 2
c = n - a - 1
for j in range(b + 1):
        ptr += math.factorial(c - j) / (math.factorial(j) * math.factorial(c - 2 * j))
alls = alls * ptr
print(int(alls % 1000000007))

Submission status: Runtime Error

Solution code:
import numpy as np


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

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

sq = []
for k in range(M+1):
    if k == 0:
        sq.append(a[k])
    
    elif k == M:
        sq.append(N-a[k-1])

    elif a[k] == a[k-1] +1:
        sq.append(0)
    
    else:
        sq.append(a[k] - a[k-1]-1)

ans = 1
for p in sq:
    if p == 0:
        ans *= 0
    else:
        q = int((1/np.sqrt(5))*  ( (((1+np.sqrt(5))/2)**p) -  (((1-np.sqrt(5))/2)**p)  ))%1000000007
        ans *= q
        


print(int(ans)%(1000000007))

Submission status: Runtime Error

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

def dd(n):
    if ms[n-1]>0:
        return ms[n-1]
    if n==1:
        ms[n-1]=1
        return 1
    if n==2:
        ms[n-1]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n-1]=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

ans=(ans%mod)*(dd(n-al[-1]-1)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
def fib_memo(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) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

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

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

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib(diff-1)
    sum %= 1000000007
    a_p = a

sum *= fib(N - a_p)

print(sum % 1000000007)

Submission status: Runtime Error

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

for i in a:
    res_arr[i] = 0

for i in range(1, n):
    if res_arr[i] == 0:
        next
    elif i == 1:
        res_arr[i] = 1
    elif i == 2:
        res_arr[i] = 1 + res_arr[i-1]
    else:
        res_arr[i] = res_arr[i-1] + res_arr[i-2]

res = res_arr[-1]+res_arr[-2]
if n == 1:
    res = res_arr[1]
elif n == 2:
    res = 1 + res_arr[1]
amari = res % 1000000007
print(amari)

Submission status: Runtime Error

Solution code:

target=0
o_list=[1,2]
n=0
t_list=[]
try:
    input1=[int(n) for n in input().split(' ')]
    target=input1[0]
    n=input1[1]
    for x range(n):
        t_list.append(int(x))
except:
  print('age,price must be numbers')
  sys.exit(1)

min_v = 10000
is_found = True
is_less = True
path=[0]
success = 0
d=1000000007
while(is_found or is_less):
    path_new=[]
    is_found=False
    is_less= False
    for i in o_list:
        for pre in path:
            new_n = i + pre
#             print(new_n)
            if not(new_n in t_list):
                if new_n < target:
                    is_less= True
                    path_new.append(new_n)
                if new_n == target:
                    success+=1
                    is_found=True
    if not is_found:
        path=[0]
    path = path_new
#     print(is_less)
#     print(is_found)
#     print("success")
#     print(success)
# print(success)
q, mod = divmod(success, d)
print(mod)

Submission status: Runtime Error

Solution code:
import math
import functools
import operator
N,M= list(map(int,input().split()))
a = []
for i in range(M):
    an = int(input())
    a.append(an)
#print(a)

#実質的に歩く階段の数
toS=N-M
check = 0
#連番の場合存在しない
for i in range(M-1):
    if a[i+1] == a[i]+1:
        check = 1
        print(0)

#間の階段の数
dela = [a[0]]
for i in range(M-1):
    delan = a[i+1]-a[i]
    dela.append(delan)
dela.append(N-a[M-1])
#print(dela)


number = 0
#2の個数を選ぶ(dela[i]=4なら(1,1,2),(1,2,1),(2,1,1),(2,2)の組み合わせ
kumiawase = []
for i in range(len(dela)):
    if dela[i] >=3:
        for j in range(dela[i]//2):
            twonum = j+1 #2の個数
            rownum= dela[i]- twonum
#            print("twonum,rownum,j=",twonum,rownum,j,dela[i])
            number = number + (math.factorial(rownum))/(math.factorial(twonum))
        kumiawase.append(number)
        number = 0
#print(kumiawase)
result = functools.reduce(operator.mul,kumiawase)        
if check ==0:
    print(int(result)%1000000007)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

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

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-2):
    li.append(li[i] + li[i+1])
ans = 1
for i in range(len(ai) - 1):
    if ai[i+1] - ai[i] == 1:
        ans = 0
    else:
        ans *= li[(ai[i+1] - ai[i]) - 2]
        ans = ans % mm
print(ans)

Submission status: Runtime Error

Solution code:
N_M = [int(e) for e in input().split()]
div = 1000000007
a=[]
flag=1
for i in range(N_M[1]):
  a.append(int(input()))
  if(i>=1 and a[i]=a[i-1]+1):
    print(0)
    flag=0

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

if(flag==1){
	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]
	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(' '))

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

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib(diff-1)
    a_p = a

sum *= fib(N - a_p)

print(sum % 1000000007)

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
  elif((a[i] + 1) == (a[i+1] - 1)):
    ans *= 1
  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:
N, M = map(int,input().split())
List = [int(input()) for i in range(M)]

import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i) 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
a_list = []
for i in range(m):
    a_i = int(input())
    a_list.append(a_i)
    a_list = list(set(a_list))
#print(n, m, a_list)
#print(a_list)
m = len(a_list)
flag = 0

def stepup(x):
    #x段
    ans = 0
    for i in range(x):
        if i==0:
            two_before=1
            ans=1
        elif i==1:
            one_before=2
            ans=2
        else:
            #print(two_before, one_before)
            ans = one_before+two_before
            two_before = one_before
            one_before = ans
    return(ans)
        
a_list.sort()
#print(stepup(5))
#print(a_list)
for i in range(m):
    if i==0:
        if a_list[i]==1:
            count = 1
            continue
        else:
            count = stepup(a_list[0]-1)
    else:
        if a_list[i]-a_list[i-1]==1:
            #print(a_list[i], a_list[i-1])
            flag = 1
            break
        else:
            #print(stepup(23))
            #print(i, stepup(a_list[i]-a_list[i-1]))
            count *= stepup(a_list[i]-a_list[i-1]-2)
    #print(count)
if n-a_list[i]==1:
    pass
else:
    count *= stepup(n-a_list[i]-1)
#print(count)

if flag==1:
    print(0)
else:
    print(count%1000000007)
#print((stepup(20)**4 * stepup(10))%1000000007)

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

if m == 0:
    x = a[m+1]-a[i]-1
    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:
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 m == 0:
  print(steps[n])
else:
  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:
def rec(n,me,stair):
    if me[n-1]!=0:
        return me[n-1]
    elif n in stair:
        return 0
    elif n==1:
        if n-1 in stair:
            me[n-1]=0
            return 0
        me[n-1]=1
        return 1
    elif n==2:
        test1=n-1 in stair
        test2=n-2 in stair
        if test1 and test2:
            me[n-1]=0
            return 0
        elif test1 or test2:
            me[n-1]=1
            return 1
        me[n-2]=2
        return 2
    else:
        ans=rec(n-2,me,stair)+rec(n-1,me,stair)
        me[n-1]=ans
        return ans

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
memo=[0]*(n+1)
print(rec(n,memo,a)%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
def f(a):
  return round(((((1+5**0.5)/2)**a)-(((1-5**0.5)/2)**a))/5**0.5)
s = 1
a1 = -1
a2 = -1
for i in range(m):
  a2 = int(input())
  if a2 == a1:
    continue
  a = a2-a1-1
  if a <= 1 and a1 > 0:
    s = 0
    break
  s = s * f(a)
  if s >= 1000000007:
    s = s % 1000000007
  a1 = a2
if s > 0:
  a = n - a2
  s = s * f(a)
  if s >= 1000000007:
    s = s % 1000000007
print(s)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]
mod=1000000007
ms=[0]*n

def dd(n):
    if ms[n-1]>0:
        return ms[n-1]
    if n==1:
        ms[n-1]=1
        return 1
    if n==2:
        ms[n-1]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n-1]=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

ans=(ans%mod)*(dd(n-al[-1]-1)%mod)%mod
print(ans)

Submission status: Runtime Error

Solution code:
cache = {1: long(1), 2: long(2)}


def calc(_n):
    if _n in cache:
        return cache[_n]
    else:
        x = long(calc(_n - 1) + calc(_n - 2))
        cache[_n] = x
        return x


N, M = map(int, raw_input().split())
prev_a = long(-1)
ans = long(1)
for i in range(0, M):
    a = long(input())
    if a == 1:
        prev_a = 1
    elif prev_a + 1 == a:
        ans = 0
        break
    else:
        ans = ans * calc(a - prev_a - 2)
        prev_a = a

if ans == 0:
    print(ans)
else:
    if prev_a + 1 == N:
        ans = ans
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

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,10))
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:
import pysnooper

@pysnooper.snoop()
def rec(n,me,stair):
    if me[n-1]!=0:
        return me[n-1]
    elif n in stair:
        return 0
    elif n==1:
        if n-1 in stair:
            me[n-1]=0
            return 0
        me[n-1]=1
        return 1
    elif n==2:
        test1=n-1 in stair
        test2=n-2 in stair
        if test1 and test2:
            me[n-1]=0
            return 0
        elif test1 or test2:
            me[n-1]=1
            return 1
        me[n-2]=2
        return 2
    else:
        ans=rec(n-2,me,stair)+rec(n-1,me,stair)
        me[n-1]=ans
        return ans

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
memo=[0]*(n+1)
print(rec(n,memo,a)%1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 1000000007

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % 1000000007)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans *= c[num - 1]
        if ans >= BIGNUM:
            ans = ans % BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Runtime Error

Solution code:
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)
#print(a)

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

else:
    dp = [0]*100000
    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]

    #print(ans)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
    return memo[k]

print(stair(n))

Submission status: Runtime Error

Solution code:
def solve(n):
  if n <= 1:
    ans = 1
  elif n == 2:
    ans = 2
  else:
    ans = solve(n-1) + solve(n-2)
  return ans

n,m=map(int, input().split())
a=[0]
ans = 1
for i in range(0,m):
  a = a+[int(input())]
  if a[i+1] - a[i] == 1 and i > 1:
    ans = 0
a = a + [n+1]

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

for i in range(0,m+1):
  if a[i+1] - a[i] != 1:
    ans = (ans * memo[a[i+1] - a[i] - 2]) % 1000000007
print(ans)

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
        if ind < M-1:
            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 = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
if m == 0:
    x = a[m+1]-a[i]-1
    ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007  
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:
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
        
N,M = list(map(int,input().split()))
ans = 1
z = False

if M != 0:
    a = [int(input()) for _ in range(M)]
else:
   ans *= fib(N)
   print(ans) 







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

Submission status: Runtime Error

Solution code:
class Solution(object):
	def __init__(self):
		self.ans = 0
	def search(self, pos, dest):
		if(pos > dest):
			return
		if(pos == dest):
			self.ans += 1
			return
		self.search(pos+1, dest)
		self.search(pos+2, dest)

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

prev = 0

for i in range(M):
	curr = int(input())
	A.append(curr)
	#prev = curr

A.append(N+1)

#print(A)

ans = 1

prev = 0
for i in range(len(A)):
	s = Solution()
	if(i == 0):
		prev = 0
	else:
		prev = A[i-1] + 1
	#print(prev)
	s.search(prev,A[i]-1)
	con = s.ans
	#print(con)
	ans *= con

print(ans % 1000000007)

Submission status: Runtime Error

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

# 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())  #複数数値入力

import sys

sys.setrecursionlimit(10**5)

if m == 0:
    print(countWays_memo(n))
else:
    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 = [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)

Submission status: Runtime Error

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

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

def get_count(num):
	count = 0
	for i in range(num // 2 + 1):
		count += c_count(num - i, i)
	return count

num = a[0]
ans = get_count(num - 1)

if M > 1:
	for i in range(1, M):
		if a[i] == a[i-1] + 1:
			print(0)
			sys.exit()
		ans *= get_count(a[i] - a[i-1] - 2)
ans *= get_count(N - a[-1] -1)
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
#C問題
N, M = map(int, input().split())
lack = []
for _ in range(M):
    lack.append(int(input()))

def fib(n):
    if n in lack:
        return 0
    elif (n == 0) or (n == 1):
        return 1
    else:
        return fib(n-1) + fib(n-2)

print(fib(N) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

def dfs(heights: int, a_index:int):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[heights] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[heights] = memo[heights-1] + memo[heights -2]
        #print("13",heights)
    dfs(heights+1,a_index)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(n+1)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            #print(i,a)

    if a[0] == 1:
        memo[1] = 0
        a_index += 1
a = list(set(a))
a.sort()
dfs(2,a_index)
#print(memo)
print(memo[n] % (10**9+7))

Submission status: Runtime Error

Solution code:
def fibo(x):
    if x>0:
        ll=[0]*x
        ll[0]=1
        if x>1:
            ll[1]=2
            if x>2:
                for y in range(x-2):
                    ll[y+2]=ll[y+1]+ll[y]
        return(ll[x-1])

    else:
        return(0)

N,M=(int(x) for x in input().split())
a=[]
for x in range(M):
    aa=int(input())
    a.append(aa)
ans=[0]*(M+1)
sa=a[0]-1
if sa>0:
    ans[0]=fibo(sa)
else:
    ans[0]=1
for x in range(M-1):
    sa=a[x+1]-a[x]-1
    ans[x+1]=fibo(sa)
saa=N-a[M-1]-1
ans[M]=fibo(saa)

kotae=ans[0]%1000000007
for x in range(M):
    kotae=kotae*int(ans[x+1])%1000000007
print(kotae%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fibmemo={1:1,2:1}
def fib(n):
    if n in fibmemo:
        return fibmemo[n]
    k=fib(n-2)+fib(n-1)
    fibmemo[n]=k
    return k

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
m=fib(a[0])
tmp=a[0]
for i in a:
    if i+1 in a:
        print(0)
        sys.exit()
    if a[0]==i:
        continue
    m=fib(i-tmp-1)*m%mod
    tmp=i
m=fib(n-tmp)*m%mod
print(m)

Submission status: Runtime Error

Solution code:
import numpy as np


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

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

sq = []
for k in range(M+1):
    if k == 0:
        sq.append(a[k])
    
    elif k == M:
        sq.append(N-a[k-1])

    elif a[k] == a[k-1] +1:
        sq.append(0)
    
    else:
        sq.append(a[k] - a[k-1]-1)

ans = 1
for p in sq:
    if p == 0:
        ans *= 0
    else:
        q = int((1/np.sqrt(5))*  ( ((1+np.sqrt(5))/2)**p -  ((1-np.sqrt(5))/2)**p  ))%1000000007
        ans *= q
        


print(int(ans)%(1000000007))

Submission status: Runtime Error

Solution code:
import pysnooper

@pysnooper.snoop()
def rec(n,me,stair):
    if me[n-1]!=0:
        return me[n-1]
    elif n in stair:
        return 0
    elif n==1:
        if n-1 in a:
            me[n-1]=0
            return 0
        me[n-1]=1
        return 1
    elif n==2:
        test1=n-1 in a
        test2=n-2 in a
        if test1 and test2:
            me[n-1]=0
            return 0
        elif test1 or test2:
            me[n-1]=1
            return 1
        me[n-2]=2
        return 2
    else:
        ans=rec(n-2,me,stair)+rec(n-1,me,stair)
        me[n-1]=ans
        return ans

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
memo=[0]*(n+1)
print(rec(n,memo,a)%1000000007)

Submission status: Runtime Error

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

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

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp2 = 1
        for j in range(i):
            tmp2 *= n - j
        for j in range(i):
            tmp2 /= j + 1
        tmp += tmp2

    return tmp

routes = 1
prev = 0
for x in a:
    if x - prev == 0:
        routes = 0
        break
    else:
        x -= 1
        dan = x - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+2

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

Submission status: Runtime Error

Solution code:
"""
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

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)

Submission status: Runtime Error

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


def count_steps(NN):
    NN -= 1
    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 a[0] == 1:
    ans = 1
else:
    ans = count_steps(a[0])

for i in range(1, len(a)):
    ans *= count_steps(a[i]-a[i-1]-1)
ans *= count_steps(n-a[-1])
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = []

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


def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)


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

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

print(np.prod(a2) % 1000000007)