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 = []
for i in range(M):
    a.append(int(input()))
    
way = []
for i in range(N+1):
    if i == 0:
        way.append(0)
    elif i == 1:
        way.append(1)
    else:
        way.append(way[i-1]+way[i-2])
    
ans = 1
now = 0
for i in range(N):
    if (i+1) in a:
        if now == 0 and i != 0:
            ans = 0
            break
        elif i == 0:
            pass
        else:
            ans*=way[now]
            now = 0
    else:
        now+=1
ans*=way[now]
print(ans%1000000007)


mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = 0
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a

if flag == 1:
    print(0)
else:
    
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)
    


mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = 0
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)
    


mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = -1
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

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):
N, M = map(int, input().split())
if N == 1:
    print(1)
else:
    A = [int(input()) for _ in range(M)]

    S =[0]*(N + 1)
    S[0] = 1
    if A[0] == 1:
        S[1] = 0
    else:
        S[1] = 1

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


N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(N + 1)]
DP[0] = 1
if 1 in A:
    DP[1] = 0
else: DP[1] = 1
for i in range(2, N+1):
    if i in A:
        DP[i] = 0
    else:
        DP[i] = (DP[i-1] + DP[i-2])%p
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 exit
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]

N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = 0
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % mod)

import sys
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = -1
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    sys.exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % 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):
a

a, b = map(int, input().split())
c = [int(input()) for _ in range(b)]
d = [0] * (a + 1)
d[0] = 1
d[1] = 1
for i in c:
    d[i] = -1
for i in range(2, len(d)):
    if d[i] != -1:
        d[i] = ((0 if d[i-1] == -1 else d[i-1]) + (0 if d[i-2] == -1 else d[i-2])) % 1000000007
print(d[len(d)-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):


MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1

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

print(dp[N])




MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for i in range(N):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in A:
    dp[1] = 1

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

print(dp[N])




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

def f(i):
    if dp[i] != None:
        return dp[i]
    else:
        if i in A:
            dp[i] = 0
        elif i < 2:
            dp[i] = 1
        else:
            dp[i] = (f(i - 1) + f(i - 2)) % MOD
        return dp[i]

print(f(N))




MOD = (10 ** 9) + 7
N, M = map(int, input().split())
A = [False] * (N + 1)
for _ in range(M):
    A[int(input())] = True
dp = [0] * (N + 1)
dp[0] = 1
if A[1] == False:
    dp[1] = 1

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

print(dp[N])


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

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
mod = 10**9+7
dp[0] = 1
dp[1] = int(1 not in a)
for i in range(2,n+1):
  if i in a:
    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):
import numpy as np
from math import factorial as fac

N,M=  map(int, input().split())
broken_steps=[]

for m in range(M):
    broken_steps.append(int(input()))

for i in range(len(broken_steps)-1):
    if broken_steps[i+1]-broken_steps[i]==1:
        print("{}".format(0))
        FLG=True

if FLG!=True:        
    count=0
    for two_step in range(M,N//2+1):
        one_step=N-two_step*2
        count+=fac(two_step+one_step)/(fac(two_step)*fac(one_step))

    print("{}".format(count%1000000007))

import numpy as np
from math import factorial as fac
FLG=False
N,M=  map(int, input().split())
broken_steps=[]

for m in range(M):
    broken_steps.append(int(input()))

for i in range(len(broken_steps)-1):
    if broken_steps[i+1]-broken_steps[i]==1:
        print("{}".format(0))
        FLG=True

if FLG!=True:        
    count=0
    for two_step in range(M,N//2+2):
        one_step=N-two_step*2
        if one_step>0:
            count+=fac(two_step+one_step)/(fac(two_step)*fac(one_step)*fac(M))

    print("{}".format(count))
        



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

ls = [1 for _ in range(N + 1)]
for i in range(M):
    ls[int(input())] = 0

for n in range(2, N + 1):
    if ls[n] != 0:
        
        ls[n] = (ls[n - 1] + ls[n - 2]) % MOD
print(ls[N])

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):
from collections import deque

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

before1 = 1
before2 = 0
ai = a.popleft if len(a) else 0

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        ai = a.popleft if len(a) else ai
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current

print(before1)


from collections import deque

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

before1 = 1
before2 = 0
ai = a.popleft() if len(a) else 0

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        ai = a.popleft() if len(a) else ai
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current

print(before1)


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

n,m=map(int,input().split())
a=set()
for i in range(m):
  a.add(int(input()))
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
if n==1:
  print(dp[1])
  exit()
if 2 in a:
  dp[2]=0
else:
  dp[2]=dp[1]+1
for i in range(3,n+1):
  if i in a:
    dp[i]=0
  else:
    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):
n,m=map(int, input().split())  

import sys

sys.setrecursionlimit(10**20)

if m == 0:
    print(countWays_memo(n))
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    def countWays_memo(n):
        memo = [-1]*(n+1)
        def _countWays(n):
            if n < 0:
                return 0
            elif n == 0:
                return 1
            else:
                if memo[n] > -1:
                    return memo[n]
                else:
                    memo[n] = _countWays(n-1) + _countWays(n-2) 
                    return memo[n]
        return _countWays(n)

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

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

import sys

sys.setrecursionlimit(10**9)

def countWays_memo(n):
    memo = [-1]*(n+1)
    def _countWays(n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        else:
            if memo[n] > -1:
                return memo[n]
            else:
                memo[n] = _countWays(n-1) + _countWays(n-2) 
                return memo[n]
    return _countWays(n)
    
if m == 0:
    print(countWays_memo(n)% 1000000007)
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 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())
dp = [0]*n

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if dp[1] == 10**12:
    dp[1] = 0
else:
    dp[1] = 1+ dp[0]

mod = 1000000007

if 2 in a_list:
    dp[1] = 0
for i in range(2,n):
    if dp[i] == 10**12:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[-1])

n,m = map(int,input().split())
a_list = []
for i in range(m):
    a_list.append(int(input()))
    
mod = 1000000007

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

n,m = map(int,input().split())
dp = [0]*n

for i in range(m):
    dp[int(input())-1] = 10**12
    
if dp[0] == 10**12:
    dp[0] = 0
else:
    dp[0] = 1

if n == 1:
    print(dp[0])
else:
    if dp[1] == 10**12:
        dp[1] = 0
    else:
        dp[1] = 1+ dp[0]

    mod = 1000000007

    for i in range(2,n):
        if dp[i] == 10**12:
            dp[i] = 0
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= mod
    print(dp[-1])

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 fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
a = [int(input()) for i in range(M)]
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,i-preidx-2])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    ans.append([idx,N-preidx-1])

# print(ans)
fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= fibonacci(val[1])
print(fibsum%1000000007)







import sys
sys.setrecursionlimit(10000001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)%1000000007

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1%1000000007 if n==0 else fibonacci_sub2(n-1, (fibo_minus1+fibo_minus2)%1000000007, fibo_minus1%1000000007)%1000000007


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum) 


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())
def C(a,b):
    return math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
def pattern(n):
    ans = 0
    i = 0
    while n - 2*i >= 0:
        ans += C(n-i*2,i)
        i += 1
    return ans
ab = 0
ans = 1
mod = 10**9 + 7
for i in range(M):
    aa = int(input())
    if aa != 1:
        n = aa-ab-2
        ans *= pattern(n)
        ans = ans%mod
    ab = aa
if ab != N-1:
    n = N-ab-2
    ans *= pattern(n)
    ans = ans%mod
print(int(ans))

import math
N,M = map(int, input().split())
def C(a,b):
    return math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
def pattern(n):
    ans = 0
    i = 0
    while n - 2*i >= 0:
        ans += C(n-i*2,i)
        i += 1
    return ans
ans = 1
mod = 10**9 + 7
l = [0 for i in  range(M)]
for i in range(1,M):
    l[i] = int(input()) - l[i-1] -2
if N-l[M-1]-2 >= 0:
    l.append(N-l[M-1]-2)
l.sort()
for i in range(len(l)):
    if i != 0 and l[i] == l[i-1]:
        ans *= tmp
    else:
        ans *= pattern(l[i])
    ans = ans%mod
    tmp = pattern(l[i])
print(int(ans))

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

Verdicts: 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())
aa = {int(input()) for _ in range(m)}
dp = [0 for _ in range(n + 1)]
dp[0] = 1

if 1 not in aa:
    dp[1] = 1

for i in range(2, n + 1):
    if dp[i - 1] > 0 and (i - 1) not in aa:
        dp[i] += dp[i - 1]
    if dp[i - 2] > 0 and (i - 2) not in aa:
        dp[i] += dp[i - 2]

print(dp[-1] % 1000000007)
print(dp[-1])


n, m = map(int, input().split())
aa = {int(input()) for _ in range(m)}
dp = [0 for _ in range(n + 1)]
dp[0] = 1

if 1 not in aa:
    dp[1] = 1

for i in range(2, n + 1):
    if dp[i - 1] > 0 and (i - 1) not in aa:
        dp[i] += dp[i - 1]
    if dp[i - 2] > 0 and (i - 2) not in aa:
        dp[i] += dp[i - 2]

print(dp[-1] % 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())
def stair(N):
    if(N <0):
        return 0
    if(N == 0):
        return 1
    elif(N == 1):
        return 1
    elif(N == 2):
        return 2
    else:
        return stair(N-1)+stair(N-2)
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    ans = ans*stair(b-a)%mod
    print(a,b,ans)
    a = b+2
ans = ans*stair(N-a)%mod
print(ans)

N,M = map(int,input().split())
steps = [1,1,2]
for i in range(3,N+1):
    steps.append(steps[i-1]+steps[i-2])
ans = 1
a = 0
mod = 10**9+7
for i in range(M):
    b = int(input())
    b -=1
    if(b<a):
        print(0)
        exit()
    else:
        ans = ans*steps[b-a]%mod
    a = b+2
ans = ans*steps[N-a]%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):
n, m = map(int,input().split())

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

for i in range(m):
    b[int(input())] = -1

for i in range(m):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= 1000000007

print(b[n] % 1000000007)


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

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

for i in range(m):
    b[int(input())] = -1

for i in range(n):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= 1000000007

print(b[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):
n,m=map(int,input().split())
broken=[int(i) for i in range(n)]
mod=10**9+7

factorial=[1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)

inv_factorial = [-1] * (n+1)
inv_factorial[-1] = pow(factorial[-1], mod-2, mod)

for i in reversed(range(n)):
    inv_factorial[i] = inv_factorial[i+1] * (i+1) % mod

def fact(n):
    return factorial[n]

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n] * inv_factorial[n-k] * inv_factorial[k]

def cnt(n):
    ans=0
    for i in range(n//2+1):
      ans+=nck(n-i,i)
      ans%=mod
    return ans

ans=cnt(broken[0]-1)
for i in range(1,m):
  tmp=broken[i]-broken[i-1]-2
  if tmp==-1:
    ans=0
    break
  else:
    ans*=cnt(tmp)
    ans%=mod
    
tmp=n-broken[m-1]-1
ans*=cnt(tmp)
print(ans)

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

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

A = [int(a) for a in input().strip()]

a0 = 1 
a1 = 1 if A[0] !=1 else 0 

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A[1:] if a1 !=0 else A
next = 0
for i in range(2,n+1) :
  if i == Next[next]:
    A[i] = 0
    next += 1 
  else:
    A[i] = A[i-2] + A[i-1] 
  
print(A[n])

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

A = [int(input().strip()) for _ in range(m)]

a0 = 1
if len(A) == 0:
  a1 = 1
else:
  a1 = 1 if A[0] !=1 else 0
mod = 1000000007

ANS=[0]*(n+1)
ANS[0]=a0
ANS[1]=a1
Next = A if a1 !=0 else A[1:]
next = 0
for i in range(2, n+1):
    if next <= len(Next)-1:
        if i == Next[next]:
            ANS[i] = 0
            next += 1
            continue
    ANS[i] = ANS[i-2] + ANS[i-1]

print(ANS[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 = list(map(int, input().split()))
if m > 0:
  a = [int(input()) for i in range(m)]
else:
  a = []

if n = 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

pat = (pt[-1] % 1000000007)
print(pat)


n, m = list(map(int, input().split()))
if m > 0:
  a = set([int(input()) for i in range(m)])
else:
  a = set([])

if n == 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

  pat = (pt[-1] % 1000000007)
print(pat)


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 functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  if n in a:
    return 0
  if 1 not in a and n == 1:
    return 0
  elif n in (0, 1):
    return 1
  else:
    return (comb(n-1) + comb(n-2))

print(comb(n)%(10**9 + 7))

n, m = list(map(int,input().split()))
a = []
for i in range(m):
  a.append(int(input()))
c = [0] * (n+2) #combination
for i in a:
  c[i] = -1
c[0] = 1

for i in range(n):
    if c[i] < 0:
      continue
    if c[i+1] >= 0:
        c[i+1] = c[i] + c[i+1]
    if c[i+2] >= 0:
        c[i+2] = c[i] + c[i+2]
    c[i] = c[i] % 10**9+7
print(c[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):
import sys
import math 
n,m=map(int,input().split())
a=[]
for i in range(m):
    b=int(input())
    if b-1 in a:
        print(0)
        sys.exit()
    else:
        a.append(b)
        
state=0
step=0
ans=0

bunnbo=lambda n,r: math.factorial(r)*math.factorial(n-r)
bunshi=lambda n: math.factorial(n)

for i in range(m):
    temp=0
    step=(a[i]-1)-state
    
    for j in range(step//2+1):
        temp+=(bunshi(step-j)//bunnbo(step-j,j))
    print(temp)
    
    if i==0:
        ans+=temp
    else:
        ans*=temp
    
    state=a[i]+1
    
    if i==m-1:
        temp=0
        step=n-state
        for j in range(step//2+1):
            temp+=(bunshi(step-j)//bunnbo(step-j,j))
        
        print(temp)
        ans*=temp
            
print(ans%(10**9+7))

        


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


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):
m = map(int, (input().split()))
a = {int(input()) for i in range(m)}
mod = 10 ** 9 + 7
 
x = 1 if 1 not in a else 0
dp = [1, x] + [0] * (n - 1)
 
for i in range(2, n + 1):
    if i in a:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2])
 
print(dp[-1] % mod)

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

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

for i in range(2,n+1):
   if i not in A:
      dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%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):
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]
    
N, M = map(int, input().split())
if N == 1:
    print(1)
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *= fib(x)
    num = num % 1000000007
print(num)

N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
S = [-1] * (N + 1)
S[0] = 1
for i in range(M):
    S[int(input())] = 0
if S[1] != 0:
    S[1] = 1
for i in range(2, N + 1):
    if S[i] == 0:
        continue
    else:
        S[i] = (S[i - 1] + S[i - 2]) % 1000000007
        if S[i] == 0:
            print(0)
            quit()
print(S[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):
def kjou(kkk):
    ka=1
    for km in range(kkk):
        ka=ka*(km+1)    
    return ka

def fcof(ad):
    k=ad//2
    if k==0 :
        return 1
    kcnt=0
    for kk in range(k+1):
        ar=ad-(kk)*2
        dk=kjou(kk+ar)/kjou(kk)/kjou(ar)
        kcnt=kcnt+ dk
        print(ad,k,kk,ar)
    return kcnt       

n,m=map(int,input().split())
n=20
m=2
a1=int(input())
a1=3
icnt=1
for i in range(m):
    a2=int(input())
    a2=11
    ad=a2-a1-1
    if ad<=0:
        print(0)
    fcof1=fcof(ad) 
    icnt=icnt*fcof1
    a1=a2
    print(icnt)

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

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
for now in range(n):
    for next in range(now+1,min(n,now+2)+1):
        if a[next]:
            dp[next]+=dp[now]
            dp[next]=dp[next]%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):
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
if 1 in a:
    dp[1]=0
dp[0]=1
mod=10**9+7
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

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

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

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

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

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

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):
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2,N+1)
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[-1]%(7+10**9))

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

dp = [0]*(N+100)
for i in range(N+1):
  if i == 0:
    dp[i] = 1
    continue
  if i in a:
    continue
  elif i-1 in a:
    dp[i] = dp[i-2]
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a and i-2 in a:
    break
  else:
    dp[i] = dp[i-1] + dp[i-2]
  dp[i] = dp[i]%(7+10**9)
    
print(dp[N]%(7+10**9))

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 sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = 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)
      
  




import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = False


DP = [0] * (N+1)
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)
      
  




import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [True] * (N+10)
MOD = 10 ** 9 + 7
for _ in range(M):
  x = int(readline())
  A[x] = 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)
      
  




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())
dp = [int(input()) for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

N, M = map(int, input().split())
dp = [int(input()) for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[i] = dp[i-2] + dp[i-1]

print(dp[N] % 1000000007)

N, M = map(int, input().split())
dp = [0 for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

N, M = map(int, input().split())
dp = [0 for i in range(N+1)]
for i in range(M):
    A = int(input())
    dp[A] = -1
dp[0] = 1
if dp[1] != -1:
    dp[1] = 1
else:
    dp[1] = 0
for j in range(2, N + 1):
    if dp[j] == -1:
        dp[j] = 0
        continue
    dp[j] = dp[j-2] + dp[j-1]

print(dp[N] % 1000000007)

Verdicts: Runtime Error

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

if n==1:
  print(1)
  exit()
if n==2:
  print(2-m)
  exit()
kumiawase = [0 for i in range(n+1)]
kumiawase[0] = 1
kumiawase[1] = 1
kumiawase[2] = 2
for i in range(3,n+1):
  kumiawase[i] = kumiawase[i-2] + kumiawase[i-1]

if m==0:
  print(kumiawase[n])
  exit()
if m==1:
  if a[0]==1 or a[0]==n-1:
    print(kumiawase[n-2])
  else:
    print(kumiawase[a[0]-2]*kumiawase[n-1-a[0]])
houhou = 1
if a[0] != 1:
  houhou *= kumiawase[a[0]-1]
houhou %= 1000000007
if a[m-1] != n-1:
  houhou *= kumiawase[n-1-a[m-1]]
houhou %= 1000000007
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    exit()
  elif a[i]-a[i-1]==2:
    continue
  houhou *= kumiawase[a[i]-a[i-1]-2]
  houhou %= 1000000007
print(houhou)


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

if n==1:
  print(1)
  exit()
if n==2:
  if m==0:
    print(2)
  else:
    print(1)
  exit()

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

com=1
anow=-1
for i in range(m):
  a=int(input())
  if a-anow==1:
    print(0)
    exit()
  com = (com * fib[a-anow-1]) % 1000000007
  anow=a

com = (com * fib[n-anow]) % 1000000007
print(com)

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.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

a=[int(input()) for i in range(m)]

def fib(n):
    if n==0:
        return 1
    if n==1:
        return 1
    if n==2:
        return 2
    return fib(n-1)+fib(n-2)

ans=1
check=0
for i in a:
    if i-check==1 and i!=1:
        print(0)
        exit()
    if i-check==1 and i==1:
        check=1
    else:
      ans*= fib(i-check-2)
      check=i
ans*=fib(n-a[-1]-1)
print(ans%((10**9)+7))


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

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

    

Verdicts: Runtime Error

Accepted