Problem p03013 (python)

Fixed submission:
def main(N, M, a_list):
    div = 10**9 + 7

    a_set = set(a_list)
    
    dp = {}
    dp[0] = 1
    if 1 in a_set:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_set:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i])
    
    print(dp[N] % div)


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) % div + fib(n-2) % div
    
    
    print(fib(N) % div )




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) % div + fib(n-2) % div
    
    
    print(fib(N) % div )




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

def main(N, M, a_list):
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) + fib(n-2)
    
    div = 10**9 + 7
    print(fib(N) % int(div))




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
sys.setrecursionlimit(10**5)

def main(N, M, a_list):
    fib_memo = {}
    fib_memo[0] = 1
    fib_memo[1] = 1
    def fib(n):
        if n not in fib_memo:
            fib_memo[n] = fib(n-1) + fib(n-2)
        return fib_memo[n]

    mul = 1
    old_a = 0

    for a in a_list:
        if a != 1 and old_a == a - 1:
            print(0)
            return

        mul *= (fib(a - old_a - 1) % 1000000007)
        old_a = a
        

    mul *= (fib(N - a_list[-1] -1) % 1000000007)
    print(mul % 1000000007)




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Buggy submission (verdict: Runtime Error):
import numpy as np



def main(N, M, a_list):
    fib_memo = {}
    fib_memo[0] = 1
    fib_memo[1] = 1
    def fib(n):
        if n not in fib_memo:
            fib_memo[n] = fib(n-1) + fib(n-2)
        return fib_memo[n]

    mul = 1
    old_a = 0

    for a in a_list:
        if a != 1 and old_a == a - 1:
            print(0)
            return

        mul *= (fib(a - old_a - 1) % 1000000007)
        old_a = a
        

    mul *= (fib(N - a_list[-1] -1) % 1000000007)
    print(mul % 1000000007)




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)