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):
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width) % 1000000007
    print(width,tmp)
    cnt *= tmp

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N,M = [int(i) for i in input().split()]
A = [0]
for _ in range(M):
    A.append(int(input()))
A.append(N)
ans = 1
for n in range(len(A)):
    if n ==0:
        pass
    else:
        div = (A[n]-A[n-1]-1) // 2
        mod = (A[n]-A[n-1]-1) % 2
        div_mod = div+mod
        comb = 0
        for _ in range(div):
            print(div_mod,div)
            comb += combinations_count(div_mod,div)
            div_mod += 1
            div -=1
            if div == 0:
                div = 1
                div_mod = 1
        comb += combinations_count(div_mod,div)
        print(comb)
        ans = ans * comb

N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width)%1000000007
    cnt = (tmp*cnt)%1000000007
print(cnt)

N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width) % 1000000007
    cnt *= tmp
print(cnt)

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N,M = [int(i) for i in input().split()]
A = [0]
for _ in range(M):
    A.append(int(input()))
A.append(N)
ans = 1
for n in range(len(A)):
    if n ==0:
        pass
    else:
        div = (A[n]-A[n-1]-1) // 2
        mod = (A[n]-A[n-1]-1) % 2
        div_mod = div+mod
        comb = 0
        for _ in range(div):
            comb += combinations_count(div_mod,div)
            div_mod += 1
            div -=1
            if div == 0:
                div = 1
                div_mod = 1
        comb += combinations_count(div_mod,div)
        print(comb)
        ans = (ans * comb) % 1000000007
print(ans)

N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
def fibo(n):
    if n <= 2:
        return n
    return fibo(n-1) + fibo(n-2)
cnt = 1
for a in range(len(A)+1):
    if a == 0:
        if A[a] == 1:
            width = 1
        else:
            width = A[a]-2
    elif a > 0 and a < M:
        width = A[a] - A[a-1] - 2
    elif a == (M):
        width = N-A[a-1]-1
    if width < 0:
        tmp = 0
        cnt = 0
        break
    else:
        tmp = fibo(width)
    cnt = (tmp*cnt)%1000000007
print(cnt)

mod = 1000000007
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
steps = [0]*N
for a in A:
    steps[a-1] = 1
cnt = []
for n in range(N):
    if n == 0:
        if steps[n]==0:
            cnt.append(1)
        elif steps[n]==1:
            cnt.append(0)
    elif n == 1:
        if steps[n]==0:
            cnt.append(cnt[n-1]+1)
        elif steps[n]==1:
            cnt.append(0)
    elif steps[n] == 0:
        cnt.append((cnt[n-2]+cnt[n-1])%mod)
    elif steps[n] == 1:
        cnt.append(0)
print(cnt[-1])

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Accepted