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=list(map(int,open(0).read().split()))

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

for j in range(M):
    b[a[j]]=-1

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

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

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

for j in range(M):
    b[a[j]]=-1

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

Verdicts: Runtime Error

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

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

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

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

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

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):
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=list(range(N+1))

res=[1,1]
for i in range(10**5):
    res.append(res[-1]+res[-2])

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if (a-start)==1:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    print(sum)
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=list(range(N+1))

res=[1,1]
for i in range(10**5):
    res.append(res[-1]+res[-2])

sum=1
start=0
judge=True

for i in range(M):
    a=int(input())
    if a==start:
        if start==0:
            pass
        else:
            judge=False
            break
    sum*=res[a-start-1]
    start=a+1
sum*=res[N-start]

if judge:    
    print(sum%(10**9+7))
else:
    print(0)

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())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

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

if len(A) and len(A) != 1:
    for i in range(2, N+1):
        if i != A[idx]:
            dp[i] = (dp[i-1] + dp[i-2]) % P
        else:
            dp[i] = 0
            if idx < M-1:
                idx += 1
else:
    for i in range(2, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[N])

N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

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

if len(A):
    for i in range(2, N+1):
        if i != A[idx]:
            dp[i] = (dp[i-1] + dp[i-2]) % P
        else:
            dp[i] = 0
            if idx < M-1:
                idx += 1
else:
    for i in range(2, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % P
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 sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

import sys
def input(): return sys.stdin.readline().rstrip()
    
def main():
    n,m=map(int,input().split())
    A=[int(input())for _ in range(m)]
    flag=[True]*(n+2)
    for a in A:
        flag[a]=False
    mod=10**9+7
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(n):
        if flag[i+1]:
            dp[i+1]+=dp[i]%mod
        if flag[i+2] and i<n-1:
            dp[i+2]+=dp[i]%mod
    print(dp[n]%mod)

if __name__=='__main__':
    main()

Verdicts: Runtime Error

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

Submission attempts (in order):
import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if 1 in p:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if 1 in p:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if p[1] == 1:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
N, M = map(int, input().split())
a = [int(input())-1 for _ in range(M)]
mod =  1000000007
ret = [0] * N
for i in range(N):
    if i in a:
        continue
    elif i < 2:
        ret[i] = ret[i]+1
    else:
        ret[i] = ret[i-2] + ret[i-1]
        if ret[i] == 0:
            break


print(ret[len(ret)-1]%mod)


N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%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):
import numpy as np

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

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
    else:
        cost = np.zeros(N + 1, dtype=np.int64)
        cost[0] = 1
        cost[1] = 1
        cost[A] = 0
        cost[2] = cost[0] + cost[1]

        for i in range(1, N + 1):
            cost[A] = 0
            cost[i] = (cost[i - 1] + cost[i - 2]) % q

        print(cost[-1] % q)


import sys
import numpy as np
import math

N, M = list(map(int, input().split()))
A = np.zeros(M)

for i in range(M):
    A[i] = int(input())



for i in range(M-1):
    if A[i] == A[i+1]-1:
        print(0)
        sys.exit()


d = np.zeros(M+1)

for i in range(M-1):
    d[i+1] = A[i+1] - A[i] - 2

d[0] = A[0] - 1
d[-1] = N - A[-1] - 1


p = np.zeros(M+1)

for i in range(M+1):

    n = int(d[i] // 2)

    for j in range(1,n+1):
        
        
        n1 = d[i] - 2*j
        pp = math.factorial(n1+j)/(math.factorial(j) * math.factorial(n1))
        p[i] += pp

    p[i] += 1

mm = 1000000007
p = p % mm

print(int(np.prod(p) % mm))

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

if N == 1:
    if M == 0:
        print(1)
    elif M == 1:
        print(0)
else:
    cost = [0 for _ in range(N + 1)]
    cost[0] = 1

    cnt = 0
    A.append([0])
    for i in range(1, N + 1):
        if i == A[cnt]:
            cnt += 1
            continue
        else:
            cost[i] = cost[i - 1] + cost[i - 2]

    print(cost[-1] % q)


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):
#dp
n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0
line = []
for i in range(n+1):
    if ln[i] ==0
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        line.append((line[-1] + line[-2]) % mod_1)
print(line[-1])


#dp
n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0

for i in range(n+1):
    if ln[i] ==0
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        ln.append((ln[-1] + ln[-2]) % mod_1)
print(ln[-1])


#dp
n,m  = map(int,input().split())
ln = [-1 for i in range(n +1)]
mod_1 = 10**9 + 7
for i in range(m):
    ln[int(input())] = 0
#print(ln)
for i in range(n+1):
    if ln[i] ==0:
        pass
    elif i == 0:
        ln[i] = 1
    elif i == 1:
        ln[i] = 1
    else:
        ln[i] = (ln[i-1] + ln[i-2]) % mod_1
#print(ln)
print(ln[-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):
N,M = map(int,input().split())
a = set([int(input()) for i in range(M)])
dp = [0]*(N+1)
dp[1] = 1

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



N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
dp = [0]*(N+1)
dp[1] = 1
if 1 in a:
    dp[2] = 1
    dp[1] = 0
else:
    dp[2] = 2
for i in range(3,N+1):
    if i-1 in a:
        continue
    
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
ans = dp[N]
print(ans)


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



Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
N, M = map(int, input().split())
A = set(list(int(input()) for _ in range(M)))



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

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


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



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

for i in range(1, N+1):
    dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
    if i in A:
        dp[i] = 0
print(dp[-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):
import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    for x in range(stg+1):
      if (stg - x) % 2 == 0:
        y = (stg - x) / 2
        tmp += math.factorial(x+y) / (math.factorial(x) * math.factorial(y))
    
    ans_list.append(int(tmp))
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
    
  print(ans)
else:
  print(0)


import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False
    break

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    for x in range(stg+1):
      if (stg - x) % 2 == 0:
        y = (stg - x) / 2
        tmp += math.factorial(x+y) / (math.factorial(x) * math.factorial(y))
    
    ans_list.append(int(tmp))
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
  print(ans)
else:
  print(0)

# input
stairs, broken = map(int, input().split())
conditions = [1] * (stairs + 1)
for i in range(broken):
  tmp = int(input())
  conditions[tmp] = 0
  
# main
for i in range(2, stairs+1):
  conditions[i] *= (conditions[i-1] + conditions[i-2]) % (10**9+7)

print(conditions[stairs])

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




N,M=map(int,input().split())
dp=[1]*(N+1)
for _ in range(M):
  i=int(input())
  dp[i]=0
for i in range(2,N+1):
  if dp[i]!=0:
      dp[i]=dp[i-1]+dp[i-2]
  dp[i]%=1000000007
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
    def cmb(n, r):
        return math.factorial(n)// ( math.factorial(n-r) * math.factorial(r) )
     
     
     
    N,M = input().split()
     
    N = int(N)
    M = int(M)
     
    a = []
    ans = 1
     
    for i in range(M):
        newa = int(input())
        a.append(newa)
     
    if (M != 0):
        for k in range(M-1):
            if (a[k+1] - a[k] == 1):
                ans = 0
                
        
        
        for i in range(M + 1):
        
     
            if (i == 0):
                dan = a[i] - 1
            elif (i == M):
                dan = N - a[i - 1] - 1
            else:
                dan = a[i] - a[i - 1] - 2
     
            abletwo = (dan - (dan % 2)) // 2
            now = 0
     
            if (dan != 0):
     
                for j in range(abletwo + 1):
     
                    now += cmb (dan - j , j )
     
            else:
                now = 1
            
            ans *= now
     
    else:
        ans = 0
        abletwo = (N - (N % 2)) // 2
     
        for j in range(abletwo + 1):
     
            ans += cmb (N - j , j )
     
    ans = ans % 1000000007
    print (ans)


N, M = input().split()

N = int(N)
M = int(M)
a = []
c = []

for i in range(M):

    anew = int(input())
    a.append(anew)

now_a = 0
a.append(-1)
ans = 0

for i in range( N + 1 ):

    if (i == 0):
        c.append(1)
        
    elif (i == 1):

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append(1)

    else:

        if (a[now_a] == i):
            c.append(0)
            now_a += 1
        else:
            c.append( c[i - 1] + c[i - 2])
        

ans = c[N] % 1000000007

print (ans)
    


Verdicts: Runtime Error

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

Submission attempts (in order):
from math import factorial
import sys
N,M=map(int,input().split())
ANS1=1
ANS2=1
ANS3=1
A=int(input())
list1=[A]
DAN=A
B=DAN-DAN//2
for k in range(B):
  a = factorial(B) / factorial(k+1) / factorial(B - (k+1))
  ANS1+=a
for i in range(1,M):
  ans2=1
  A=int(input())
  list1+=[A]
  DAN=A-list1[i-1]-1
  B=DAN-DAN//2
  if A==list1[i-1] or A==list1[i-1]+1 and M!=1:
    print(0)
    sys.exit()
  for k in range(B):
    a = factorial(B) / factorial(k+1) / factorial(B - (k+1))
    ANS2+=a
  ANS3*=ANS2
DAN=N-A-1
B=DAN-DAN//2
for t in range(B):
  a = factorial(B) / factorial(t+1) / factorial(B - (t+1))
  ANS3+=a
ANS=ANS1*ANS2*ANS3  
print(int(ANS)%1000000007)

N,M=map(int,input().split())
dp=[1]*N
listA=[]
for i in range(M):
  a=int(input())
  listA+=[a]
  dp[a-1]=0
setA=set(listA)    
if (1 not in setA) and (2 not in setA) and N!=1:
  dp[1]=2
for i in range(2,N):
  if i+1 not in setA:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[-1]%(10**9+7)
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())
for _ in range(M):
  a.append(input())

S = [0] * (N+1)
for n in range(N+1):
    if str(n) in a:
        S[n] = 0
    elif n<=1:
        S[n] = 1
    else:
        S[n] = S[n-1] + S[n-2]

N,M = map(int,input().split())
a = [True] * (N+1)

for _ in range(M):
  a[int(input())] = False

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if a[n]==False:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[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):
memo = [0]*10**6 
def fib(n):
    if n in a:
        return 0
    if n<=1:
        return 1 
    if memo[n] != 0:
        return memo[n] 
    memo[n] = fib(n-1) + fib(n-2) 
    return memo[n]

print(fib(i)%1000000007)


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

for i in range(m):

    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True





if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+1)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    
    

    print(ans)



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

for i in range(m):

    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+2)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    
    

    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())
breaks = []
for _ in range(m):
  breaks.append(int(input())-1)
stairs = [0 for _ in range(n)]

if n == 1:
  print(1)
else:
  if 0 not in breaks:
    stairs[0]=1

  if 1 not in breaks:
    stairs[1]=1  

  for i in range(n):
    if i+1 not in breaks:
      if i+1>=n:
        pass
      else:
        stairs[i+1]=stairs[i]+stairs[i+1]
    if i+2 not in breaks:
      if i+2>=n:
        pass
      else:
        stairs[i+2]=stairs[i]+stairs[i+2]
    if len(n)>3:
      if sum(stairs[-3:]) == 0:
        break

  print(stairs[-1]%1000000007)
  

n, m = map(int, input().split())
stairs = [1]*(n+1)
for _ in range(m):
  stairs[int(input())] = -1

flg = False
for i in range(2,n+1):
  if stairs[i]==-1:
    pass
  elif stairs[i-1]==-1 and stairs[i-2]==-1:
    flg=True
    break
  elif stairs[i-1]==-1:
    stairs[i] = stairs[i-2]
  elif stairs[i-2]==-1:
    stairs[i] = stairs[i-1]
  else:
    stairs[i] = stairs[i-1] + stairs[i-2]
if flg:
  print(0)
else:
  print(stairs[-1]%1000000007)

Verdicts: Runtime Error

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

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

from collections import defaultdict
N, M = map(int, input().split())
A = {i:0 for i in range(N+1)}
for _ in range(M):
  A[int(input())] = 1

mod = 10**9 + 7
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  if A[i+1] != 1: 
    dp[i+1] += dp[i]
    dp[i+1] %= mod
  if i+2 >= N+1:
    continue
  if A[i+2] != 1:
    dp[i+2] += dp[i]
    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(' '))
a = []
for i in range(m):
    a.append(int(input()))

def t(current, n):
    if current == n:
        return 1
    if current in a:
        return 0
    p1, p2 = 0, 0
    if current + 1 not in a:
        p1 = t(current + 1, n)
    if current + 2 <= n and current + 2 not in a:
        p2 = t(current + 2, n)
    return p1 + p2

result = 1
a.append(n - 1)
for index in range(len(a)):
    if index == 0:
        a1 = 0
    else:
        a1 = a[index - 1] + 1
    a2 = a[index] + 1
    p_step1 = t(a1 + 1,  a2)
    p_step2 = t(a1 + 2,  a2)
    result = (result * (p_step1 + p_step2)) % 1000000007
 
print(result)


n, m = map(int, input().split(' '))
a = set()
for i in range(m):
    a.add(int(input()))


s = [0] * (n + 1)
s[0] = 1
for i in range(n):
    j = i + 1
    while(j <= min(n, i + 2)):
        if j not in a:
            s[j] += s[i]
            s[j] = int(s[j] % 1000000007)
        j += 1

print(s[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 = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n == 0 :
    return 1
  elif n == 1 :
    return 2
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

N, M = map(int,input().split(' '))
a = [int(input()) for i in range(M)]
for i in range(M-1):
  if a[i]+1 == a[i+1]:
    print(0)
    exit()
def step(n):
  if n <= 1 :
    return 1
  tmp = [0]*n
  tmp[0] = 1
  tmp[1] = 2
  for i in range(2,n):
    tmp[i] = tmp[i-2] + tmp[i-1]
  return tmp[n-1]
ans = step(a[0]-1)
for i in range(1,M):
  n = a[i] - a[i-1] - 2
  ans = ans*step(n)
n = N - a[M-1] -1
ans = ans*step(n)

print(ans%(10**9+7))
print([step(i) for i in range(6)])

N, M = map(int,input().split(' '))
a = set([int(input()) for i in range(M)])
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
  if i in a:
    ans[i] = 0
  else:
    ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[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()))
 
dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    print(now, dp[now])
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

n, m = map(int, input().split())
 
a = []
for i in range(m):
    a.append(int(input()))
 
dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

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

a = []
for i in range(m):
    a.append(int(input()))
a = set(a)

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[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):
import queue
q=queue.Queue()
l=[]
n,m=map(int,input().split())
for i in range(m):
  p=int(input())
  q.put(p)
que=q.get()
for j in range(n+1):
  if j==0:
    l.append(1)
  elif j==1 and que!=1:
    l.append(1)
  elif j==que:
    l.append(0)
    que=q.get()
  else:
    l.append(l[j-2]+l[j-1])
print(l[n]%(10**9+7))

n,m=map(int,input().split())
broken=[]
for i in range(m):
  broken.append(int(input()))
b=set(broken)
l=[1]
for j in range(1,n+1):
  if j in b:
    l.append(0)
  elif j==1:
    l.append(1)
  else:
    l.append(l[j-2]+l[j-1])
print(l[n]%(10**9+7))

Verdicts: Time Limit Exceeded

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

Submission attempts (in order):
import numpy as np
from math import factorial
import math, sys

N, M = map(int, input().split())
A = [None]*M

for i in range(M):
    A[i] = int(input())

tmp = 0
x = []

for i, a in enumerate(A):
    x.append(a-tmp-1)
    tmp = a + 1

x.append(N - tmp)
    
x = np.array(x)
if x[1:].min()<1:
    print(0)
    sys.exit()

def calc_combi(a):
    ans = 0
    for i in range(int(a/2)+1):
        tmp_n = math.ceil(a/2)+i
        tmp_r = a - tmp_n
        ans += factorial(tmp_n) // factorial(max(tmp_r, tmp_n - tmp_r))                        
    return ans

memo =  list(map(lambda x: calc_combi(x), x))

ans = 1
for m in memo:
    ans = ans * m % 1000000007

n, m = map(int, input().split())
arr = 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):
    if not i in arr:
        if i == 1:
            dp[i] = dp[i - 1] % MOD
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])

Verdicts: Runtime Error

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

Submission attempts (in order):
import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 1
r2 = []
f1 = False
for i2 in range(n1):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        r2.append(r1)
        r1 = 1
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
print(r2)
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

import sys

n1, n2 = [int(i) for i in input().split()]

na1 = []

for i1 in range(n2):
    na1.append(int(input()))

for i3 in range(n2):
    if i3 == 0:
        continue
    else:
        if na1[i3] == na1[i3 - 1] + 1:
            print("0")
            sys.exit()

n3 = 0
n4 = 0
n5 = 0
n6 = 0
n7 = 0
r1 = 1
r2 = []
f1 = False
for i2 in range(n1):
    if len(na1) > n7 and (na1[n7] == i2 + 1 ):
        n3 = 0
        n4 = 0
        n6 = 0
        n7 += 1
        r2.append(r1)
        r1 = 1
        f1 = True

    else:
        if f1 == True:
            f1 = False
            continue
        if n4 == 0 :
            n4 = 1
            r1 = 1
        elif n3 == 0 :
            n3 = 1
            n4 = 2
            r1 = 2
        else:
            n6 = n3 + n4
            r1 = n6
            n3 = n4
            n4 = n6
    if i2 == (n1 - 1) :
        r2.append(r1)

r3 = 1
for i6 in range(len(r2)):
    r3 *= r2[i6]

print(r3 % 1000000007)

Verdicts: Wrong Answer

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

Submission attempts (in order):
import math
N,M=map(int,input().split())

a1=int(input())
a2=a1
data=[a1]
ans_data=[]
for i in range(M-1):
  a1=a2
  a2=int(input())
  #print("a",a2-a1-1)
  data.append(a2-a1-1)
  
data.append(N-a2-1)
  
data=sorted(data)
#print(data)
if  data[0]==0:
  print(0)
  
elif data[M]==1:
  print(1)
else:
  mm=data.count(1)
  ma=2
  #print("mm=",mm)
  f1=1
  f2=2
  for i in range(0,data[M]+len(data)-2-mm):  
      
    if ma==data[mm]:
      ans_data.append(f2)
      #print("data[mm]",data[mm],"f2",f2,"i",i)
      mm=mm+1
     
    else:
      ma=ma+1
      f11=f1
      f1=f2
      f2=f1+f11
      #print("data[mm]",data[mm],"f2",f2,"ma",ma)
        
        
  ans=1
  #print("ans_data",ans_data)
  for i in range(0,len(ans_data)):
    ans=ans*ans_data[i]
    
  mod=10**9+7
  print(ans%mod)
    
    
    
    

N,M=map(int,input().split())
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
A=set(A)
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
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):
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
d = [0]*N
d[0] = 1
d[1] = 1
def func(N):
    if d[N] > 0:
        return d[N]
    d[N] = func(N-1) + func(N-2)
    return d[N]
if M == 0:
    print(func(N)/%1000000007)
    sys.exit()

for i in range(M-1):
    if A[i+1] == A[i]+1:
        print(0)
        sys.exit()
        

A = [-1] + A + [N+1]

B = [A[i+1]-A[i]-2 for i in range(M+1)]
ans = 1
for i in range(M+1):
    ans = ans * func(B[i])
ans = ans%1000000007
print(ans)

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

for i in range(1,n+1):
  if i==a[j]:
    j+=1
  elif i>1:
    dp[i] = (dp[i-1] + dp[i-2])%MOD 
  else:
    if i!=a[0]:
      dp[i] = dp[i-1]

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

n = 100

m = 5

a = [1, 23, 45, 67, 89]


INIT = 0

dp = [INIT for i in range(n + 1)]


dp[0] = 1


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


print(dp[n] % 1000000007)

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

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

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

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

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

mod=10**9+7

dp=[0]*(N+1)

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

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

import math
total_case = 1
for m in range(M+1):
  a1 = A[m]
  a2 = A[m+1]
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = int(math.factorial(jump1 + jump2)) / (int(math.factorial(jump1)) * int(math.factorial(jump2)))
    case += c
  total_case *= case
else:
  ans = total_case % (10**9 + 7)
  print(ans)

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())
  M -= 1

C = [1, 0] 
C += [0]*(N+10) 
for n in range(0, N+1):
  if n != a or M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # n == a and M != 0:
    C[n+2] = 0
    a = int(input())
    M -= 1

ans = C[N+2]  % 1000000007
print(ans)

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] 
C += [0]*(N+10) 
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # M > 0:
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: # n == a:
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)

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=mp(int,input().split())
a=[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
else:
  dp[1]=0
  

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


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
else:
  dp[1]=0
  

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



Verdicts: Runtime Error

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

Submission attempts (in order):
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
j = 0
if 1 == a[j]:
    dp.append(0)
    j += 1
else:
    dp.append(1)

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

print(dp[n]%(1000000007))

n, m = map(int,input().split())
a = []
pam = -1


def fib(k):
    if k<0:
        return 0
    elif k==0 or k==1:
        return 1
    else:
        return fib(k-1)+fib(k-2)


for i in range(0,m):
    am = int(input())
    a.append(am-pam)
    pam = am
a.append(n+1-pam)
count = 1
for aa in a:
    count = count * fib(aa-2)
print(a)
print(count%(1000000007))

n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
if m == 0:
    a.append(-1)
j = 0
k = len(a)-1
if 1 == a[j]:
    dp.append(0)
    j = min(k,j+1)
else:
    dp.append(1)

for i in range(2,n+1):
    if i == a[j]:
        dp.append(0)
        j = min(k,j+1)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))

Verdicts: Runtime Error

Runtime Error

Accepted