Problem p03013 (python)

Fixed submission:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] # a_0...a_(M-1)

def f(x):
    a, b = 1, 1
    if x == 0:
        return a
    elif x == 1:
        return b
    else:
        for i in range(x-1):
            a, b = b, a + b
        return b
"""
# 再帰だとTLEとかREとかになるよ
def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    else:
        return(f(x-1) + f(x-2))
"""

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += f(N) % MOD
    print(ans)
else:
    ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    for i in range(1, M): # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break
    ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] # a_0...a_(M-1)

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) + f(x-2))

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += f(N) % MOD
    print(ans)
else:
    ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    for i in range(1, M): # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break
    ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    print(ans % MOD)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] # a_0...a_(M-1)

MOD = 10**9 + 7

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) % MOD + f(x-2) % MOD)

ans = 0

for i in range(M+1): # iは0からM
    if i == 0:
        ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    elif i == M:
        ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    else: # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break

print(ans % MOD)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)] # a_0...a_(M-1)

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) + f(x-2))

ans = 0
MOD = 10**9 + 7

for i in range(M+1): # iは0からM
    if i == 0:
        ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    elif i == M:
        ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    else: # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break

print(ans % MOD)