TnT/Multi_CodeNet4Repair huggingface dataset:
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())
ls=[int(input()) for i in range(m)]

if 1 in ls:
    steps=[1,0]
else:
    steps=[1,1]

for this_step in range(2,n+1):
    if this_step in ls:
        ap=0
    else:
        ap=steps[-1]+steps[-2]
    steps.append(ap)
    print(steps)

print(steps[-1]%1000000007)

n,m=map(int,input().split())
danger=[int(input()) for i in range(m)]
danger=set(danger)
steps=[0]*(n+1)
steps[0]=1

if 1 in danger:
    steps[1]=0
else:
    steps[1]=1

for this_step in range(2,n+1):
    if this_step in danger:
        ap=0
    else:
        steps[this_step]=steps[this_step-1]+steps[this_step-2]

print(steps[-1]%1000000007)

Verdicts: Runtime Error

Accepted
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())
a = set([int(input()) for _ in range(m)])
print(a)
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
  dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
  if i in a:dp[i]=0
print(dp[n])

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


Verdicts: Wrong Answer

Accepted
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):
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (N)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n])

li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n]%=1000000007 if DP[n] != 0 else 0)

li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n] % 1000000007 if DP[n] != 0 else 0)

Verdicts: Runtime Error

Runtime Error

Accepted
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 main():
    N, M = map(int, input().split())
    broken = [int(input()) for _ in range(M)]
    div = 1000000007

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


if __name__ == "___main__":
    main()


def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)

    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1

    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div

    print(comb_list[-1])


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted
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())
A=[]
a=[]
a.append(0)
x=0
d=1
A.append(1)
A.append(2)
for j in range(2,N):
    A.append(A[j-1]+A[j-2])
for i in range(1,M+1):
    a.append(int(input()))
    x=A[a[i]-a[i-1]-2]
    d=d*x
    if i>1:
        if a[i]-a[i-1]==1:
            d=0
x=A[N-a[M]-2]
d=d*x
print(A[21],A[11])
print(d%(10**9+7))

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

Verdicts: Runtime Error

Accepted
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())
e = 10*9 + 7
c = 0
ans = 1
for _ in range(m):
    a = int(input())
    b = a-1-c
    if b < 0:
        ans *= 0
        break
    c = a+1
    print(sum([i for i in range(-(-b//2), b)]))
    ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
    
b = n - c
ans *= (1 + sum([i for i in range(-(-b//2), b)])) % e
print(ans)

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
e = 1e9 + 7
for i in range(1, N+1):
    if i not in A:
        if i == 1:
            dp[i] = 1
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[N])

n, m = map(int, input().split())
mod = 10e9+7
dp = [0]*(n+1)
dp[0] = 1
isPass = [1]*(n+1)
for _ in range(m):
    a = int(input())
    isPass[a] = 0
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if isPass[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(dp[n])

N, M = map(int, input().split())
A = [1] * (N+2)
for _ in range(M):
    a = int(input())
    A[a+1] = 0
dp = [0] * (N+2)
dp[1] = 1
e = 1e9 + 7
for i in range(2, N+2):
    if A[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[-1]))

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted
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())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1
fact = [1] * MAX

for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

def comb_init():
    fact[0], fact[1] = 1, 1
    for i in range(2, MAX):
        fact[i] = fact[i-1] * i

def comb(n, r):
    return (fact[n]%MOD) * pow(fact[r], -1, MOD) * pow(fact[n-r], -1, MOD) 

def f(k):
    idx = k // 2
    num = 0
    for i in range(1, idx+1):
        num += comb(k-i, i)
        num %= MOD
    return num+1

comb_init()
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    ans *= f(between)
    ans %= MOD
print(ans)

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]
print(fib[:10])

for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]
    
for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)

Verdicts: Time Limit Exceeded

Wrong Answer

Accepted
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 Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
elif b==0:
    print(Fib(a+2))
else:
    x=ll[0]
    l2.append(Fib(x+1))
    del ll[0]
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
a,b=input().split()
a=int(a)
b=int(b)
ll=[]
y=-1
s=0
for i in range(b):
    x=input()
    x=int(x)
    ll.append(x)
    if x-y==1:
        s=1
        break
    y=x
ll.append(a+1)
l2=[]
if s==1:
    print(0)
else:
    x=-1
    for i in ll:
        l2.append(Fib(i-x))
        x=i
    ans=1
    for i in l2:
        ans*=i
    print(ans%1000000007)

Verdicts: Wrong Answer

Accepted
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())
p=10**9+7
a=[int(input()) for i in range(m)]
b=[a[0]-1]
for i in range(m):
  b.append(a[i+1]-a[i]-2)
x=[1]*(max(b)+1)
for i in range(2,max(b)+1):
  x[i]=(x[i-1]+x[i-2])%p

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m):
    ans=(ans*x[b[i]])%p
print(ans)

n,m=map(int,input().split())
p=10**9+7
a=[int(input()) for i in range(m)]
a.append(n+1)
b=[a[0]-1]
for i in range(m):
  b.append(a[i+1]-a[i]-2)
x=[1]*(max(b)+1)
for i in range(2,max(b)+1):
  x[i]=(x[i-1]+x[i-2])%p

ans=1
if min(b)==-1:
  ans=0
else:
  for i in range(m+1):
    ans=(ans*x[b[i]])%p
print(ans)

Verdicts: Runtime Error

Accepted
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 main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    a = set(a)

    s[0] = 1
    s[1] = 1 if 1 not in a else 0

    for i in range(2, n+1):
        if i in a:
            continue
        s[i] = (s[i-1] + s[i-2]) % 1000000007

    print(s[n])

main()

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

s[0] = 1
s[1] = 1 if n-1 not in a else 0

for i in range(2, n+1):
    if i in a:
        continue
    s[i] = (s[i-1] + s[i-2]) % 1000000007


print(s[n])

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

s[0] = 1
s[1] = 1 if 1 not in a else 0

for i in range(2, n+1):
    if i in a:
        continue
    s[i] = (s[i-1] + s[i-2]) % 1000000007

print(s[n])

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
    
s = [0 if n-i in a else -1 for i in range(n+1)] 

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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
    
s = [0 if n-i in a else -1 for i in range(n+1)] 

s[0] = s[1] = 1
for i in range(2, n+1):
    if s[i] == 0:
        continue
    s[i] = (s[i-1] + s[i-2]) % 1000000007

def main():
    n, m = map(int, input().split())
    if m != 0:
        a = [int(input()) for _ in range(m)]
        a = set(a)
    else:
        a = set()
    
    s = [0] * (n+1)
    s[0] = 1
    s[1] = 1 if 1 not in a else 0

    for i in range(2, n+1):
        if i in a:
            continue
        s[i] = (s[i-1] + s[i-2]) % 1000000007

    print(s[n])

main()

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Accepted
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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = {}


def step(now):
    if now in a:
        return 0
    # print(now)
    if now == n:
        return 1
    if now > n:
        return 0
    if memo.get(now) != None:
        return memo[now]
    # print(now)
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


print(step(0) % 1000000007)
print(memo)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)

Verdicts: Wrong Answer

Accepted
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 sys
import math
input = sys.stdin.readline


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()[0]
    w = sc.intarr()
    is_safe = [True] * (n+2)
    for a in w:
        is_safe[a + 1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


import sys
import math
input = sys.stdin.readline


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()
    w = sc.intarr_ver(m)
    is_safe = [True] * (n)
    for i in w:
        is_safe[i-1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i-2]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0
    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


Verdicts: Runtime Error

Accepted
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 -*-
"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a and len(a)>=2 :
    f[1] = 0
elif 1 not in a and len(a)>=2:
    f[1] = 1

for i in range(2,N):
    if i in a:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
    f[i] %= mod

if N == 1:
    print(f[N-1])
else:       
    print((f[N-1]+f[N-2]) % mod)
    
    


N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

f = [0 for i in range(N)]
f[0] = 1
if 1 in a:
    f[1] = 0
else:
    f[0] = 1

for i in range(2,N):
    if i in a:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
        
print((f[N-1]+f[N-2])%1000000007)

# -*- coding: utf-8 -*-
"""
Created on Wed Jun 19 17:29:01 2019

@author: makigon
"""
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

aset = set(a)
f = [0 for i in range(N)]
f[0] = 1
if 1 in a and N>=2 :
    f[1] = 0
elif 1 not in a and N>=2:
    f[1] = 1

for i in range(2,N):
    if i in aset:
        continue
    else:
        f[i] = f[i-1]+f[i-2]
    f[i] %= mod

if N == 1:
    print(f[N-1])
else:       
    print((f[N-1]+f[N-2]) % mod)
    
    


Verdicts: Wrong Answer

Wrong Answer

Accepted
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 = list(map(int, input().split()))
A =[0]*M
for i in range(M):
    A[i] = int(input())

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
cnt[2] = 2 
for i in range(3,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
for i in range(M): 
    if i == 0:
        if A[i] != 1:
            ans*= cnt[A[i]-1]
    elif i > 0 and i < M:
        ans*=cnt[A[i] - A[i-1] - 1]

    if i == M-1:
        if A[i] != N -1:
            ans*= cnt[N - A[i]]
    
    if ans == 0:
        break
  
    ans %= amari

print(ans)

N, M = list(map(int, input().split()))
A =[0]*M
for i in range(M):
    A[i] = int(input())

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
for i in range(M): 
    if i == 0:
        if A[i] != 1:
            ans*= cnt[A[i]-1]
    elif i > 0 and i < M:
        ans*=cnt[A[i] - A[i-1]-1]

    if i == M-1:
        if A[i] != N -1:
            ans*= cnt[N - A[i]]
    
    if ans == 0:
        break
  
    ans %= amari

print(ans)

N, M = list(map(int, input().split()))
A =[0]*M
for i in range(M):
    A[i] = int(input())

amari = 1000000007
cnt = [0]*(N+2)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+2):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
def calc(ans):
    if M == 0:
        return cnt[N+1]

    for i in range(M): 
        if i == 0:
            ans*= cnt[A[i]]
        elif i > 0 and i < M:
            ans*=cnt[A[i] - A[i-1]-1]

        if i == M-1:
            ans*= cnt[N - A[i]]
        
        if ans == 0:
            break
    
        ans %= amari
        
    return ans

print(calc(ans))

Verdicts: Runtime Error

Wrong Answer

Accepted
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())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
def a(x):
  if x in l :
    return 0
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=0:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))%
print(a(n)%q)

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
for i in l:
  memo[i]=0
def a(x):
  if x in l :
    continue
  elif x==1:
    memo[1]=1
    return 1
  else:
    if memo[x]!=-1:
      return memo[x]
    else:
      memo[x] = a(x-1)+a(x-2)
      return (a(x-1)+a(x-2))
print(a(n)%q)

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1
for j in l:
  memo[j]=0
  
for i in range(2,n+1):
  if memo[i]==0:
    continue
  else:
    memo[i]=((memo[i-1]%q)+(memo[i-2]%q))%q
print(memo[-1]%q)

Verdicts: Runtime Error

Runtime Error

Accepted
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())
route = [int(x) for x in range(N)]
a = [int(input()) for _ in range(M)]
route = [item for index, item in enumerate(route) if index not in a]

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    print(nums)
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    print(nums)
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))


N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])

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

print(nums[N]%(1000000007))


Verdicts: Runtime Error

Runtime Error

Accepted
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())
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
def Fib(n, memo={}):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = Fib(n-1,memo)+Fib(n-2,memo)
        return memo[n]
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
print(b)


n,m=map(int,input().split())
a=[-1]
d=[]
for i in range(m):
 a.append(int(input()))
a.append(n+1)
for i in range(m+1):
 d.append(a[i+1]-a[i]-1)
ansk=1
for i in range(m+1):
 k=int(((1+5**(1/2)/2)**d[i]-(1-5**(1/2)/2)**d[i])/(5**1/2))
 ansk*=k
print(ansk%1000000007)


mod=10**9+7
n,m=map(int,input().split())
a=[int(input())for _ in range(m)]
a.append(n+1)
fib=[1,1]
for i in range(n):
	r=fib[-1]+fib[-2]
	fib.append(r%mod)
ans=1
now=0
for x in a:
	ans*=fib[x-1-now]
	if x-1-now<0:
		print(0)
		exit()
	ans%=mod
	now=x+1
print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted
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 numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

for i in range(m):
    a1=int(input())
    a.append(a1)

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*1000001
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        #dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

for i in range(m):
    a1=int(input())
    a.append(a1)

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*110000
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)

    if m == 0:
        print(dp[n+1])
    else:
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)

Verdicts: Time Limit Exceeded

Accepted
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())
a = []
ans = 1
for _ in range(m):
    a.append(int(input()))
mod = 10**9 + 7
p = 0
for i in range(m):
    print(p)
    if i == m-1:
        ans *= n - a[i] - 1
        # print('Y')
        break
    if a[i] == 1:
        if a[i+1] == 2:
            ans *= 0
        else:
            pass
    else:
        if a[i] == a[i+1] - 1:
            ans *= 0
        else:
            ans *= a[i] - p - 1
            p = a[i]

print(ans % mod)

n, m = map(int, input().split())
mod = 10**9 + 7
dp = [0]*(n+1)
broken = [0]*(n+1)
dp[0] = 1
for _ in range(m):
    broken[int(input())] = 1

for i in range(1, n+1):
    if broken[i]:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] %= mod

print(dp[n])

Verdicts: Wrong Answer

Accepted
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())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x
ans = dp[n] % x
print(ans)

n,m = map(int,input().split())
a = {int(input()) for _ in range(m)}
mod = 10**9 + 7

dp = [0]*(n+1)
dp[0] = 1
    
for i in range(1,n+1):
    if i in a:
        continue
    x = dp[i-1] 
    if i > 1:
        x += dp[i-2]
    dp[i] = x
ans = dp[n] % mod
print(ans)

Verdicts: Runtime Error

Accepted
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 main():
    n, m = map(int,input().split())
    a = [0] * m
    for i in range(m):
        a[i] = int(input())
    ans = [0] * (n+1)
    head = 0
    MOD = 10**9 + 7
    ans[0] = 1
    for i in range(1,n+1):
        print(head,i)
        if head < m and a[head] == i:
            ans[i] = 0
            head += 1
        else:
            if i == 1:
                ans[i] = 1
            else:
                print(i,i-1,i-2)
                ans[i] = (ans[i-1] + ans[i-2]) % MOD

    print(ans[n] % MOD)



if __name__ == '__main__':
    main()


def main():
    n, m = map(int,input().split())
    a = [0] * m
    for i in range(m):
        a[i] = int(input())
    ans = [0] * (n+1)
    head = 0
    MOD = 10**9 + 7
    ans[0] = 1
    for i in range(1,n+1):

        if head < m and a[head] == i:
            ans[i] = 0
            head += 1
        else:
            if i == 1:
                ans[i] = 1
            else:
                
                ans[i] = (ans[i-1] + ans[i-2]) % MOD

    print(ans[n] % MOD)



if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
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 math
def f(k):
    aaa = 1/math.sqrt(5)*(((1+math.sqrt(5))/2)**k-((1-math.sqrt(5))/2)**k)%1000000007
    return aaa
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(f(n-1))
else:
    pstart = [-1]+start+[n+1] 
    newlist = [] 
    for j in range(n-1):
        newlist.append(pstart[j+1]-pstart[j]) 
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: 
        for w in newlist:
            ans = 1
            ans = ans*f(w-1)%1000000007      
        print(ans)         

import math
def f(k):
    aaa = 1/math.sqrt(5)*(((1+math.sqrt(5))/2)**k-((1-math.sqrt(5))/2)**k)%1000000007
    return aaa
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input())
if start == []:
    print(f(n-1))
else:
    pstart = [-1]+start+[n+1] 
    newlist = [] 
    for j in range(n-1):
        newlist.append(pstart[j+1]-pstart[j]) 
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: 
        for w in newlist:
            ans = 1
            ans = ans*f(w-1)%1000000007      
        print(ans)         

def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1)%1000000007)
else:
    pstart = [-1]+start+[n+1] 
    newlist = [] 
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) 
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: 
        ans = 1
        #print(newlist)
        for w in newlist:
            #print(Fib(w-1))
            #print(ans)
            ans = (ans*Fib(w-1))%1000000007
        print(ans)         

Verdicts: Runtime Error

Runtime Error

Accepted
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())
A = [int(input()) for _ in range(M)]

MOD = 10**9 + 7

safe = [True] * (N+1)
for i in range(len(A)):
    safe[A[i]] = False

print(safe)

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

for i in range(2, N+1):
    if(safe[i]):
        dp[i] = dp[i-1] + dp[(i-2)]
        dp[i] = dp[i] % MOD
    else:
        dp[i] = 0

print(dp)

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

MOD = 10**9 + 7

safe = [True] * (N+1)
for i in range(len(A)):
    safe[A[i]] = False

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

for i in range(2, N+1):
    if(safe[i]):
        dp[i] = dp[i-1] + dp[(i-2)]
        dp[i] = dp[i] % MOD
    else:
        dp[i] = 0

print(dp)

MOD = 10**9 + 7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

aa = [True] * (N+1)
for i in a:
    aa[i] = False

dp = [0] * (N+1)
dp[0] = 1
if aa[1]:
    dp[1] = 1

for i in range(2,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] =  dp[i] % MOD
print(dp[N])


Verdicts: Wrong Answer

Wrong Answer

Accepted
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 sys
from collections import defaultdict

stairs = []
steps = []
MOD = 1000000007

n, m = int(input()), int((input()))
stairs = {int(input()):True for i in range(m)}

step = defaultdict(int)
step[0] = 1

for i in range(n):
    if i in stairs.keys():
        step[i] = 0
    else:
        step[i+1] = (step[i] + step[i+1]) % MOD
        step[i+2] = (step[i] + step[i+2]) % MOD

print(step[n])


from collections import defaultdict

stairs = []
steps = []
MOD = 1000000007

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

step = defaultdict(int)
step[0] = 1

for i in range(n):
    if i in stairs.keys():
        step[i] = 0
    else:
        step[i+1] = (step[i] + step[i+1]) % MOD
        step[i+2] = (step[i] + step[i+2]) % MOD

print(step[n])


Verdicts: Runtime Error

Accepted
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 = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = FalseN, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
elif len(dp) == 2:
    if dp[1] == -1:
        ans = 0
    else:
        ans = 1
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)
            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)
            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

N, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
elif len(dp) == 2:
    if dp[1] == -1:
        ans = 0
    else:
        ans = 1
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)
            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)
            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

Verdicts: Runtime Error

Accepted
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):
#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    As = list(map(int, readlines()))
    
    
    #     print(0)
    #     return
    broken = [False] * (n + 1)
    for a in As:
        broken[a] = True
    p1, p2 = 0, 1
    if broken[1]:
        p1 = 1

    for i in range(2, n + 1):
        if broken[i]:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()


#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    As = set(map(int, readlines()))
    
    
    #     print(0)
    #     return
 
    p1, p2 = 1, 1
    if 1 in As:
        p1 = 0

    for i in range(2, n + 1):
        if i in As:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Accepted
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 sys
input = sys.input.readline

MOD = 1000000007

n , m = map(int,input().split())

count = [-1] * (n+1)
for i in range(m):
    count[int(input())] = 0

for i in range(1,n+1):
    if count[i] == 0:
        continue
    
    if i == 1:
        count[i] = 1 
    elif i == 2:
        count[i] = count[i-1] + 1
    else:
        count[i] = (count[i-1] + count[i-2]) % MOD

print(count[n])



MOD = 1000000007

def main():
    n,m = map(int,input().split())
    al = [False for _ in range(n+1)]
    for i in range(m):
        a = int(input())
        al[a] = True
    
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp[1] = 1 if al[1] == False else 0

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

    print(dp[n])


if __name__ == "__main__":
    main()

Verdicts: Runtime Error

Accepted
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):
, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if i in alist:
        li[i] = 0
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = (li[i-1] + li[i-2])%(10**9+7)
print(li[N]%(10**9+7))

N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if len(alist)>=1 and i ==  alist[0]:
        li[i] = 0
        alist.pop(0)
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))

Verdicts: Runtime Error

Accepted
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())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(a)):
  steps=a[i]-a[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
    res*=patern_nmu
    res%=1000000007
print(res)

N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(A)):
  steps=A[i]-A[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
  res*=patern_nmu
  res%=1000000007
print(res)

Verdicts: Runtime Error

Accepted
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())
A = [True] * (N + 1)
for _ in range(M):
    a = int(input()) - 1
    A[a] = False

dp = [0] * (N + 1)

dp[0] = 1
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if A[j] is True:
            dp[j] += dp[i]
            dp[j] %= 10 ** 9 + 7

print(dp[N])


N, M = map(int, input().split())
A = [True] * (N + 1)
for _ in range(M):
    a = int(input())
    A[a] = False

dp = [0] * (N + 1)

dp[0] = 1
for i in range(N):
    for j in range(i + 1, min(N, i + 2) + 1):
        if A[j] is True:
            dp[j] += dp[i]
            dp[j] %= 10 ** 9 + 7

print(dp[N])


Verdicts: Wrong Answer

Accepted
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())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f = [0] * N
f[1] = 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    continue
  f[i] = f[i-2] + f[i-1]
print(f[N] % mod)

N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))
broken = set(broken)

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = (f2 + f1) % mod
  f2 = f1
  f1 = f
print(f)


Verdicts: Runtime Error

Runtime Error

Accepted