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):
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if a>1:
            memo[a]=memo[a-1]+memo[a-2]
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
            continue
        if a>1:
            memo[a]=(memo[a-1]+memo[a-2])%mod
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in M:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    print(mod)
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()


# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=10**9+7
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    global N,M,A,mod,memo
    if(index>N):memo[index]=0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=A[a]
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
            continue
        if a>1:
            memo[a]=memo[a-1]+memo[a-2]
        else:
            memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in range(M):
        ban[a]=True
    mod=1000000007

    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in M:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            print("ban")
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] 
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in A:
        ban[a]=True
    mod=1000000007
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Accepted