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):
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
else:
    j=0
    for i in range(1,N+1):
        if i==a[j]:
            if j+1<=M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==1:
            c[i]=1
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)
            

import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
elif N==1:
    print(1)
else:
    j=0
    for i in range(1,N):
        if i==a[j]:
            if j+1<M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==2:
            c[i]=c[i-1]
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)
            


import numpy as np
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a_a=np.ones( N+1 )
MOD=7+10**9
for i in range(M):
    a_a[a[i]]=0
c=np.zeros(N+1)
c[0]=1
for i in range(1,N+1):
    if i==1:
        c[i]=c[i-1]*a_a[i-1]
    else:
        c[i]=c[i-1]*a_a[i-1]%MOD+c[i-2]*a_a[i-2]%MOD
print(int(c[N])%MOD)

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



memo = [-1] * (N+1)
memo[0] = 1

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1:
        memo[i] = memo[i-1]
    if memo[i] >= 0:
       memo[i] = 0
        
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)

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

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



memo = [-1] * (N+1)
memo[0] = 1

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1 and memo[i]>=0:
        memo[i] = memo[i-1]
    elif memo[i] >= 0:
       memo[i] = 0
        
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)



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

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



memo = [-1] * (N+1)
memo[0] = 1

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1 and memo[i] == -1:
        memo[i] = memo[i-1]
    elif memo[i] >= 0:
       memo[i] = 0
        
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.  However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

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

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


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

for i in range(n):
  if i+1 not in o:
    dp[i+1] = dp[i] + dp[i-1]
  else:
    dp[i+1] = 0
  #print(i,dp)
#print(dp)
print(dp[-1]%mod)

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

brokenIndexSet = set([int(input()) for i in range(brokenCount)])

ans = [0] * (maxNum + 1)
ans[0] = 1

for i in range(1,maxNum+1):
  if i in brokenIndexSet:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1] + ans[i-2]) % 1000000007
  print(ans)

print(ans[maxNum])

maxNum, brokenCount = map(int,input().split(" "))

brokenIndexSet = set([int(input()) for i in range(brokenCount)])

ans = [0] * (maxNum + 1)
ans[0] = 1

for i in range(1,maxNum+1):
  if i in brokenIndexSet:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1] + ans[i-2]) % 1000000007

print(ans[maxNum])

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


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

    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, N+1):
        if i in a:
            dp[i] = 0
            continue


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


    print(dp)

main()

import sys
from collections import deque
 
def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])
 
    atmp = -1
    if len(a) != 0:
        atmp = a.popleft()
 
    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue
 
        if i == 0 or i == 1:
            dp[i] = 1
            continue
 
        if dp[i-1] == 0 and dp[i-2] == 0:
            break
 
 
        dp[i] = dp[i-1] + dp[i-2]
 
    print(dp[N] % 1000000007)
 
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):
#C
n, m = map(int, input().split())
a = [1] * (n + 1)
mod=1e9+7
print(a)
for i in range(m):
    a[int(input())] = 0
print(a)
b = [1] * (n + 1)
if a[1] == 0:
    b[1] = 0
for i in range(2, n + 1):
    b[i] = int(a[i] * (b[i - 2] + b[i - 1]) % mod)
print(b[n])

#C
n, m = map(int, input().split())
a = [1] * (n + 1)
b = [1] * (n + 1)

for i in range(m):
    a[int(input())] = 0
mod = 1e9+7
print(a)
if a[1] == 0:
    b[1] == 0
for i in range(2, n+1):
    
    b[i] = (b[i - 1] + b[i - 2]) * a[i] % mod
print(int(b[n]))


#C
n, m = map(int, input().split())
a = [1] * (n + 1)
mod=1e9+7
print(a)
for i in range(m):
    a[int(input())] = 0
print(a)
b = [1] * (n + 1)
if a[1] == 0:
    b[1] = 0
for i in range(2, n + 1):
    b[i] = int(a[i] * (b[i - 2] + b[i - 1]) % mod)
print(b, b[n])

#C
n, m = map(int, input().split())
a = [1] * (n + 1)
b = [1] * (n + 1)

for i in range(m):a[int(input())] = 0
mod = 1e9+7
# print(a)
if a[1] == 0:b[1] = 0
for i in range(2, n+1):b[i] = (b[i - 1] + b[i - 2]) * a[i] % mod
    
print(int(b[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):
Num = 1000000007 
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
now = 0
if 1 in a:
    prev1 = 0
else:
    prev1 = 1
prev2 = 1

for i in range(2,N+1):
    if i in a:
        now = 0
        prev2 = prev1
        prev1 = now 
        continue
    else:
        now = prev1 +prev2
        prev2 = prev1
        prev1 = now
    print(prev1,prev2)

print(now%Num)

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

Keiro = [0 for _ in range(N+1)]
Keiro[0] = 1
Keiro[1] = 1
for i in range(2,N+1):
    if i in a:
        continue
    else:
        Keiro[i] = (Keiro[i-1]+Keiro[i-2])%(1e9+7)

print(Keiro)
print(Keiro[-1])

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

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

    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[-1]%Num)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.  However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

Submission attempts (in order):
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
if M == 0:
    print(pat[N] % MOD)
else:
    pat = [0] * (N+1)
    pat[1] = 1
    pat[2] = 2
    for i in range(3, N+1):
        pat[i] = (pat[i-1] + pat[i-2]) % MOD
    steps = []
    if len(A) > 1
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
pat = [0] * (N+3)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = []
    if len(A) > 1:
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % 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())
a=[]
for i in range(m):
    a.append(int(input()))

inf=1000000007

def fib(k):
    a, b = 1, 1
    for i in range(k):
        yield a
        a, b = b, a + b
 
l=[i for i in fib(n)]
p=[]
for i in range(n):
    if i+1 in a:
        p.append(1)
    else:
        p.append(0)

ans=1

for i in range(n-1):
   if p[i]==1 and p[i+1]==1:
       print(0)
       exit()
k=[a[0]-1]
for i in range(m-1):
    k.append(a[i+1]-a[i]-2)
k.append(n-a[m-1]-1)
print(k)
#if k[0]==0:
#   k[0]=1
for j in range(len(k)):
    if j==0:
        ans*=l[k[j]]%inf
    elif j==len(k)-1:
        ans*=l[k[j]]%inf
    else:
        ans*=l[k[j]]%inf
print(ans%inf)


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

inf=1000000007

l=[1,1]
for i in range(n+2):
    l.append((l[i]+l[i+1])%inf)



if m!=0:
    k=[a[0]]
    for i in range(m-1):
        k.append(a[i+1]-a[i]-1)
    k.append(n-a[m-1])

    flag=True
    for i in range(1,len(k)):
       if k[i]==0:
            flag=False
    ans=1

    for j in range(len(k)):
        ans=(ans*l[k[j]-1])%inf

    if flag:
        print(ans%inf)
    else:
        print(0)
else:
    print(l[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 numpy as np
BIG_NUM = 10**9+7
def stairs_n(n):
    if n <= 3:
        return n
    else:
        return stairs_n(n-1)+stairs_n(n-2)



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

if m == 0:
    print(stairs_n(n)%BIG_NUM)
else:


    a_list = [int(input()) for _ in range(m)]
    a_list.append(n)
    a_np = np.array(a_list)
    diff_a_np = np.diff(a_np)-1
    ans = 1
    # print(a_np)
    # print(diff_a_np-1)
    ans *= (a_list[0])
    for num in diff_a_np:
        ans *= stairs_n(num)

    print(ans%BIG_NUM)

import numpy as np
BIG_NUM = 10**9+7
def stairs_n(n):
    if n <= 3:
        return n
    else:
        return stairs_n(n-1)+stairs_n(n-2)



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

if m == 0:
    print(stairs_n(n)%BIG_NUM)
else:


    a_list = [int(input()) for _ in range(m)]
    a_list.append(n)
    a_list.insert(0,1)
    a_np = np.array(a_list)
    diff_a_np = np.diff(a_np)-1
    ans = 1
    # print(a_np)
    # print(diff_a_np)
    for num in diff_a_np:
        ans *= stairs_n(num)

    print(ans%BIG_NUM)

N, M = map(int,input().split())
dp = [0]*(N+1)
broke = [0]*(N+1)
dp[0] = 1
dp[1] = 1

for _ in range(M):
    a = int(input())
    broke[a] = -1

for i in range(N-1):
    if broke[i] != -1 and broke[i+1] != -1:
        dp[i+2] = dp[i+1] + dp[i]
    elif broke[i] == -1and broke[i+1] != -1:
        dp[i+2] = dp[i+1]
    elif broke[i+1] == -1and broke[i] != -1:
        dp[i+2] = dp[i]
    else:
        print(0)
        exit()
# print(broke)
# print(dp)
MOD = 10**9+7
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(i) for i in input().split()]
a = [-1]

MAX = 100000
MOD = 1000000007
fac = [1 for i in range(MAX)]
finv = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def COM(n , r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r]* finv[n-r]%MOD)%MOD

for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += COM(k-i, i)
    ans = ans * cnt % 1000000007
    if ans == 0:
        break

print(int(ans))


n, m = [int(i) for i in input().split()]
a = [-1]
 
MAX = 100000
MOD = 1000000007
fac = [1 for i in range(MAX)]
finv = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
 
def COM(n , r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r]* finv[n-r]%MOD)%MOD
 
for mi in range(m):
    a.append(int(input()))
a.append(n+1)
 
ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += COM(k-i, i)
    ans = ans * cnt % 1000000007
    if ans == 0:
        break
 
print(int(ans))

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

b = [0 for i in range(n+1)]

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.  However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

Submission attempts (in order):
N,M=map(int,input().split())
A=[]
for i in range(M):
  A.append(int(input()))
ans=0
MOD=1000000007
dp=[]
for i in range(N-1,0,-1):
  if i in A:
    dp[i]=0
    continue
  dp[i]=dp[i+1]+dp[i+2]
  
ans=dp[0]
ans/=MOD
print(ans)
           


MOD = 10**9 + 7
n, m = map(int, input().split())

ban = [False] * (n + 1)

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

dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if(ban[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 i in range(m)]
check=[0 for i in range(n+1)]
for i in range(m):
    check[a[i]]=1
MOD= 1000000007

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

for i in range(2,n+1):
    if check[i]!=0:
        print(i)
        continue
    else:
        c[i] = (c[i - 1] + c[i - 2]) % MOD

print(c[n])

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
check=[0 for i in range(n+1)]
for i in range(m):
    check[a[i]]=1
MOD= 1000000007

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

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

print(c[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 calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1:
        return 1
    if num == 2:
        return 2
    return calc_step_combination(num - 1) + calc_step_combination(num - 2)


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start - 1)
        batch_start = a + 1
    step_batch.append(n - batch_start)

    result = 1
    for i, steps in enumerate(step_batch):
        if i == 0 and steps == 0:
            continue
        result *= calc_step_combination(steps)

    print(result % 1_000_000_007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list = int(input())
    sol(n, a_list)


main()

import sys

sys.setrecursionlimit(110000)

d = {}


def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        result *= calc_step_combination(steps)
    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()


Verdicts: Runtime Error

Accepted
Problem: There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step. He can climb up one or two steps at a time.  However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.  How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps? Find the count modulo 1\ 000\ 000\ 007.

Submission attempts (in order):
n.m = map(int,input().split())
l = [int(input()) for _ in[0]*m]
l=set(l)
dp=[0]*(n+1)

dp[0]=1
dp[1]=0 if 1 in l else 1
MOD =10**9+7

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

n,m = map(int,input().split())
l = [int(input()) for _ in[0]*m]
l=set(l)
dp=[0]*(n+1)

dp[0]=1
dp[1]=0 if 1 in l else 1
MOD =10**9+7

for i in range(2,n+1):
  if i not in l:
    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):
from functools import lru_cache
2.@lru_cache(maxsize=1000)
3.def fib(n):
4.    if n < 2:
5.        return n
6.    else:
7.        return fib(n - 1) + fib(n - 2)
8. 
9.n,m = map(int,input().split())
10.a = []
11.a.append(0)
12.for i in range(m):
13.    b = int(input())
14.    b -= 1
15.    a.append(b)
16.a.append(n)
17.b = []
18. 
19.for i in range(n):
20.    b.append(fib(i))
21. 
22.c = []
23.#if a[1] == 0:
24.    #c.append(1)
25.#else:
26.    #c.append(b[a[1] - a[0] ])
27.i = 0
28.while i <= m:
29.    #if a[i + 1] - a[i] - 2 >= 0:
30.    c.append(b[a[i + 1] - a[i]  - 2])
31.    i += 1
32.    #elif a[i + 1] - a[i] - 2 == 0:
33.        #c.append(1)
34.    #else:
35.        #c.append(0)
36.        #break
37.#print(c)
38.d = c[0] 
39.i = 1
40.#print(d)
41.while i < len(c):
42.    d = d * c[i]
43.    i += 1
44.e = 1000000007
45.print(d % e)
46.#print(b[0])


from functools import lru_cache
@lru_cache(maxsize=1000)
def fib(n):
	if n < 2:
		return n
	else:
		return fib(n - 1) + fib(n - 2)



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

a.append(n)

b = []
for i in range(n+1):
	b.append(fib(i))
	
c = []
#if a[1] == 0:
	#c.append(1)
#else:
	#c.append(b[a[1] - a[0] ])
	
	
i = 0
while i <= m + 1:
	if a[i + 1] - a[i] - 2 >= 0:
		c.append(b[a[i + 1] - a[i]  - 2])
		i += 1
	#elif a[i + 1] - a[i] - 2 == 0:
		#c.append(1)
	else:
		c.append(0)
		break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
	d = d * c[i]
	i += 1

e = 1000000007
print(d % e)
#print(b[0])

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

for i in range(1,n):
    b.append(fib(i))

c = []
if a[1] == 0:
    c.append(1)
else:
    c.append(b[a[1] - a[0] ])
i = 1
while i <= m:
    if a[i + 1] - a[i] - 2 >= 0:
        c.append(b[a[i + 1] - a[i]  - 2])
        i += 1
    #elif a[i + 1] - a[i] - 2 == 0:
        #c.append(1)
    else:
        c.append(0)
        break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
    d = d * c[i]
    i += 1
e = 1000000007
print(d % e)
#print(b[0])

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

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


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

arr = [-1]+arr+[N+1]
from math import factorial
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    nptn = int(span/2)
    regional_count = 0
    print(span,nptn)
    for k in range(0,nptn+1):
        print(span,k,factorial(span-k)//factorial(k)//factorial(span-2*k))
        regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
    print(regional_count)
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

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

arr = [-1]+arr+[N+1]
from math import factorial
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        #regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
        mul = lambda a,b: a*b
        regional_count += reduce(mul, range(span-k,k,-1),1) // reduce(mul, range(1,span-2*k+1),1)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

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

dp = [0 for _ in range(0,N+1)]

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % 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):
import math
N,M = map(int, input().split())
ans = 1
bro = list([])

def Comp (A , B):
    ans = math.factorial(A) // (math.factorial(A-B) * math.factorial(B))
    return ans

def Keisan (X):
    sum=0
    a = int(X//2+1)
    x = int(X)
    if X== -1:
        return 0

    for i in range(a):
        sum+= Comp(x-i , i)

    return sum


for i in range(M):
    bro.append(input())

bro.append(N+1) 


for i in range(len(bro)):
    if i == 0:
        a = int(bro[i])
        ans = ans*Keisan(a-1)
    else:
        a = int(bro[i])
        b = int(bro[i-1])
        ans = ans*Keisan(a-b-2)

ans = int(ans//(10**9+7))

print(ans)


N,M = map(int, input().split())
ans = 1
bro = list([])

for i in range(M):
    bro.append(int(input()))

bro.append(-1)

f = [0,0,1]

def Step (i):
    if i == bro[0]:
        bro.pop(0)
        f[0],f[1],f[2] = f[1],f[2],0
    else:
        f[0],f[1],f[2] = f[1],f[2],(f[1]+f[2])%(10**9+7)

for i in range(N):
    Step(i+1)

ans = f[2]%(10**9+7)

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):
#
import sys
import math
import numpy as np
import itertools


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


a = [int(input()) for i in range(m)] 
a.append(9999999) # sentinel
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
MOD = 1000000007

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2])%MOD
        b.append(c)

#print(a,b)
print(b[n])


#
import sys
import math
import numpy as np
import itertools

MOD = 1000000007

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


if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []
a.append(9999999) # sentinel
dame=0

b=[1]
if a[dame]==1:
    dame += 1
    b.append(0)
else:
    b.append(1)

for i in range(2,n+1):
    if i==a[dame]:
        dame += 1
        b.append(0)
    else:
        c=(b[i-1]+b[i-2]) % MOD
        b.append(c)

#print(a,b)
print(b[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())
MOD = 1000000007

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

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

def sigmaComb(dis):
  ans=0
  end=dis//2 if dis%2 != 0 else dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    ans+=t
  return ans

#print(fact)
#print(fact_inv)
hole=[0]
ans=1
for i in range(m):
  t = int(input())
  if t == hole[-1]+1:
    if hole[-1] == 0:
      hole.append(t)
      continue
    else:
      ans=0
      break
  dis=t-hole[-1]-2
  ans=ans*sigmaComb(dis)%MOD
  hole.append(t)
else:
  dis=n-hole[-1]-2+1
  ans=ans*sigmaComb(dis)%MOD

print(ans%MOD)

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

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

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

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    #print(dis-i,i,t)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  #print("dis=",dis,t,ans)
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

print(ans%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,ng = map(int,input().split())
nglist = list(int(input()) for i in range(ng))

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

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

  if i in nglist:
    dp[i] == 0
    continue

  if i==1:
    dp[1] == dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

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

MOD    = 10**9+7 
nglist = [0]*(n+1)
dp     = [0]*(n+1)
dp[0]  = 1

for i in range(ng):
  x = int(input())
  nglist[x] = 1
 
for i in range(1,n+1):

  if nglist[i]==1:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % 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 math
from fractions import Fraction
import sys

from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
    if (n == 0):
        return (Fraction(1), Fraction(1));
    if (n % 2 == 0):
        return fibExp(fibMul(fn, fn), n / 2);
    return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a - c, b - d)

def fibMain(n):
    fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
    fibNum2 = (Fraction(1, 2), Fraction(-1, 2))
    fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n)) 
    fibNum4 = (Fraction(0, 1), Fraction(1, 5))
    return fibMul(fibNum3, fibNum4)

def fib(n):
    return fibMain(n)[0].numerator

print(fib(100))



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

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:

        count *= fib(x)
print(int(count)%1000000007)

import math
from fractions import Fraction
import sys


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a;
        self.b = b;
        self.c = c;
        self.d = d;
    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)
    
def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a



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

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:

        count *= fib(x)
print(int(count)%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 scipy.misc as sm

def fib(N):
  N = N-1
  a = N // 2
  ans = 0
  for i in range(a+1):
      sum = sm.factorial(N-i)/(sm.factorial(N-2*i)*sm.factorial(i))
      ans += int(sum)
  return ans

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

flag = False
for i in range(M-1):
  if (A[i]+1 == A[i+1]):
    flag = True

if flag:
  print(0)
else:
  parts = []  
  for i in range(M):
    if i == 0:
      a_list = [x for x in range(0, A[i])]
      parts.append(a_list)
    else:
      a_list = [x for x in range(A[i-1]+1, A[i])]
      parts.append(a_list)
  a_list = [x for x in range(A[M-1]+1, N+1)]
  parts.append(a_list)
  ans = 1
  for part in parts:
    part_ans = fib(len(part))
    ans *= part_ans
  print(ans % 1000000007)

    

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

flag = False
for i in range(M-1):
  if (A[i]+1 == A[i+1]):
    flag = True

if flag:
  print(0)
elif M != 0:
  parts = []  
  for i in range(M):
    if i == 0:
      a_list = [x for x in range(0, A[i])]
      parts.append(a_list)
    else:
      a_list = [x for x in range(A[i-1]+1, A[i])]
      parts.append(a_list)
  a_list = [x for x in range(A[M-1]+1, N+1)]
  parts.append(a_list)
  ans = 1
  for part in parts:
    part_ans = fib(len(part))
    ans *= part_ans
  print(ans % 1000000007)
else:
  ans = fib(N+1)
  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):
import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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

import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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



import numpy as np

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

ans = np.zeros(N + 1)
ans[N] = 1

if N - 1 not in a:
    ans[N - 1] = 1

print(ans[N])

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

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

stairs = []

for i in range(M):
    stairs.append(int(input()))
path = []
index = 1
if stairs[-1] == N-1:
    path.extend([1, 0])
    index += 1
else:
    path.extend([1, 1])
# caluclate from N-2 step (second last)

if N >= 2:
    for n in range(2, N):
        if N - n != stairs[-index]:

            path.append(path[n-2] + path[n-1])
        else:
            path.append(0)
            index += 1
    print((path[-1] + path[-2]) % (10**9+7)) 
#     print(path)
elif N < 2:
    print(1)
        

import numpy as np

N, M = map(int, input().split())
stairs_exist = np.ones(N+1)
div_num = 10 ** 9 + 7

for c in range(M):
    stairs_exist[int(input())] = 0
    
steps = np.zeros(N+1)
steps[0] = 1
for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if stairs_exist[j]:
            steps[j] += steps[i]
            steps[j] %= div_num
            
print(int(steps[-1]))

Verdicts: Wrong Answer

Wrong Answer

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())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False
dp = [0] * (N+1)
if oks[1]:
    dp[1] = 1
if oks[2]:
    dp[2] = 1
for i in range(3, N+1):
    if oks[i]:
        dp[i] = int((dp[i-1] + dp[i-2]) % (1e9+7))


print(dp[N])

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


print(dp[N])

import sys

sys.setrecursionlimit(1000000)

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


print(dp[N])

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

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])


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

for _ in range(m):
  a = int(input())
  dp[a] = -1

for i in range(1,n-1):
  if dp[i+2]==-1:
    continue
  if dp[i]==-1 and dp[i+1]==-1:
    dp[i+2] = -1
  elif dp[i]==-1:
    dp[i+2] = dp[i+1]
  elif dp[i+1]==-1:
    dp[i+2] = dp[i]
  else:
    dp[i+2] = dp[i] + dp[i+1]
    
print(dp[n]%(10**9+7) if dp[n]!=-1 else 0)

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

for _ in range(m):
  a = int(input())
  dp[a] = -1

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

print(dp[n]%(10**9+7) if dp[n]!=-1 else 0)

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
n,m=map(int,input().split())
if m==0:
    x=1
    y=2
    for i in range(n-2):
        if x<y:
            x+=y%1000000007
        else:
            y+=x%1000000007
    print(max(x,y)%1000000007)
    sys.exit()
a=list(int(input()) for i in range (m))

x=['']*n
if a[0]==1:
    x[0]=0
else:
    x[0]=1

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1
    else:
        x[1]=0
    

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1
    elif a[0]==2:
        x[1]=0


for z in range(m):
    x[a[z]-1]=0
        
if n>=3:
    for k in range(2,n):
        if x[k]!=0:
            x[k]=x[k-2]%1000000007+x[k-1]%1000000007
            
elif n==1:
    print(1)
    sys.exit()
    
elif n==2:
    print(x[0]+1)
    sys.exit()
    
print(x[n-1]%1000000007)

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

if m>=2:
	if a[0]!=2 and a[1]!=2:
		x[1]=x[0]+1

if m==1:
    if a[0]!=2:
	       x[1]=x[0]+1

if n>3:
    for k in range(2,n):
        for z in range(m):
            x[a[z]-1]=0
        x[k]=x[k-2]+x[k-1]
else:
    x[2]=x[1]+x[0]
print(x[n-1]%1000000

import sys

n,m=map(int,input().split())
broken=set(map(int,sys.stdin))

if n==1:
  print (1)
  sys.exit()
if n==2:
  if 1 not in broken and 2 not in broken:
    print (2)
  elif 2 in broken:
    print(0)
  elif 1 in broken and 2 not in broken:
    print(1)
  sys.exit()

way = [0]*n
if 1 not in broken:
  way[0]=1
if 1 not in broken and 2 not in broken:
  way[1]=2
elif 1 in broken and 2 not in broken:
  way[1]=1
for i in range(2,n):
  if i+1 in broken:
    way[i]=0
    continue
  way[i]=(way[i-1]+way[i-2])%1000000007
print(way[n-1])
  

Verdicts: Runtime Error

Runtime Error

Accepted