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 fib_memo(n):
    
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, array)
print(Ans % 1000000007)
    
    

def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
# A = range(M)
B = range(M)

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans % 1000000007)
    



  
N, M = map(int, input().split())

A = range(M)
B = range(M)

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(10)
    


def fib_memo(n):
    
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

step = [-1] * (N+1)
if 1 in A:
  step[1] = 0
  step[2] = 1
else:
  step[1] = 1
if 2 in A:
  step[2] = 0

for i in range(3, N+1):
  if i in A:
    step[i] = 0
  else:
    step[i] = step[i-1] + step[i-2]
print(step[N])
  
  

def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = [0] * M
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M - 1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M - 1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)

Ans = 10
print(Ans % 1000000007)
    


  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
# A = range(M)
B = range(M)

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans)
    


def fib_memo(n):
    
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


def fib_memo(n):
    
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


def fib_memo(n):
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    




N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M - 1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)

Ans = 10
print(Ans % 1000000007)
    


def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
# A = range(M)
B = range(M)
for i in range(M):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == (M - 1):
    diff = N - A[M - 1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    if diff == 0:
      print(0)
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans % 1000000007)
    


def fib_memo(n):
    
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    

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

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))
  
  


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted