Problem: 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.

Submission attempts (in order):
def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()


def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2]) % mod
    print(F[N])


if __name__ == "__main__":
    main()


def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    last_broken = 0
    if not A[0] == 1:
        F[0] = 1
    if M > 1 and not A[1] == 2:
        F[1] = 1 + F[0]
    for i in range(2, N + 1):
        if last_broken < M and not i == A[last_broken]:
            F[i] = (F[i-1] + F[i-2]) % mod
        else:
            last_broken += 1
    print(F[-1])


if __name__ == '__main__':
    main()

def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    last_broken = 0
    if not A[0] == 1:
        F[0] = 1
    if M > 1 and not A[1] == 2:
        F[1] = 1 + F[0]
    for i in range(2, N + 1):
        if last_broken < M and not i == A[last_broken]:
            F[i] = (F[i-1] + F[i-2]) % mod
        else:
            last_broken += 1
    print(F[-1])


if __name__ == '__main__':
    main()

def main():
    N, M = map(int, input().split(" "))
    A = [-1]
    maximum = 0
    way = [1, 2]
    mod = 1000000007
    result = 1
    for i in range(M):
        a = int(input())
        if A[-1] + 1 == a:
            return 0
        else:
            maximum = max(maximum, a - A[-1])
            A.append(a)
    for i in range(2, maximum):
        way.append(way[i - 2] + way[i - 1])
    for j in range(1, M):
        result = result * (way[j] - way[j - 1] + 1) % mod
    return result


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

def main():
    N, M = map(int, input().split(" "))
    mod = 1000000007
    A = []
    for _ in range(M):
        A.append(int(input()))
    F = [0] * (N + 1)
    A.sort()
    last_broken = 0
    if not A[0] == 1:
        F[0] = 1
    if M > 1 and not A[1] == 2:
        F[1] = 1 + F[0]
    print(F)
    for i in range(2, N + 1):
        if last_broken < M and not i == A[last_broken]:
            F[i] = (F[i-1] + F[i-2]) % mod
        else:
            last_broken += 1
    print(F[-1])


if __name__ == '__main__':
    main()

def main():
    mod = 1000000007
    N, M, *A = map(int, open(0).read().split())
    A = set(A)
    F = [0] * (N + 1)
    F[0] = 1
    if 1 in A:
        F[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            F[i] = (F[i-1] + F[i-2])
    print(F[N] % mod)


if __name__ == "__main__":
    main()


def main():
    n, m = map(int, input().split())
    a = set([int(input()) for _ in range(m)])
    if 1 < n:
        dp = [0 for _ in range(n + 1)]
        dp[1] = 0 if 1 in a else 1
        dp[2] = 0 if 2 in a else 1
        dp[2] += dp[1]
        for i in range(3, n + 1):
            if i - 1 not in a:
                dp[i] += dp[i - 1]
            if i - 2 not in a:
                dp[i] += dp[i - 2]
        print(dp[-1] % (10 ** 9 + 7))
    else:
        print(1 if 1 not in a else 0)


if __name__ == '__main__':
    main()



Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted