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())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])
    

from collections import deque

def bfs(maze, visited, sy, sx, dead, goal):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    count = 0
    while queue:
        y, x = queue.popleft()
        if maze[y][x] == goal:
            count += 1
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if not maze[new_y][new_x] in dead and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return count % 1000000007

n,m=map(int, input().split())
a=[int(input()) for i in range(m)]
maze=[[2*i+j for i in range(int(n/2+1))] for j in range(n+1)]
visited = [[[-1] for i in range(int(n/2+1))] for j in range(n+1)]
print(bfs(maze, visited, 0, 0, a, n))


N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

for i in range(M):
    a=int(input())
    is_broken[a] = True

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])
    

N, M=map(int, input().split())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in range(N).reverse:
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])
    

N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

for i in range(M):
    a=int(input())
    is_broken[a] = True

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])
    

N, M=map(int, input().split())
items=[int(input()) for i in range(M)]
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0] = 1
is_broken =[1 for i in range(N+1)]

for i in range(M):
    is_broken[items[i]] = 0

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+1]) % mod

print(dp[0])
    

from collections import deque

def bfs(maze, visited, sy, sx, dead, goal):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    count = 0
    while queue:
        y, x = queue.popleft()
        if maze[y][x] == goal:
            count += 1
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if not maze[new_y][new_x] in dead and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return count % 1000000007
if __name__ == "__main__":
    n,m=map(int, input().split())
    a=[int(input()) for i in range(m)]
    maze=[[2*i+j for i in range(int(n/2+1))] for j in range(n+1)]
    visited = [[[-1] for i in range(int(n/2+1))] for j in range(n+1)]
    print(bfs(maze, visited, 0, 0, a, n))


N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+2)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

for i in range(M):
    a=int(input())
    is_broken[a] = True

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])
    

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Accepted