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 = []


from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)




ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    N,M = map(int,input().split())
A = []


from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)






ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  

N,M = map(int,input().split())
A = []


def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)









if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): 
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)  

N,M = map(int,input().split())
A = []


def Fib(n):
    a, b = 1, 1
    if n == 0:
        return 0
    elif n== 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)









if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): 
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)  

Verdicts: Runtime Error

Wrong Answer

Accepted