Problem p03013 (python)

Fixed submission:
def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()

ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
print(b)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[-1]
d=[]
for i in range(m):
 a.append(int(input()))
a.append(n+1)
for i in range(m+1):
 d.append(a[i+1]-a[i]-1)
ansk=1
for i in range(m+1):
 k=int(((1+5**(1/2)/2)**d[i]-(1-5**(1/2)/2)**d[i])/(5**1/2))
 ansk*=k
print(ansk%1000000007)