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())
issafe = [True] * n
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * n
dp[0] = 1
if issafe[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

n, m = map(int, input().split())
issafe = [True] * n + 1
for _ in range(m):
    a = int(input())
    issafe[a] = False
 
dp = [0] * n +1
dp[0] = 1
if issafe[1]:
    dp[1] = 1
 
for i in range(2, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

n, m = map(int, input().split())
a = int(input()) for _ in range(m)

dp = [0] * 10000
dp[0] = 1
if 1 not in a:
    dp[1] = 1
    
for i in range(2, n + 1):
    if  (i - 1) not in a:
        dp[i] = dp[i] + dp[i - 1]
    if (i - 2) not in a:
        dp[i] = dp[i] + dp[i - 2]

    dp[i] %= 1000000007    
print(dp[n])



n, m = map(int, input().split())
a = int(input()) for _ in range(m)

dp = [0] * 10000
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if  (i - 1) not in a:
        print("/", dp[i])
        dp[i] = dp[i] + dp[i - 1]
        print("●  dp[{0}]={2}  dp[{1}]={3}".format(i-1, i, dp[i - 1],  dp[i]))
    if (i - 2) not in a:
        print("//", dp[i])
        dp[i] = dp[i - 2] + dp[i] 
        print("■  dp[{0}]={2}  dp[{1}]={3}".format(i-2, i, dp[i - 1],  dp[i]))
    
    print("dp[{0}]={1}".format(i, dp[i]))
    
    dp[i] %= 1000000007
    
print(dp[n])

, m = map(int, input().split())
issafe = [True] * 10000
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10000
dp[0] = 1
if issafe[1]:
    dp[1] = 1

for i in range(1, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

n, m = map(int, input().split())
a = int(input()) for _ in range(m)
 
dp = [0] * 10000
dp[0] = 1
if 1 not in a:
    dp[1] = 1
 
for i in range(2, n + 1):
    if  (i - 1) not in a:
        dp[i] = dp[i] + dp[i - 1]
    if (i - 2) not in a:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

, m = map(int, input().split())
issafe = [True] * 10000
for _ in range(m):
    a = int(input())
    issafe[a] = False

dp = [0] * 10000
dp[0] = 1
if issafe[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

n, m = map(int, input().split())
issafe = [True] * n
for _ in range(m):
    a = int(input())
    issafe[a] = False
 
dp = [0] * n
dp[0] = 1
if issafe[1]:
    dp[1] = 1
 
for i in range(2, n + 1):
    if  issafe[i - 1]:
        dp[i] = dp[i] + dp[i - 1]
    if issafe[i -  2]:
        dp[i] = dp[i - 2] + dp[i] 
    
    dp[i] %= 1000000007
    
print(dp[n])

n, m = map(int, input().split())
broken = {int(input()) for _ in range(m)}

mod = 10 ** 9 + 7

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in broken:
    dp[1] = 1

for i in range(2, n + 1):
    if i -1 not in broken:
        dp[i] = dp[i] + dp[i - 1]
    if i - 2 not in broken:
        dp[i] = dp[i] + dp[i - 2]
    
    dp[i] %= 1000000007
    
print(dp[n])

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted