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):
def main(A, dp, n, mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)

def mul(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(0, 2*(c + 1), 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS

def mul_odd(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(1, 2*c + 3, 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS

N, M = map(int, input().split())
D = 0
A = [0]
ans = []
aans = 1
for i in range(M + 1):
  if i != M :
  	A.append(int(input()))
  else: 
    A.append(N + 1)
  diff = A[i + 1] - A[i]
  if (diff == 1) & (i != 0):
    print(0)
    D = 1
    break
  
  temp = diff -1
  if (temp) % 2 == 0:
    aans *= mul(temp//2)
  else:
    aans *= mul_odd(temp//2)
if D == 0:   
	print(aans)

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = [int(input()) for _ in range(M)] 
dp[-1] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])



def main(A, dp, n mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)


def mul(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(0, 2*(c + 1), 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
def mul_odd(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(1, 2*c + 3, 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
N, M = map(int, input().split())
D = 0
A = [0]
ans = []
aans = 1
for i in range(M + 1):
  if i != M :
  	A.append(int(input()))
  else: 
    A.append(N + 1)
  diff = A[i + 1] - A[i]
  if (diff == 1) & (i != 0):
    print(0)
    D = 1
    break
  
  temp = diff -1
  if (temp) % 2 == 0:
    aans *= mul(temp//2)
  else:
    aans *= mul_odd(temp//2)
if D == 0:   
	print(aans % 1000000007)

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * N
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

for i in range(N-2, -1, -1):
    if (i in A) == False:
        dp[i] = dp[i + 1] + dp[i + 2] 

print(dp[0] % mod)




N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])

Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Accepted