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 math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer)

import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer % 1000000007)

import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			# print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer)

import math
print(math.factorial(5))

N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
  
answer = 0
for i in range(len(a) - 1):
  dif = a[i + 1] - a[i]
  if dif >= 4:
    b = dif // 2
    tmp_sum = 0
    for j in range(b):
      tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
    if tmp_sum != 0 and answer = 1:
      answer += 1
    answer *= tmp_sum
    
print(answer)

import math
 
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
  
answer = 0
for i in range(len(a) - 1):
  dif = a[i + 1] - a[i]
  if dif >= 4:
    b = dif // 2
    tmp_sum = 0
    for j in range(b):
      tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
    if tmp_sum != 0 and answer = 1:
      answer += 1
    answer *= tmp_sum
    
print(answer)

import math
 
N, M = list(map(int, input().split()))
a = []

for i in range(M):
  a.append(int(input()))
  
answer = 0
# a = [3]
for i in range(len(a) + 1):
	if i == 0:
		dif = a[i] - 1
	elif i == len(a):
		dif = N - a[-1] - 1
	else:
		dif = a[i] - a[i - 1] - 2
	if dif >= 2:
		b = dif // 2
		tmp_sum = 0
		for j in range(b + 1):
			tmp_sum += math.factorial(j + dif - j * 2) / (math.factorial(j) * math.factorial(dif - j * 2))
			print(tmp_sum)
		if tmp_sum != 0 and answer == 0:
			answer += 1
		answer *= tmp_sum
    
print(answer)

import math
 
N, M = list(map(int, input().split()))
stairs = [0] * (N + 1)

for i in range(M):
	stairs[int(input())] = -1

# all element of stairs
for i in range(N, -1, -1):
	# last is always 1
	if i == N:
		stairs[i] = 1
	# if stair[N - 1] is not broken 
	elif i == N - 1 and stairs[i] != -1:
		stairs[i] = stairs[i + 1]
	# if stairs[i] is not broken
	elif stairs[i] != -1:
		if stairs[i + 1] != -1:
			stairs[i] += stairs[i + 1]
		if stairs[i + 2] != -1:
			stairs[i] += stairs[i + 2]
print(int(stairs[0]) % 1000000007)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted