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())
if m>=2:
    lists=[]
    for i in range(m):
        a=int(input())
        lists.append(a)

    fiblist=[1,1]
    for j in range(10**5):
        nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
        fiblist.append(nums)
    lists.insert(0,0)
    lists.append(n)
    ans=1
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fib(n))
if m==1:
    print(fib(lists[0]-1)*fib(n-lists[0]-1)%(10**9+7))

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

lists=[]
for i in range(m):
    a=int(input())
    lists.append(a)

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
if m>=2:
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fib(n))
if m==1:
    print(fib(lists[1]-1)*fib(n-lists[1]-1)%(10**9+7))

n,m=map(int,input().split())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)
print(use)
if N>=2:        
    lists=[1,2]

    for i in range(n-2):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1:
            ans=0
            break
        else:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
            
            
    print(ans)
elif N==1:
    print(1)


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

if N>=2:        
    lists=[1,2]

    for i in range(n-2):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1:
            ans=0
            break
        else:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
            
            
    print(ans)
elif N==1:
    print(1)

n,m=map(int,input().split())
use=[0]
ans=1
for i in range(m):
    use.append(int(input()))
use.append(n)
print(use)
if n>=2:        
    lists=[1,1]

    for i in range(n-1):
        lists.append((lists[-1]+lists[-2])%1000000007)

    
    for i in range(m+1):
    
        if use[i+1]-use[i]==1 and i>=1and i<=(m-1):
            ans=0
            break
        if use[i+1]-use[i]>=2 and i>=1:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
        if i==0 and use[1]==1:
            ans=ans
        if i==0 and use[1]>=2:
            ans=(ans*lists[int(use[i+1]-use[i]-2)])%1000000007
        if i==m+1 and n-use[i-1]==1:
            ans=ans
        if i==m+1 and n-use[i-1]>=2:
            ans=(ans*lists[int(use[i]-use[i-1]-1)])%1000000007
      
            
    print(ans)
elif n==1:
    print(1)


def main():
    N,M = map(int,input().split())
    mod = 10**9 + 7
    a = [0]*(N+1)
    a[0] = 1
    banned = [False]*(N+1)
    for x in range(M):
        n = int(input())
        banned[n] = True
    for i in range(1,N+1):
        res = 0
        if not banned[i-1]:
            res += a[i-1]
        if not banned[i-2]:
            res += a[i-2]
        a[i] = res
    print(a[-1]%mod)
    return

main()


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted