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())
a =  [int(input()) for i in range(m)]

dp =[0]*(n+1)
if 0 in a:
    dp[0] =0
else:
    dp[0]=1

if 1 in a:
    dp[1] =0
else:
    dp[1]=1

for i in range(2,n+1):

    if dp[i-1]==dp[i-2]==0:break

    dp[i] = (dp[i-2]+dp[i-1])

    if i in a[i]:
        dp[i] = 0

print(dp[-1]%1000000007)


import sympy as sym

def fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True) 
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) 
    result=Fib.subs(x,n) 
    result=result.evalf() 
    return int(result)

n,m = map(int,input().split())
a =  [int(input()) for i in range(m)]
a.append(n+1)

time_f=[]

for i,v in enumerate(a):
    if i == 0:
        # print (fib(a[i]))
        time_f = fib(a[i])
    else:
        # print((a[i]-a[i-1]-1))
        # print (fib(a[i]-a[i-1]-1))
        time_f *=fib(a[i]-a[i-1]-1)


print(time_f%1000000007)

def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

n,m = map(int,input().split())
a =  [int(input()) for i in range(m)]
a.append(n+1)

time_f=[]

for i,v in enumerate(a):
    if i == 0:
        print (fib(a[i]))
        time_f = fib(a[i])
    else:
        # print((a[i]-a[i-1]-1))
        print (fib(a[i]-a[i-1]-1))
        time_f *=fib(a[i]-a[i-1]-1)


print(time_f%1000000007)

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

dp =[0]*(n+1)

for i in a:
    dp[i] = -1

for i in [0,1]:
    if dp[i] == -1:
        dp[i] =0
    else:
        dp[i] =1

for i in range(2,n+1):
    if dp[i] == -1:
        dp[i] = 0
    else:
        if dp[i-1]==dp[i-2]==0:break
        dp[i] = (dp[i-2]+dp[i-1])

print(dp[-1]%1000000007)


Verdicts: Runtime Error

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):
# -*- coding: utf-8 -*-
#ABC130C
import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)

print(a)

for i in range(0,m):
	tmp = int(input())
	a[tmp]=0

print(a)

for i in range(2,n):
	a[i]=a[i]*(a[i-1]+a[i-2])


print((a[n-1]+a[n-2])% 1000000007)




# -*- coding: utf-8 -*-
#ABC130C
import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)

#print(a)

for i in range(0,m):
	tmp = int(input())
	a[tmp]=0

#print(a)


for i in range(2,n):
	a[i]=a[i]*(a[i-1]+a[i-2])


if(n==1):
	print(1)
else:
	print((a[n-1]+a[n-2])% 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 math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007



if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    broken = [True if i in A else False for i in range(N + 1)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007



if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



import sys

mod = 1000000007



if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())

    broken = [False for _ in range(N + 1)]
    for _ in range(M):
        broken[int(sys.stdin.readline())] = True

    L = [0] * (N + 1)
    L[0] = 1
    if not broken[1]:
        L[1] = 1
    for i in range(2, N + 1):
        if not broken[i]:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



Verdicts: Time Limit Exceeded

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

dp=[0]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
else:
    dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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

dp=[-1]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
if dp[1]==-1:dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

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):
sum_ = [0]

N,M = input().split()
N,M = int(N),int(M)
m_ = [0,N-1]
for i in range(M):
    m_.append(int(input()))


m = [1 for i in range(N+1)]
for i in m_:
    m[i] = 0
for i in range(1,N+1):
    if(i==1):
        if(m[i]==1):
            sum_.append(1)
        else:
            sum_.append(0)
    elif(i==2):
        if(m[i]==1):
            sum_.append(1+sum_[1])
        else:
            sum_.append(sum_[1])
    
    else:
        sum_.append(m[i-1]*sum_[i-1]+m[i-2]*sum_[i-2])
#print(sum_)
print(sum_[N]%1000007)

sum_ = [0]

N,M = input().split()
N,M = int(N),int(M)
m_ = []
for i in range(M):
    m_.append(int(input()))


m = [1 for i in range(N+1)]
for i in m_:
    m[i] = 0
for i in range(1,N+1):
    if(i==1):
        if(m[i]==1):
            sum_.append(1)
        else:
            sum_.append(0)
    elif(i==2):
        if(m[i]==1):
            sum_.append(1+sum_[1])
        else:
            sum_.append(sum_[1])
    
    else:
        sum_.append((m[i-1]*sum_[i-1]+m[i-2]*sum_[i-2])*m[i])
print(sum_[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
 
n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]
 
dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
 
for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans*=fib[a-1]
    if ans >= 1000000007:
        ans-=1000000007
    bef=a+1
 
print(ans)

import sys

n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]

dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
print(dist)

for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans*=fib[a-1]
    ans%=1000000007
    bef=a+1

print(max(1,ans))


import sys

n,m=map(int,input().split())
A=[int(input()) for __ in range(m)]
bef=0
ans=0
fib=[0,2,3]

dist=[]
for a in A:
    if a-bef-1 == 0 and a != 1:
        print(0)
        sys.exit()
    else:
        dist.append(a-bef-1)
    bef=a
dist.append(n-bef-1)
print(dist)

for a in dist:
    if len(fib)<=a:
        for i in range(len(fib),a):
            fib.append(fib[i-1]+fib[i-2])
    ans+=fib[a-1]
    if ans >= 1000000007:
        ans-=1000000007
    bef=a+1

print(max(1,ans))


N,M=map(int,input().split())
A=set([int(input()) for __ in range(M)])
ans=[0]*(N+1)
ans[0] = 1

if 1 in A:
    ans[1]=0
else:
    ans[1]=1

for n in range(N+1):
    if n>1:
        if n-1 in A and n in A:
            print(0)
            break
        elif n in A:
            ans[n]=0
        else:
            ans[n]=(ans[n-1]+ans[n-2]) % 1000000007
else:
    print(ans[N])


Verdicts: Wrong Answer

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):
from itertools import permutations

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

patterns = []
for i in range(N, -1, -2):
    pattern = [1] * i
    while sum(pattern) < N:
        pattern.append(2)
    else:
        patterns.extend(set(permutations(pattern)))
import ipdb; ipdb.set_trace()
ans = 0
for pattern in patterns:
    now = 0
    for p in pattern:
        if now + p not in AL:
            now += p
        else:
            break
    else:
        ans += 1
print(ans)


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

# DP
dp = [1] * (N + 1)
for A in AL:
    dp[A] = 0

for i in range(2, N + 1):
    if dp[i] == 1:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9 + 7)
print(dp[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):
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, n+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % MOD)


from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, n+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n] % MOD)


from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
dp = [1 for i in range(N+1)]
MOD = 1000000007
for _ in range(M):
  a = int(stdin.readline().rstrip())
  dp[a] = 0
for i in range(2, N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % MOD)

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 = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
a1 = int(input())
a.append(a1)
diff.append(a1+1)

if m>1:
    for xi in range(m-1):
        a0 = a1
        a1 = int(input())
        a.append(a1)
        diff.append(a1-a0)

if a1==n-1:
    diff.append(n-a1+1)
else:
    diff.append(n-a1+1)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)+2):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )


import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, m = (int(xi) for xi in input().split())

a = []
diff = 0
a0 = 0
a1 = 0
for xi in range(m):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    if a1-a0>diff :
        diff=a1-a0

print(comb(n,diff))
print(diff)
print(a)

p = [1]
for xi in range(1,diff+1):
    add = 1
    for j in range(1, int(xi/2)):
        add += comb(xi-j,j)
    p.append(add)


import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, m = (int(xi) for xi in input().split())

a = []
diff = 0
a0 = 0
a1 = 0
for xi in range(m):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    if a1-a0>diff :
        diff=a1-a0

print(comb(n,diff))
print(diff)
print(a)

p = [1]
for xi in range(1,diff+1):
    p[xi] = 1
    for j in range(1, int(xi/2)):
        p[xi] += comb(xi-j,j)


n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
if m>0:
    a1 = int(input())
    a.append(a1)
    diff.append(a1+1)

    if m>1:
        for xi in range(m-1):
            a0 = a1
            a1 = int(input())
            a.append(a1)
            diff.append(a1-a0)

    if a1==n-1:
        diff.append(n-a1+1)
    else:
        diff.append(n-a1+1)


else:
    if n==1: diff.append(n+1)
    diff.append(n+2)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)+2):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )


Verdicts: Runtime Error

Wrong Answer

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())
mod=10**9+7
A=[1]*(N+1)
for i in range(M):
  a=int(input())
  A[a]=0
print(A)
for i in range(2,N+1):
  if A[i]!=0:
    A[i]=(A[i-1]+A[i-2])%mod
print(A[-1]%mod)
print(A)

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

N,M = map(int,input().split())
mod=10**9+7
A = {int(input()) for i in range(M)}

if 1 in A:
  x=0
else:
  x=1
B=[1,x]
for i in range(2,N+1):
  if i in A:
    B +=[0]
  else:
    B +=[(B[i-1]+B[i-2])%mod]
print(B[-1]%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):
def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1])
    print(answer[N] % 1000000007)

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input().split()))
solve(N, M, A)



def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if A[1]:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if A[s] == 0:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

N, M = [int(x) for x in input().strip().split()]
A = [1] * N
for _ in range(M):
    A[int(input())] = 0
solve(N, M, A)



def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input()))
solve(N, M, A)



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 = [True]*(n+2)
mod = 10**9+7
for i in range(m):
    a[i] = False

dp = [0]*(n+2)
dp[0]=1

for i in range(n):
    if not a[i]:
        continue
    if a[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if a[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n]%mod)

n,m = map(int,input().split())
a = [True]*(n+10)
mod = 10**9+7
for i in range(m):
    a[i] = False

dp = [0]*(n+10)
dp[0]=1

for i in range(n):
    if not a[i]:
        continue
    if a[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if a[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n]%mod)

n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])
step = [1] + [0]*n
mod = 10**9 + 7
for i in range(1,n+1):
    if i in a:
        continue
    else:
        if i-1 not in a:
            step[i] += step[i-1]%mod
        if i-2 not in a and i>=2:
            step[i] += step[i-2]%mod
        if i-1 in a and i-2 in a:
            print(0)
            exit()
print(step[n]%(10**9+7))

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):
zimport sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		sys.exit()
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		sys.exit()
	for k in range(2,N):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if a == N - 1:
		print(ans%1000000007)
	else:
		print(ans%1000000007)
main()

import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	print(A)
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			print(r)
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

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 i in range(m)]
for i in range(m-1):
  if A[i]+1 == A[i+1]:
    print(0)
    exit()

ANS = [A[0]-0]
for i in range(m-1):
  ANS.append(A[i+1]-A[i]-1)
ANS.append(n-A[m-1])

Fib = [1,1,2]
for i in range(3,max(ANS)+4):
  Fib.append(Fib[i-1]+Fib[i-2])

print(Fib)
print(ANS)
ans = 1
for i in range(len(ANS)):
  ans = (ans * Fib[ANS[i]-1])%1000000007
  
print(ans)

n,m = map(int, input().split())
A = [int(input()) for i in range(m)]
if m == 0:
  Fib = [1,2]
  for i in range(2,n):
    Fib.append(Fib[i-2]+Fib[i-1])
  print(Fib[n-1]%1000000007)
  exit()

B = [A[i+1]- A[i] for i in range(m-1)]
B.insert(0,A[0]+1)
B.append(n+1-A[m-1])

M = max(A)

Fib = [0,1]
for i in range(2,M+10):
  Fib.append(Fib[i-2]+Fib[i-1])

ans = 1
for i in range(len(B)):
  ans = (ans * Fib[B[i]-1])%1000000007
  
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 solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    if N == 1:
        return 1

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


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



# -*- coding: utf-8 -*-
"""



"""
import sys


def solve(N, M, A):
    MOD = 10**9 + 7
    A = set(A)
    if N == 1:
        return 1 if 1 not in A else 0
        
    dp = [0] * (N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in A else 0
    for i in range(2, N+1):
        if i in A:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % MOD
    return dp[-1]


def main(args):
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    ans = solve(N, M, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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=[0]
for _ in range(M):
    a.append(int(input()))

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

print(b)

num=max(b)

mod=1000000007

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

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib[b[j]]
    print(p%mod)

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)

mod=1000000007

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

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib[b[j]]
    print(p%mod)

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

n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
broken=[False for _ in range(n+1)]
for _ in range(m):
    broken[int(input())]=True
    
for i in range(1,n+1):
    if broken[i]:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%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)]

dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        pass
    else:
        dp[i] = dp[i-1] + dp[i-2]
        
print(dp[n]%MOD)

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[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):
import math

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

for i in range(M+1):
    dist=a[i+1]-a[i]-2
    if dist<0 and a[i]!=-1 and a[i+1]!=N+1:
        ans=0
        break
    
    val=0
    cnt1=dist%2
    cnt2=dist//2
    while cnt2 >= 0:
        val+=math.factorial(cnt1+cnt2)/math.factorial(cnt1)/math.factorial(cnt2)
        cnt2-=1
        cnt1+=2
    ans*=val
    print(dist,val)

print(ans%1000000007)

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

for i in range(N+1):
    if a[i+1] != 1:
        dp[i+1]+=dp[i]
        dp[i+1]%=mod
    if a[i+2] != 1:
        dp[i+2]+=dp[i]
        dp[i+2]%=mod
    print(i,dp[i])
    
print(dp[N])

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
dp=[1]*(N+1)
dp[0]=1
dp[1]=1
print(a)

for i in range(1,N+1):
    if i in a:
        dp[i]=0
    elif i==1:
        pass
    else:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007

print(dp[N])

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
dp=[1]*(N+1)
dp[0]=1
dp[1]=1
print(a)

for i in range(1,N+1):
    if i in a:
        dp[i]=0
    elif i==1:
        pass
    else:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
    print(i,dp[i])
        
print(dp[N])

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

Verdicts: Runtime Error

Wrong Answer

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):
def selector(flag):
    if flag:
        return 0
    else:
        return 1

def func(x, a, n):
    if not a[n]:
        x[n] = selector(a[n-1]) * x[n-1] + selector(a[n-2]) * x[n-2]
    else:
        x[n] = 0

K = 1000000007
line = input().split(' ')
N = int(line[0])
M = int(line[1])
a = [False] * (N + 1)
x = [0] * (N + 1)

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

x[0] = 1
if a[1]:
    x[1] = 1
else:
    x[1] = 0

for i in range(2, N+1):
    func(x, a, i)
    
print(x[N]%K)

def func(x, a, n):
    if a[n] == 1:
        x[n] = a[n-1] * x[n-1] + a[n-2] * x[n-2]
    else:
        x[n] = 0

def main():
    K = 1000000007
    line = input().split(' ')
    N = int(line[0])
    M = int(line[1])
    a = [1] * (N + 1)
    x = [0] * (N + 1)

    for i in range(M):
        hole = int(input())
        a[hole] = 0

    x[0] = 1
    if a[1] == 1:
        x[1] = 1
    else:
        x[1] = 0

    for i in range(2, N+1):
        func(x, a, i)
        
    print(x[N]%K)

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):
fib=[0,1]
for i in range(9999):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[0]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
  ans=ans*max(1,fib[hoge[i+1]-hoge[i]-1])
  ans=ans%1000000007
  
print(ans%1000000007)

fib=[0,1]
for i in range(9999):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
  ans=ans*max(1,fib[hoge[i+1]-hoge[i]-1])
  ans=ans%1000000007
  
print(ans%1000000007)

fib=[0,1]
for i in range(100000):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[-1]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
for i in range(len(hoge)-1):
  sa=hoge[i+1]-hoge[i]-1
  ans=ans*fib[sa]
  ans=ans%1000000007
print(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())
a=[]
b=[0]*N
for i in range(M):
    a.append(int(input()))
j=0
if a[0]==1:
    b[0]=0
    b[1]=1
elif a[0]==2:
    b[0]=1
    b[1]=1
else:
    b[0]=1
    b[1]=2
for i in range(N-2):
    if j==M-1 or ((i+2)!=a[j] and (i+1)!=a[j]):
        b[i+2]=b[i+1]+b[i]
    if j>0 and a[j]==a[j-1]+1:
        b[N-1]=0
    if j+1<M and a[j+1]==a[j]+1:
        b[N-1]=0
    elif (i+2)==a[j]:
        b[i+2]=b[i]
    elif j+1<M and (i+1)==a[j]:
        j+=1
        b[i+2]=b[i+1]
    elif (i+1)==a[j]:
        b[i+2]=b[i+1]
print(b[N-1]%1000000007,b)

N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
j=M-1
if a[0]==1:
    f1=0
    f2=1
elif a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    print("a")
    if n>2:
        if (n-1)!=a[j] and (n-2)!=a[j]:
            if n>3 and n-3==a[j]:
                return f(n-1,a,j)+f(n-2,a,j-1)
            else:
                return f(n-1,a,j)+f(n-2,a,j)
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
             if n>3 and j>0 and n-3==a[j-1]:
                return f(n-2,a,j-1)
             else:
                return f(n-2,a,j)
        elif (n-2)==a[j]:
            return f(n-1,a,j-1)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

N,M=map(int,input().split())
a=[]
b=[0]*N
for i in range(M):
    a.append(int(input()))
if M==0:
    j=-1
else:
    j=0
if N==1:
    b[0]=1
elif M>0 and a[0]==1:
    b[0]=0
    b[1]=1
elif M>0 and a[0]==2:
    b[0]=1
    b[1]=1
else:
    b[0]=1
    b[1]=2
for i in range(N-2):
    if j==M-1 or (j>=0 and (i+2)!=a[j] and (i+1)!=a[j]):
        b[i+2]=b[i+1]+b[i]
    if j>0 and a[j]==a[j-1]+1:
        b[N-1]=0
    if j+1<M and a[j+1]==a[j]+1:
        b[N-1]=0
    elif j>=0 and (i+2)==a[j]:
        b[i+2]=b[i]
    elif j>=0 and j+1<M and (i+1)==a[j]:
        j+=1
        b[i+2]=b[i+1]
    elif j>=0 and (i+1)==a[j]:
        b[i+2]=b[i+1]
print(b[N-1]%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):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)
read=sys.stdin.read
N,M,*alst=map(int,read().split())
mod=10**9+7
dp = [1, 1 if 1 not in alst else 0]
@lru_cache(maxsize=None)
def a(n):
  if n==0:
    return dp[0]
  elif n==1:
    return dp[1]
  else:
    if n not in alst:
      return (a(n-2)+a(n-1))%mod
    else:
      return 0
print(a(100))


from collections import deque
def main():
  N,M,*A=map(int, open(0).read().split())
  mod=10**9+7
  dp = [0] * (N+1)
  A=deque(A+[N+1])
  tmp=A.popleft()
  dp[:2] = [1, 1 if tmp!=1 else 0]
  if tmp==1:
    tmp=A.popleft()
  for i in range(2, N+1):
    if i==tmp:
      tmp=A.popleft()
      continue
    dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
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(' '))

@lru_cache(maxsize=4096)
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n -2)

safe_area = []
a_p = int(input())
safe_area.append(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    safe_area.append(diff-1)
    a_p = a

safe_area.append(N - a_p)

sum = 1
for i in safe_area:
    sum *= fib(i)
print(sum % 1000000007)


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

MOD = 1000000007

def fib(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

broken_step = []
p_a = -1
for i in range(M):
    a = int(input())
    if (a - p_a == 1):
        print("0")
        exit()
    else:
        p_a = a
    broken_step.append(a-1)

count_0 = 0
count_1 = 1
next_broken = 0
pre_is_broken = False
for i in range(N):
    if (next_broken >= len(broken_step) or i != broken_step[next_broken]):
        if (pre_is_broken):
            count_0 = 0
            pre_is_broken = False
        else:
            count_0, count_1 = count_1, count_0 + count_1
            count_0 %= MOD
            count_1 %= MOD
    else:
        next_broken+=1
        count_0 = 0
        pre_is_broken = True

print(count_1)


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 = list(map(int, input().split()))
alist = []
for m in range(M) :
    alist.append(int(input()))
    
a2 = 0
a1 = 1
for n in range(N) :
    a0 = (a1 + a2)*int((n+1) not in alist)%1000000007
    print(a0)
    a2, a1 = a1, a0
else :
    print(a0)

from functools import lru_cache
from sys import setrecursionlimit

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

mod = 10**9+7
setrecursionlimit(mod)

@lru_cache(maxsize=n)
def stairway(i) :
    if i in a :
        return 0
    elif i == 0 :
        return 1
    elif i == 1 :
        return stairway(0)
    else :
        return (stairway(i-1)+stairway(i-2))%mod
    
print(stairway(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):
import sys
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int,input().split()))
def inpm():
    return map(int,input().split())

n,m = inpm()
dp = [0] * (n+2)
for _ in range(m):
    a = int(input())
    dp[a] = -1

# init
dp[0] = 1
# start
print(a)
for i in range(n):
    if dp[i] == -1:continue
    dp[i] %= mod
    if dp[i+1] != -1:
        dp[i+1] += dp[i]
    if dp[i+2] != -1:
        dp[i+2] += dp[i]

print(dp[n]%mod)


mod = 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(0,n-1):
    dp[i+2] = dp[i+2] * (dp[i+1] + dp[i])%mod
print(dp[-1])


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())
lis = [0]*n+1
a = []
for i in range(m):
    a.append(int(input()))
    
mod = 10**9+7
ans = 0
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[1] = 1
    elif 2 in a:
        lis[0] = 1
    else:
        lis[0] = 1
        lis[1] = 2
    
    for j in range(3,n+1):
        if j in a:
            lis[0] = lis[1]
            lis[1] = 0
        else:
            ans = lis[0]%mod + lis[1]%mod
            lis[0] = lis[1]
            lis[1] = ans
        
        if lis[0] == 0 and lis[1] == 0:
            ans = 0
            break
        

    print(ans%mod)

n,m = map(int,input().split())
lis = [False]*(n+1)
a = []
for i in range(m):
    a = int(input())
    lis[a] = True

mod = 10**9+7
dp =[0]*(n+1)
dp[0] =1
for i in range(n):
    dp[i] %= mod
    if (lis[i]):dp[i] = 0
    if i+1 <=n:
        dp[i+1] += dp[i]
    if i+2 <=n:
        dp[i+2] += dp[i]

print(dp[n]%mod)

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 = [int(input()) for _ in range(m)]
MOD = 10**9+7
dp = [-1]*(n+1)
dp[0] = dp[1] = 1

for x in a:
    dp[x] = 0

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


print(dp[n] if dp[n] != INF else 0)

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

for x in a:
    dp[x] = 0

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

print(dp[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):
OK = "O"
BRO = "B"

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
        
if BRO+BRO in K:
  print(0)
else:
  c=[0 for i in range(N+1)]
  if K[N-1]==OK:
    c[1]=1
  if K[N-2]==OK and K[N-1]==OK:
    c[2]=2
  if K[N-2]==OK and K[N-1]==BRO:
    c[2]=1

  for i in range(3,N+1):
    c[i]=(c[i-1]+c[i-2])%1000000007
  print(c[N])


OK = "O"
BRO = "B"

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

K = list(OK for i in range(N+1))
for i in range(M):
  K[Broken[i]] = BRO
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 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 = [int(input()) for i in range(M)] 
z = [0] * (N+1)

def rootCount(x):
     print(x)
     if x in a:
          z[x] = 0
          return 0
     elif x == 0:
          z[x] = 1
          return 1
     elif x == 1:
          z[x] = 1
          return 1
     elif x < N and z[x] != 0:
          print("hit " + str(x))
          print(z)
          return z[x]
     else:
          print(x,x-1,x-2)
          print(z)
          z[x] = rootCount(x-1) + rootCount(x-2)
          return z[x]
print(rootCount(N) % 1000000007)


N, M = map(int, input().split())
z = [-1] * (N+1)
for i in range(M):
     z[int(input())] = 0

for i, x in enumerate(z):
     if i == 0:
          z[i] = 1
     elif i == 1 and z[i] != 0:
          z[i] = 1
     elif z[i] == 0:
          continue
     elif z[i-1] == 0 and z[i-2] == 0:
          print(0)
          exit()
     else:
          z[i] = z[i-1] + z[i-2]
print(z[-1] % 1000000007)


Verdicts: Runtime Error

Accepted