Problem p03013 (python)

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

#フィボナッチ数列
def Fib(n):
    a, b = 1, 1
    if n == 0:
        return 0
    elif n== 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていた理由:
#・Fib(0)が定義されていなかったから
#・フィボナッチ数列を再帰的(=Fib(n-1)+Fib(n-2))で定義していると、
#Nが大きい(100000とか）のときに深く潜りすぎるのでRE

if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていたのはFib(0)が定義されていなかったから
if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていたのはFib(0)が定義されていなかったから
if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り



ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り



ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)