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:
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
if 1 not in broken:
    memo[1] = 1
else:
    memo[1] = 0
if 2 not in broken:
    if 1 not in broken:
        memo[2] = 2
    else:
        memo[2] = 1
else:
    memo[2] = 0
for i in range(3, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1])

print(memo[N] % INF)

Submission status: Runtime Error

Solution code:
law = 10 ** 9 + 7

def fibo(N):
    if (N <= 1):
        return N

    return 2 ** (N - 3) + 1

def main():
    N, M = map(int, input().split())

    ans = 1
    b = -1
    for _ in range(M):
        a = int(input())

        if (a > 1):
            ans = (ans * fibo(a - b - 1)) % law
        b = a

    if (a < N - 1):
        ans = (ans * fibo(N + 1 - b - 1)) % law

    return ans


if __name__ == "__main__":
    print(main())

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

dfs(2,a_index)
#print(memo)
print(memo[n] % (10**9+7))

Submission status: Runtime Error

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

n, m = map(int, raw_input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(raw_input()))
for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    # a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    # a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print(true_ans)

Submission status: Runtime Error

Solution code:
fib=[0,1]
for i in range(9999):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[-1]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
for i in range(len(hoge)-1):
  sa=hoge[i+1]-hoge[i]-1
  ans=ans*fib[sa]
  ans=ans%1000000007
print(ans)

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)


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,i-preidx-1])
    elif idx > 0:
        ans.append([idx,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)

Submission status: Runtime Error

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


def stairs(n):
    global pattern
    if n < N:
        if n + 1 not in a:
            if n + 1 == N:
                pattern += 1
            else:
                stairs(n + 1)
        if n + 2 not in a:
            if n + 2 == N:
                pattern += 1
            elif n >= N:
                pass
            else:
                stairs(n + 2)


stairs(0)
pattern = pattern % 1000000007
print(pattern)

Submission status: Runtime Error

Solution code:
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input()) - 1] = 0

    # print(n, m)
    # print(a)
    # ans = step(a, 0)

    f = [0] * n
    if a[0] == 0:
        f[0] = 0
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 1
    else:
        a[0] = 1
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 2

    if a[1] == 0:
        f[1] = 0

    # print(f)
    for i in range(2, n):
        # print(i)
        if a[i]:
            f[i] = (f[i-1] % LARGE) + (f[i-2] % LARGE)
    # print(f)
    print(f[n-1])


if __name__ == '__main__':
    solve()

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
      elif a[i+1]-a[i] == 0:
        b[i+1] = 1
      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:

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  ))
        ans *= q
        ans = ans%1000000007


print(int(ans)%(1000000007))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = 0
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]-2
    if x == 0 or x == 1:
      ans = ans%1000000007
    elif x == 2:
      ans = ans*2%1000000007
    else:
      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:
mod = 1000000007

def feb(n):
    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:
import itertools

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

mlist = [int(input()) for i in range(m)]

past = -10
minus = 0

for i in mlist:
    if i == past+1 :
        print(0)
        quit()
    past = i

    if i ==1:
        minus += 1
    if i == n-1:
        miunus += 1

nopattern = len(mlist)*3 + minus
fig = n - nopattern

figlist=[]
for i in range(fig-1):
    figlist.append(i+1)

ans = 0

for i in range(fig-1):
    ans += (len(list(itertools.permutations(figlist, i+1))))

print(ans % 1000000007)

#    print(list(itertools.permutations(figlist, i+1)))

Submission status: Runtime Error

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

mod = 10 ** 9 + 7


def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n] % mod
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n] % mod


A = list(int(input()) for i in range(m))


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

Submission status: Runtime Error

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

for i in range(1, n):
    if i in a:
        res_arr[i] = 0
    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]
amari = res % 1000000007
print(amari)

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

    for j in range(abletwo + 1):

        now += cmb (dan - j , j )
        
    ans *= now
    

ans = ans % 1000000007
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 = []

pt = [1]
if a[0] == 1:
  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())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 1
checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

for i in range(2, n):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

n, m = map(int, raw_input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(raw_input()))
for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    # a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    # a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print(true_ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(int(input()) for _ in range(M) )
ans=0
ansn1=0
ansn2=0
mod=1000000007
A=a[0]
for i in range(N):

    if i>=2 and  i+1 < A:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans
        continue
    elif i>=2 and  i+1 > A:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans
        if a.index(A)+1<M-1:
            A=a[a.index(A)+1]
        else:
            A=mod
        continue

    elif i+1 == a:
        ans = 0
        ansn2 = ansn1
        ansn1 = ans
        if a.index(A) + 1 < M - 1:
            A = a[a.index(A) + 1]
        else:
            A=mod
        continue


    if i==0:
        if i+1 not in a:
            ans=1
            ansn2 = 0
            ansn1=ans

    elif i==1:
        if i+1 not in a:
            ans=1+ansn1
            ansn2 = ansn1
            ansn1=ans
        else:
            ans=0
            ansn2=ansn1
            ansn1=ans


print(ans)

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:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    maxdif = 0
    a = []
    for _ in range(m):
        a.append(im.inputSingle())
        if len(a) >= 2:
            maxdif = max(maxdif, a[-1] - a[len(a)-2])
    MOD = 1000000007
    # Logic ############################################################################################################
    idx = 0
    total = 1
    fib = fibonacci(maxdif + 2)
    for ai in a:
        if idx - 1 == ai and idx != 0:
            print()
            continue
        if (ai - idx) == 0 and idx != 0:
            print(0)
            return
        total *= fib[ai - idx - 1]
        idx = ai+1
    total *= fib[n - idx]
    # Output ###########################################################################################################
    print(total % MOD)
    # Return ###########################################################################################################
    return

def fibonacci(n):
    fib = [1, 1]
    for _ in range(n - 1):
        fn_1 = fib[len(fib)-1]
        fn_2 = fib[len(fib) - 2]
        fib.append(fn_2 + fn_1)
    return fib

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def culcC(num):
    if num  < 2:
        return 1
    ret = 1
    minus2 = 1
    while(True):
#         ret += int(comb(num - minus2,minus2 if minus2 >0 else 1,exact=True))
        ret += cmb(num - minus2,minus2 if minus2 >0 else 1)
        minus2 += 1
        if num - 2 * minus2 < 0:
            break
    return ret
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):
        
#        連続穴
        if stand == a:
            ans = 0
            break
            
        step_num = a - stand - 1
        ans *= culcC(step_num)
        stand = a + 1
#         print(step_num,ans,stand)
        
    # 最後のaからnまでで計算
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
cache = {1: 1, 2: 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 = 0
    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())
a = [int(input()) for _ in range(M)]

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

ans = 0
if a[0] == 1 :
    ans = 1
else :
    ans = sumList[a[0] - 1]
for i in range(1, M) :
    if a[i] - a[i-1] != 0 :
        if a[i] - a[i-1] == 1 :
            ans = 0
        else :
            ans *= sumList[a[i] - 2 - a[i-1]]
if N - a[M-1] != 1 :
    ans *= sumList[N - 1 - a[M-1]]
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

n, m = map(int, raw_input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(raw_input()))
for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    # a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    # a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print("true_ans")

print(true_ans)

Submission status: Runtime Error

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

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:
n,m=map(int,input().split())
a=[]
for _ in range(m):
   a.append(input())

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

sum=fb(int(a[0]))

for i in range(m-1):
    sum=sum*fb(int(a[i+1])-int(a[i])-1)

sum=sum*fb(n-int(a[m-1]))

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

Submission status: Runtime Error

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

step = [0]*100000
step[0] =1
step[1] =1
step[2] =2
for i in range(3,100000):
    step[i] = step[i-1] + step[i-2]

l = [a[0]-1]
for i in range(1,m):
    l.append(a[i]-a[i-1]-2)
l.append(n-a[m-1]-1)

ans = 1

for i in range(m+1):
    if step[l[i]] < 0:
        ans = 0
        break
    ans = ans*step[l[i]]
    if ans >= INF:
        ans = ans % INF

print(ans)

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)


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,i-preidx-1])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,N-preidx-1])

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
if 1 not in broken:
    memo[1] = 1
else:
    memo[1] = 0
if 2 not in broken:
    if 1 not in broken:
        memo[2] = 2
    else:
        memo[2] = 1
else:
    memo[2] = 0
for i in range(3, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
import sympy as sym

def Fib(n):
	x = sym.symbols('x',nonnegative=True,integer=True)
	Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
	result=Fib.subs(x,n)
	result=result.evalf(int(n*3/14)+1)
	return int(result)


"""
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
print("Ok")
print(Fib(100000))
"""
ans = 1
for i in range(M+1):
	if i == 0:
		ans = (ans*(Fib(a[0]-(-1))%dekai))%dekai
	elif i == M:
		ans = (ans*(Fib(N+1-a[M-1])%dekai))%dekai
	else:
		ans = (ans*(Fib(a[i]-a[i-1])%dekai))%dekai
print(ans)

Submission status: Runtime Error

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

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1

if A[0]==1:
    j=1
    flag=True
else:
    j=0
    flag=False
for x in range(2, N + 1):
    if x==A[j]:
        case[x] = 0
        j=(j+1)%M
        flag=True
    elif flag==True:
        case[x] = case[x - 2]
        flag=False
    else:
        case[x] = case[x - 1] + case[x - 2]
        flag=False

print(case[N] % 1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
def nibutan(x,l):
    low=0
    high=len(l)-1
    while low<=high:
      mid=(low+high)//2
      guess=l[mid]
      if guess==x:
         return True
      elif guess>x:
          high=mid-1
      elif guess<x:
          low=mid+1
    return False
for i in range(m):
  l.append(int(input()))
l1=[0 for i in range(n)]
if 1 in l:
  l1[0]=0
else:
  l1[0]=1
if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n>=3:
  for i in range(3,n+1): 
    if nibutan(i,l):
      pass
    else:
      l1[i-1]=(l1[i-2]+l1[i-3])%(((10**9)+7))
print(l1[n-1])

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()
        ans *= Fib(s[i]-s[i-1]-1)
if s[-1] != n:
    ans *= Fib(n-s[-1])
    
        
print(ans%1000000007)

Submission status: Runtime Error

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

a.sort()
A = [0]*(N+1)
A[0] = 1

flag = True
for i in range(1, N+1):
  if flag and i == a[0]:
    A[i] = 0
    a.remove(i)
    if len(a)==0: flag = False
  else:
    if i==1: A[i] = 1
    else:
      A[i] = (A[i-1] + A[i-2])%div

print(A[N])

Submission status: Runtime Error

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

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

print(dp[n])