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):
def fiv(n):
    return int((((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))//(5**(1/2)))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: 
        if broken[m - 1] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i] 
if ans < 0:
    ans = ans * -1
ans = ans % 1000000007

print(int(ans))

def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

n, m = map(int, input().split())
broken = [input() for i in range(m)]

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: 
        if broken[m] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: 
        if broken[m] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)


def fiv(n):
    return (((1+(5)**(1/2))/2)** (n + 1) - ((1-(5)**(1/2))/2)** (n + 1))/(5**(1/2))

n, m = map(int, input().split())
broken = []
for i in range(m):
	broken.extend(map(int, input()))

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] - 1)
    if i == m: 
        if broken[m - 1] == n - 1:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0] - 1)
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i] / 1000000007

print(ans)

def fiv(n):
    return (((1+(5)**(1/2))/2)** n - ((1-(5)**(1/2))/2)** n)/(5**(1/2))

n, m = map(int, input().split())
broken = [input() for i in range(m)]

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1 or 2:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: 
        if broken[m] == n - 1 or m - 2:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0])
    
    else:
        p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

def fiv(n):
    return (((1+(5)**(1/2))/2)** n - ((1-(5)**(1/2))/2)** n)/(5**(1/2))

n, m = map(int, input().split())
broken = [input() for i in range(m)]

p = [0] * (m + 1) 

for i in range(m + 1):
    if i == 0: 
        if broken[0] == 1 or 2:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: 
        if broken[m] == n - 1 or m - 2:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0])
    
    else:
        if broken[i] - broken[i - 1] - 1 == 0:
            print('0')
            exit()
        else:
            p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

n, m = map(int, input().split())
mod = 10 ** 9 + 7
dp = [-1 for i in range(n + 1)]
dp[0], dp[1] = 1, 1
for _ in range(m):
    dp[int(input())] = 0
for i in range(2, n + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted