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):
broken_step = []
     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
for i in range(M):
    step_num = int(input().split()[0])
    broken_step.append(step_num)
        
        
dp = [0]*(N+1)
dp[0] = 1
if 1 in broken_step:
    dp[1] = 0
else:
    dp[0] = 1
     
for i in range(2, N+1):
    dp[i] = (dp[i-1]+dp[i-2])%1000000007 if i not in broken_step else 0
print(dp[N])


N, M = [int(s) for s in input().split()]
b = [0]*N
for _ in range(M):
    b[int(input().strip())-1] = 1

a = [0]*N

if b[0] == 0:
    a[0] = 1
if N > 1 and b[1] == 0:
    a[1] = 1 + a[0]

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

Verdicts: Wrong Answer

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

Submission attempts (in order):
from functools import lru_cache
dan,ana=map(int,input().split())
l=[int(input()) for _ in range(ana)]
@lru_cache(maxsize=float('inf'))
def f(x,*li):
  if x in li:return 0
  elif x==1:return 1
  elif x==2:return f(1,*li)+1
  else:return (f(x-1,*li)+f(x-2,*li))%(10**9+7)

print(f(dan,*l))

from functools import lru_cache
dan,ana=map(int,input().split())
l=[int(input()) for _ in range(ana)]
@lru_cache(maxsize=10000000)
def f(x,li):
  if x in li:return 0
  elif x==1:return 1
  elif x==2:return f(1,li)+1
  else:return (f(x-1,li)+f(x-2,li))%(10**9+7)

print(f(dan,l))

from functools import lru_cache
dan,ana=map(int,input().split())
l=[int(input()) for _ in range(ana)]
@lru_cache(maxsize=10000000)
def f(x,*li):
  if x in li:return 0
  elif x==1:return 1
  elif x==2:return f(1,li)+1
  else:return (f(x-1,li)+f(x-2,li))%(10**9+7)

print(f(dan,*l))

n,m=map(int,input().split())
l={int(input()) for i in range(m)}
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,1+n):
    if i not in l:dp[i]+=dp[i-1]+dp[i-2];dp[i]%=10**9+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,input1.split()))
A = list(map(int,input2.split()))

dp = []
dp.append(1) 
if 1 in A: 
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1): 
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N])  

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

dp = {i:0 for i in A}

dp[0]=1 

safe_stairs = list(range(1,N+1))
[safe_stairs.remove(a) for a in A]
  
for i in safe_stairs:  
  dp[i]=dp[i-1]+dp[i-2]
print(dp[N]%1000000007)  

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

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

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

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

print(dp[-1]%1000000007)    

Verdicts: Runtime Error

Runtime Error

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

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

n,m = map(int,input().split())
D=[1] * (n+1)
for _ in range(m):
    D[int(input())] = 0
for i in range(2, n+1):
    D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[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):
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 1000000007

zero_flag = False

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

print(max(blocks))
b_max = max(blocks)

c = [1, 1]
for i in range(2, b_max):
    ctmp = c[i - 1] + c[i - 2]
    c.append(ctmp % BIGNUM)

if 0 in blocks:
    ans = 0
else:
    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans *= c[num - 1]
        if ans >= BIGNUM:
            ans %= BIGNUM

print(ans)

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = 0
    blocks = list()
    for _ in range(m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

k = list()
last_ana = -1
for _ in range(m):
    ana = int(input())
    k.append(ana - last_ana - 1)
    last_ana = ana
k.append(n - last_ana)

if 0 in k:
    ans = 0
else:
    k_max = max(k)
    c = [1, 1]
    for i in range(2, k_max):
        c_tmp = c[i - 1] + c[i - 2]
        c.append(c_tmp % BIGNUM)

    ans = 1
    for num in k:
        ans *= c[num - 1]
        ans %= BIGNUM
        if ans == 0:
            break

print(ans)

Verdicts: Runtime Error

Wrong Answer

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

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

print(dp[n]%1000000007)

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

Verdicts: Runtime Error

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

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

def factorial(x):
  if x == 0:
    return 1
  else:
    return x * factorial(x-1)

def C(x,y):
    return factorial(x)//(factorial(x-y)*factorial(y))

def f(x):
    if x == 0:
        return 1
    else:
        ret = 0
        for i in range(x//2+1):
            ret += C(x-i,i)
        return ret

b = []
for i in range(m+1):
    b.append(a[i+1]-a[i]-2)

ans = 1
if -1 in b:
    print(0)
else:
    for j in b:
        ans *= (f(j)%1000000007)
    print(ans%1000000007)

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

for i in a:
    dp[i] = 0

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

print(dp[n])

Verdicts: Runtime Error

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

Submission attempts (in order):
n, m = map(int, input().split())

def fib(n):
    if n == 0:
        return 0
    else:
        a0 = 0
        a1 = 1
        for i in range(n-1):
            b = a1
            a1 += a0
            a0 = b
        return a1

count = 1
b = 0
for i in range(m):
    a = int(input())
    if a == 1:
        b = 1
        continue
    if num == 1:
        count *= 0
        break
    if b == 0:
        num = a - b
    else:
        num = a - b - 1
    count *= fib(num)
    b = a 
#     print(b, count, num)
    
count *= fib(n - b)

print(count%1000000007)

def main():
    n,m = map(int, input().split())
    stairs = [1]*(n+1)
    mod = 1000000007
    for _ in range(m):
        stairs[int(input())] = 0
    for i in range(2, n+1):
        stairs[i] = (stairs[i-2] + stairs[i-1]) * stairs[i]
    print(stairs[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):


D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1


s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(n):
    if (n == 0):
        return s0
    elif (n == 1):
        return s1
    elif(a[n] == 1):
        return 0
    else:
        return (calc(n-1) + calc(n - 2) % D

print(s[n])


import sys  
sys.setrecursionlimit(500*500)

D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1


s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        acc2 = (acc1 + acc2) % D if a[n - l + 2] == 0 else 0
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))


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

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

Verdicts: Runtime Error

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

Submission attempts (in order):
n,m=map(int,input().split())
d=[1]*(n+1)
for i in range(m):
    d[int(input())]=0
for i in range(n+1):
    if i >1:
        d[i]=(d[i-1]+d[i-2]%(10**9+7))*d[i]
print(d[n+1])

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

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


Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
def calc_pattern(stair_num, damaged_step_list, state_number):
    if stair_num == 1:
        return 1
    if stair_num == 3 and damaged_step_list==[1]:
        return 1
    
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        for i in range(1, N+1):
            if i+1 in a:
                continue
            else:
                answer = (answer * 2)%1000000007
            print(str(i) + ' ' + str(answer))
    print(answer)

import sys

sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = [-1] * MAX_N

def f(n, na_set):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        if len(na_set & set([1])) == 1:
            return 1
        return 2
    
    elif memo[n] != -1:
        return memo[n]
    else:
        is_next_damaged = False
        is_2next_damaged = False

        if len(na_set & set([n-1])) == 1:
            is_next_damaged = True
        if len(na_set & set([n-2])) == 1:
            is_2next_damaged = True
        if is_next_damaged == True and is_2next_damaged == False:
            res = f(n-2, a_list)
        if is_next_damaged == False and is_2next_damaged == True:
            res = f(n-1, a_list)
        if is_next_damaged == False and is_2next_damaged == False:
            res = f(n-1, a_list) + f(n-2, a_list)

    
    memo[n] = res
    return res

if __name__ == '__main__':
    N, M = map(int, input().split())
    a_list = [int(input()) for i in range(M)]
    na_set = set([N-a for a in a_list])
    
    divided_by = 1000000007

    answer = -1

    
    min_diff = sys.maxsize
    for i in range(1, len(a_list)):
        min_diff = min(min_diff, a_list[i] - a_list[i - 1])

    if min_diff == 1:
        answer = 0
    else:
        
        answer = f(N, na_set)%divided_by

    print(answer)


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

   MOD = 1000000007


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

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

   print(dp[n])


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 = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
dis = []
for _ in range(M):
    dis.append(input())

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0 
    else:
        if i in dis and i+1 in dis:
            dp[i+2]=0 
        else:
            if i in dis :
                dp[i+2]=dp[i+1]%1000000007
            elif i+1 in dis :
                dp[i+2]=dp[i]%1000000007
            else :
                dp[i+2]=dp[i]%1000000007+dp[i+1]%1000000007

print(dp[N])

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

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]
        if i+1 in dis :
            dp[i+2]=dp[i]
        else :
            dp[i+2]=dp[i]+dp[i+1]

print(dp[N])

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

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]%1000000007
        if i+1 in dis :
            dp[i+2]=dp[i]%1000000007
        else :
            dp[i+2]=dp[i]%1000000007+dp[i+1]%1000000007

print(dp[N])

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

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]
        if i+1 in dis :
            dp[i+2]=dp[i]
        else :
            dp[i+2]=dp[i]+dp[i+1]

print(dp[N])

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


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = 1
        else:
            dp[i] = 1
    else:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] = dp[i] % 1000000007
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

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

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

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

A.sort()
ida = 0
a = A[ida]
mod = 10**9 + 7

x = [1] + [0]*N
if a == 1:
  ida += 1
  if M >= 2:
    a = A[ida]
  else:
    x[1] = 1

for i in range(2, N+1):
  if i == a:
    ida += 1
    if ida >= M:
      a = N+1
    else:
      a = A[ida]
  
    x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2]) % mod

print(x[N])

N, M = map(int, input().split())
x = [1] + [0] * N
mod = 10**9 + 7

if M > 0:
  A = []
  for i in range(M):
    A.append(int(input()))

  A.sort()
  ida = 0
  a = A[ida]
  if a == 1:
    ida += 1
    if M >= 2:
      a = A[ida]
    else:
      x[1] = 1

  for i in range(2, N+1):
    if i == a:
      ida += 1
      if ida >= M:
        a = N+1
      else:
        a = A[ida]

      x[i] = 0
    else:
      x[i] = (x[i-1] + x[i-2]) % mod
else:
  for i in range(2, N+1):
    x[i] = (x[i-1] + x[i-2]) % mod

print(x[N])

N, M = map(int, input().split())
x = [1] + [0] * N
broken = [False] * (N+1)
mod = 10**9 + 7

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

if not broken[1]:
  x[1] = 1

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

print(x[N])

Verdicts: Runtime Error

Wrong Answer

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

Submission attempts (in order):
n, m = map(int, input().split())

# a = set()

#     a_tmp = int(input())
#     a.add(a_tmp)

a = [1 for i in range(m)]

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


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

"""
100 5
1
23
45
67
89
"""


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

dp = [0] * (n + 1)

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

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""


n, m = map(int, input().split())
# A = set()

#     a = int(input())
#     A.add(a)
a = set()
for i in range(m):
    a.append(int(input()))
    A = a
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

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

"""
100 5
1
23
45
67
89
"""

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

a = set()
for i in range(m):
    a_tmp = int(input())  # int(input())
    a.add(a_tmp)



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


Verdicts: Wrong Answer

Runtime Error

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())
s=[]
for i in range(m):
    s.append(int(input()))
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l)

n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*(n)
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and s[0]== 1:l[1]=0
else:l[1]=1

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

n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*n
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and 1 in s:l[1]=0
else:l[1]=1
for i in range(2,n+1):
    if i in s: l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-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=[]
for i in range(m):
    a.append(int(input()))
res=1
count=0
for i in range(n):
    if i+1 in a and i+2 in a:
            res=0
            break
    else:
        if i not in a:
            if i<n-1:
                if i+1 not in a:
                    count+=1
                if i+2 not in a:
                    count+=1
                res=res*count
                print(count)
                count=0
print((res)%1000000007)

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
for i in range(m):
    dp[n-a[i]]=-1
if dp[1]==0:
    dp[1]=1
else:
    dp[1]=0
if n>1:
    if dp[2]==0:
        dp[2]=dp[1]+1
    else:
        dp[2]=0
if n>=3:
    for i in range(3,n+1):
        if dp[i]==0:
            dp[i]=dp[i-1]+dp[i-2]
        else:
            dp[i]=0
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):
import math
def calc_pattern(stairs):
    if stairs<=4:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return (sum(l))%1000000007
N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
s=1
for m in range(M+1):
    if A[m+1]==1 or A[m]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
		s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
print(int(s))


N,M=map(int,input().split())
A=[int(input()) for n in range(M)]
S=[1]*(N+1)
for a in A:
  S[a]=0
for i in range(2,N+1):
  S[i]=(S[i-1]+S[i-2])%1000000007*S[i]

print(S[-1])

Verdicts: Runtime Error

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

Submission attempts (in order):
n,m=map(int,input().split())
a=list(map(int,input().split()))
fib=[0,1]
for i in range(n):
  fib.append(fib[i]+fib[i+1])
b=[]
for j in range(m):
  b.append(fib[a[m]-1])
ans=0
for t in range(m-1):
  ans+=(b[t]*b[t+1])%(10**9+1)
print(ans%(10**9+1))

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
fib=[0,1]
for i in range(n):
  fib.append(fib[i]+fib[i+1])
b=[]
for j in range(m):
  b.append(fib[a[j]-1])
ans=0
for t in range(m-1):
  ans+=(b[t]*b[t+1])%(10**9+1)
print(ans%(10**9+1))

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

Verdicts: Runtime Error

Runtime Error

Runtime Error

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

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    elif steps <= 1:
        patern_nmu = 1
    else:
        p, q = 1, 0
        for j in range(steps-1):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)


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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    else:
        p, q = 1, 0
        for j in range(steps):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

Verdicts: 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 M == 0:
    alist = set()
else:
    alist = set(map(int, input()) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])


import sys

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

if M == 0:
    alist = set()
else:
    alist = set(map(int, sys.stdin) for _ in range(M))

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1 if 1 not in alist else 0

MOD = 10**9 + 7
for i in range(2, N + 1):
    if i in alist:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[N])


import sys

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

broken = set(map(int, sys.stdin))

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

Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
n, m = list(map(int, input().split()))
aaa = list(int(input()) for i in range(m))

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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


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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if not broken[1] else 0
MOD = 10 ** 9 + 7

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

print(dp[n])


Verdicts: Wrong Answer

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

Submission attempts (in order):

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

s = [0] * (N+1)

for i in range(M):
    ai = int(input())
    s[ai] = -1

print(s)

s[0] = 1

if N == 1:
    print(1)
else:
    if s[1] == 0:
        s[1] = 1

    for i in range(2,N+1):
        if s[i] >= 0:
            s[i] += (max(0,s[i-1]) + max(0,s[i-2]))
        print(s)

    print(s[N] % 1000000007)

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

s = [0] * (N+1)

for i in range(M):
    ai = int(input())
    s[ai] = -1

s[0] = 1

if N == 1:
    print(1)
else:
    if s[1] == 0:
        s[1] = 1

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

    print(s[N] % 1000000007)

Verdicts: Runtime Error

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

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

n,m = map(int, input())
a = set()
for i in range(m):
  a.add(int(input()))
  
b = [0]* (n+1)
b[0] = 1
if 1 not in a:
  b[1] = 1
for i in range(2, n+2):
  if i in a:
    b[i] = 0
  else:
    b[i] = b[i-1] + b[i-2]
print(b[n] % 1000000007)

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

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

Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=1 if 1 not in broken else 0

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])


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

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

if dp[1]!=-1:
  dp[1]==1

for i in range(2,len(dp)):
  if dp[i]==-1:
    continue
  else:
    dp[i]=(max(dp[i-2],0)+max(dp[i-1],0))%1000000007
    if dp[i]==0:
      print(0)
      break
else:  
  print(dp[-1])


import sys
readline = sys.stdin.readline

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

broken = set([int(readline()) for i in range(M)])

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in broken:
  dp[1] = 1
  
DIV = 10 ** 9 + 7

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

Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
n, m = list(map(int, input().split(' ')))
aaa = [0] * (n + 3)
for i in range(m):
    aaa[int(input())] = True

dp = [1] * (n + 3)
for i in range(1, n+1):  # 1e5
    if not aaa[i]:
        dp[i]  = dp[i-1]
        dp[i] += dp[i-2]
        dp[i] = dp[i] % int(1e9 + 7)
    else:
        dp[i] = 0
print(dp[n])

n, m = list(map(int, input().split(' ')))
aaa = [0] * (n + 3)
for i in range(m):
    aaa[int(input())] = True

dp = [1] * (n + 3)
for i in range(1, n+1):  # 1e5
    if not aaa[i]:
        dp[i]  = dp[i-1]
        if i >= 2:
            dp[i] += dp[i-2]
        dp[i] = dp[i] % int(1e9 + 7)
    else:
        dp[i] = 0
print(dp[n])

Verdicts: Wrong Answer

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

Submission attempts (in order):
#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

N = int(input())
X,Y = map(int, input().split())


L = list(map(int, input().split()))


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

#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

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

ans = [1,1]+[0]*(N-1)
for a in A:
    ans[a]=-1

for i in range(2,N+1):
    if ans[i]!=-1:
        if ans[i-2]!=-1:
            ans[i]=(ans[i]+ans[i-2])%MOD
        if ans[i-1]!=-1:
            ans[i]=(ans[i]+ans[i-1])%MOD

print(ans[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)]
a.insert(0,0)
a.append(n)
b=[a[i+1]-a[i] for i in range(m+1)]
ans=1
z=[1,2]
for i in range(10**5):
    z.append(z[i]+z[i+1])
for i in b:
    if i!=0:
        ans =ans*z[i-1]
    if i==0:
        ans=0
print(ans%1000000007)  

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a.insert(0,0)
a.append(n)
b=[a[i+1]-a[i] for i in range(m+1)]
ans=1
z=[1,2]
for i in range(10**5):
    z.append(z[i]+z[i+1])
for i in b:
    ans =ans*z[i-1]
print(ans%1000000007) 

n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if a[0]==1 and a[1]==2:
        continue
    elif a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
        b[1],b[2]=1,2        
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

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

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

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

Submission attempts (in order):
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i):
    c, b = 1, 0
    while i > 0:
        c, b = c + b, c
        i -= 1
    return c
m = a[0] + 1
num = fibo(m - 2)
if M > 1 :
    for i in range(M - 1):
    m = a[i + 1] - a[i]
    if m > 1:
        num = num * fibo(m - 2)
    else:
        num = 0
        break
    num = num * fibo(N - a[M - 1] - 1)
elif M == 1:
    num = num * fibo(N - a[M - 1] - 1)
else :
    num = fibo(N)
print(num % 1000000007)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0, 1:
        memo[i]=1
        return memo[i]
    else:
        if i in memo.keys():
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0:
        return 1
    elif i == 1:
        return 1
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2, memo)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2, memo)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1, memo)
print(num % 1000000007)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
def fibo(i, memo={}):
    if i == 0, 1:
        memo[i] = 1
        return memo[i]
    else:
        if i in memo:
            return memo[i]
        else:
            memo[i] = fibo(i-1, memo) + fibo(i-2, memo)
            return memo[i]
m = a[0] + 1
num = fibo(m - 2)
for i in range(M - 1):
    m = a[i + 1] - a[i]
    num = num * fibo(m - 2)
    if m == 1:
        num = 0
        break
num = num * fibo(N - a[M - 1] - 1)
print(num % 1000000007)


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

Verdicts: Runtime Error

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

if N==1:
    print(1)
    exit()

f=[0]*(N+1)

if chk[1]:
    f[1]=1
else:
    f[1]=0


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

print(f[N])

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

a=[]
for i in range(M):
    a.append(int(input()))
a.sort(reverse=True)

DP=[1]*(N+1)

if len(a)>0 and 1==a[-1]:
    DP[1]=0
    a.pop()


for i in range(2,N+1):
    if len(a)>0 and i==a[-1]:
        DP[i]=0
        a.pop()
        if DP[i-1]==0:
            print(0)
            exit()
    else:
        DP[i]=DP[i-1]+DP[i-2]
        DP[i]=DP[i]%mod

print(DP[N])


Verdicts: Wrong Answer

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

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

from collections import deque

n,m=map(int,input().split())
A={int(input()) for _ in range(m)}
L=deque([1,1])
if 1 in A:L[1]=0
for i in range(2,n+1):
    if i in A:
        L.append(0)
    else:
        L.append(L[i-2]+L[i-1])
print(L[n]%(10**9 + 7))


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)]
f=[1]
for i in range(1,n+1):
    if i in a:f.append(0)
    else:f.append(f[i-1]+f[i-2])
print(1 if n==1 else f[-1]%1000000007)

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

Verdicts: Wrong Answer

Accepted