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):
print(1)

NM = [int(i) for i in input().split()]
a = [0] * NM[0]
for _ in range(NM[1]):
    a[int(input) - 1] = -1

for i in range(NM[0]):
    if (i == 0):
        if(a[i] != -1):
            a[i] = 1
        else:
            a[i] = 0
    elif(i == 1):
        if(a[i] != -1):
            a[i] = a[i - 1] + 1
        else:
            a[i] = 0
    else:
        if(a[i] != -1):
            a[i] = a[i-1] + a[i - 2]
        else:
            a[i] = 0

print(a[N-1] % (10**9 + 7))

import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10**9 + 7)
print(0)


import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0 and a[i] - 1 != 0):
        b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1 and NM[0] - a[i] - 1 != 0):
        b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)


import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)


import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        b.append(a[i] - 1)
    else:
        b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)


NM = [int(i) for i in input().split()]
a = [0] * NM[0]
for _ in range(NM[1]):
    a[int(input()) - 1] = -1

for i in range(NM[0]):
    if (i == 0):
        if(a[i] != -1):
            a[i] = 1
        else:
            a[i] = 0
    elif(i == 1):
        if(a[i] != -1):
            a[i] = a[i - 1] + 1
        else:
            a[i] = 0
    else:
        if(a[i] != -1):
            a[i] = a[i-1] + a[i - 2]
        else:
            a[i] = 0

print(a[NM[0]-1] % (10**9 + 7))

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted