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):
from math import factorial

def cases(idx_start, idx_end):
  cases = 0
  for r in range((idx_end - idx_start)//2+1):
    n = idx_end - idx_start - r
    cases += factorial(n) / factorial(r) / factorial(n - r)
  return cases

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

ans = cases(1,alist[0])
for i in range(1,m):
  if alist[i] - alist[i-1] <= 1:
    print(0)
    exit()
  ans *= cases(alist[i-1]+1, alist[i])
ans *= cases(alist[-1]+1, n+1)
print(int(ans%div_num))

n, m  = map(int, input().split())

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for index in range(n-1)[::-1]:
  i = index + 1
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

n, m  = map(int, input().split())

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for index in range(n-2)[::-1]:
  i = index + 1
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

from math import factorial

def cases(idx_start, idx_end):
  cases = 0
  for r in range((idx_end - idx_start)//2+1):
    n = idx_end - idx_start - r
    cases += factorial(n) / factorial(r) / factorial(n - r)
  return cases

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

if m == 0:
  print(cases(1,n+1)%div_num)
  exit()

ans = cases(1,alist[0])
for i in range(1,m):
  if alist[i] - alist[i-1] <= 1:
    print(0)
    exit()
  ans *= cases(alist[i-1]+1, alist[i])
ans *= cases(alist[-1]+1, n+1)
print(int(ans%div_num))

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

f = [1, 1]
for i in range(n-1)[::-1]:
  flag1 = True if i+1 not in alist else False
  flag2 = True if i+2 not in alist else False
  if flag1 is False and flag2 is False:
    print(0)
    exit()
  elif falg1 is False and flag2 is True:
    f = [f[1]] + [f[0]]
  elif flag1 is True and flag2 is False:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

n, m  = map(int, input().split())

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-1)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
A = [True for _ in range(N+1)]
for _ in range(M):
    A[int(input())] = False

dp = [1 for _ in range(N + 1)]
for i in range(1, N+1):
    if A[i] == True:
        if i - 2 >= 0:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
        else:
            dp[i] = (dp[i - 1]) % MOD
    else:
        dp[i] = 0
print(dp[-1] % MOD)

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted