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):
import sys

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    # We can
    memo = [0] * (N + 1)
    print("?")
    sys.exit()

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())


import sys

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True

print("")
sys.exit()

def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    return 1

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())


from more_itertools import windowed

print("")

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    temp = A[0]
    for a in A[1:]:
        if a - 1 == temp:
            return 0
        temp = a

    return 1

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())


N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a
    return 0

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())


N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 1)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        return 0
        if memo[i] == 0:
            count1 = rec(i - 1) % 1000000007
            count2 = rec(i - 2) % 1000000007
            memo[i] = (count1 + count2) % 1000000007
            # print(f"memo[{i}] = {count1} + {count2} -> {memo[i]}")
        return memo[i]
    return rec(N)


print(solve())


import sys
sys.setrecursionlimit(10 ** 7)

N, M = [int(_) for _ in input().split()]
A = [int(input()) for i in range(M)]
isBroken = [False] * (N + 1)
for i in A:
    isBroken[i] = True


def solve():

    # It's impossible
    if M >= 1:
        temp = A[0]
        for a in A[1:]:
            if a - 1 == temp:
                return 0
            temp = a

    # We can
    memo = [0] * (N + 2)

    def rec(i):
        if i == 0:
            return 1
        if i < 0:
            return 0
        if isBroken[i]:
            return 0

        if memo[i] == 0:
            count1 = rec(i - 1)
            count2 = rec(i - 2)
            memo[i] = (count1 + count2) % 1000000007
        return memo[i]
    return rec(N)


print(solve())


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Accepted