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):
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
"""
python3 main.py < input.txt
"""

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""

def genArr2(h,w): return [0]*(h*w)
def setArr2(A,ij,x): A[ij[0]*W + ij[1]] = x
def getArr2(A,ij): return A[ij[0]*W + ij[1]]
H,W=map(int, input().split())
S=genArr2(H,W)
for i in range(H):
        s=input()
        l=list(s)
        for j in range(W):
                setArr2(S,(i,j),l[j])

SWR=genArr2(H,W)
for i in range(H):
        setArr2(SWR, (i, 0), 0 if getArr2(S, (i, 0)) == "#" else 1)
        for j in range(1,W):
                if getArr2(S,( i, j)) == "#": setArr2(SWR, (i, j), 0)
                else: setArr2(SWR, (i, j), getArr2(SWR, (i, j-1)) + 1)
SWL=genArr2(H,W)
for i in range(H):
        setArr2(SWL, (i, W-1), 0 if getArr2(S, (i, W-1)) == "#" else 1)
        for j in range(W-2,-1,-1):
                if getArr2(S,( i, j)) == "#": setArr2(SWL, (i, j), 0)
                else: setArr2(SWL, (i, j), getArr2(SWL, (i, j+1)) + 1)
SHB=genArr2(H,W)
for j in range(W):
        setArr2(SHB, (0, j), 0 if getArr2(S, (0, j)) == "#" else 1)
        for i in range(1,H):
                if getArr2(S,( i, j)) == "#": setArr2(SHB, (i, j), 0)
                else: setArr2(SHB, (i, j), getArr2(SHB, (i-1, j)) + 1)
SHT=genArr2(H,W)
for j in range(W):
        setArr2(SHT, (H-1, j), 0 if getArr2(S, (H-1, j)) == "#" else 1)
        for i in range(H-2, -1, -1):
                if getArr2(S,( i, j)) == "#": setArr2(SHT, (i, j), 0)
                else: setArr2(SHT, (i, j), getArr2(SHT, (i+1, j)) + 1)

ans=0
for n in range(H*W):
        ij=(n//W,n%W)
        x=getArr2(SWR, ij) + getArr2(SWL, ij) + getArr2(SHB, ij) + getArr2(SHT,ij) - 3
        ans=max(ans,x)
print(ans)

import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])


Verdicts: Runtime Error

Accepted