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 = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
ans = 0
flag = 0
a = set[a]


dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
if flag == 0:
  ans = dp[n]
print(ans%(10**9+7))

import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m): 
    if i>=m:
  	  ans += conbination(n-2*m-1, i-m) * conbination(n-m, m)
      
print(ans%(10**9+7)) 

import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m): 
    if i>=m:
  	  ans += conbination(n-2*m-1, i-m) * conbination(n-m, m)
      
print(ans%(10**9+7)) 

import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m): 
    if i>=m
    ans += conbination(n-2*m-1, i-m) * (conbination(n-m, m) 
      
print(ans%(10**9+7)) 

import math
def conbination(x,y):
  return math.factrial(x) // (math.factrial(x-y) * math.factrial(y))

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
flag = 0
ans = 0

for i in range(n-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m-1): 
    ans += conbination(n-2*m-2, i)
      
print(ans%(10**9+7))  

def fibonacci(x, y):
  return x + y

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break

dp = [0] * 3
dp[0] = 1
dp[1] = 2
if flag == 0:
  if a[0] == 1:
    dp[0] = 1
    dp[1] = 1
for i in range(n):
  dp[2] 
	
      
print(ans%(10**9+7)) 

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
ans = 0
flag = 0
a = set(a)


dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % (10**9+7)
if flag == 0:
  ans = dp[n]
print(ans)

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted