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):
MOD = 1e9 + 7

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

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

dp[0] = 1
if issafe[1]:
    dp[1] = 1

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


MOD = 1000000007

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

dp = [0] * (n + 1)
dp[0] = 1
# i=now, j=next
for i in range(n):
    for j in range(i+1, min(n, i + 2) + 1):
        if not oks[j]:
            continue
        dp[j] += dp[i]
        dp[j] %= 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())
c = [True]*(n+1)
for _ in range(m):
    c[int(input())] = False
d = [0]*(n)
if c[1] : d[1] = 1
if c[2] : d[2] = d[1] + 1
for i in range(3,n+1):
    if c[i] : d[i] = ( d[i-1] + d[i-2] ) % 1000000007
print(d[n])

def resolve():
    n,m= map(int,input().split())
    a = [int(input()) for _ in range(m)]
    d = [0]*(n+1)
    if not 1 in a : d[1] = 1
    if not 2 in a : d[2] = d[1] + 1
    for i in range(3,n+1):
        if not i in a :
            d[i] += d[i-1] + d[i-2]
    print(d[i]%1000000007)

# DP
mod = 1000000007
 
n, m = map(int, input().split())
b_list = [True] * (n+1)
dp = [0 for _ in range(n+1)]
for i in range(m):
    b_list[int(input())] = False
 
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if b_list[j] == True:
            dp[j] += dp[i]
            dp[j] %= mod
# print(b_list)
# print(dp)
print(dp[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())
dp=[0]*(n+3)
for i in range(m):
    dp[int(input())]=-1

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

print(dp[n]%1000000007)

n,m=map(int,input().split())
dp=[0]*(n+3)
dp[0]=1
for i in range(m):
    dp[int(input())]=-1

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

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

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    # mems = [False] * (N+1)

    cnts = [False] * (N+1)
    for i in range(N+1):
        c = 0
        if i in As:
            c = 0
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = cnts[i-2] + cnts[i-1]
        cnts[i] = c
        print("cnt[{}] = {}".format(str(i), str(c)))

    print(cnts[N]%1000000007)
    
    #     if i in As and i+1 in As:
    #         return 0 

    
    #     if target in As:
    #         return 0
        
    #     if target == 1:
    #         return 1
        
    #     if target == 2:
    #         return 2 if 1 not in As else 1

    #     if not mems[target]:
    #         one = rec(target-1)
    #         two = rec(target-2)
    #         mems[target] = one + two
        
    #     return mems[target]
    # print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    As.sort()

    cnts = [False] * (N+1)
    ptr = 0
    for i in range(N+1):
        c = 0
        if ptr < len(As) and i == As[ptr]:
            c = 0
            ptr = ptr + 1
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = (cnts[i-2] + cnts[i-1])%1000000007
        cnts[i] = c

    print(cnts[N])

if '__main__' == __name__:
    resolve()

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())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)]:
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)


N,M=map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)]):
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)



#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    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
    for i in range(N):
        if (i+1)<=N and (not i+1 in a):
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if (i+2)<=N and (not i+2 in a):
            dp[i+2] += dp[i]
            dp[i+2] %= mod

    print(dp[N])

if __name__ == '__main__':
    main()

Verdicts: Runtime Error

Runtime Error

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

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

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

    
    



n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[1]=1
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[1]=1
b[0]=1
MOD=(10**9)+7

a.append(int(input()),for _ in range(m))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for _ in range(m))
  
if 1 not in a:
  b[1]=1
  
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7

a.append(int(input()) for i in range(m))
  
if 1 not in a:
  b[1]=1
else:
  b[1]=0
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



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

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

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

    
    


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

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

Submission attempts (in order):
n, m = map(int, input().split())
p = {int(input()) for _ in range(m)}
s = 10 ** 9 + 7

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

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


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

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

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

print(dp[-1])


Verdicts: Wrong Answer

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

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

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

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

Verdicts: Runtime Error

Wrong Answer

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

Submission attempts (in order):
n,m=map(int,input().split())
a=[]
b=0
c=0
d=1
e=0
for i in range(m):
    a.append(int(input()))
for j in range(m-1):
    if(a[j]+1==a[j+1]):
        print('0')
        break    
z=list(set(a))
z=sorted(z)
z.append(0)     
for i in range(n):
    if(z[b]==i+1):
        b+=1    
        continue    
    else:
        c=d+e
        e=d
        d=c
print({0}.format(c%100000007)

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
flag=0
c=[0 for i in range(n+1)]
b=0
a.append(-2)
c[0]=1
if(a[b]==1):
    c[1]=0
    b+=1
else:
    c[1]=1
for i in range(2,n+1):
    if (i==a[b]):
        c[i]=0
        b+=1
    else:
        c[i]=c[i-1]+c[i-2]
        c[i]=c[i] %1000000007
print('{0}'.format(c[n]))

Verdicts: Runtime Error

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

Submission attempts (in order):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(sys.stdin.readline()) for i in range(m)]
print(a)
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
   
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)  


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(sys.stdin.readline()) for i in range(m)]
print(a)
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
   
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)  


import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = []*(n+1)
for i in range(m):
  hole[int(input())] = 1
dp = [0]*(n+1)
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  dp[i] = dp[i-1]+dp[i-2]
  dp[i] %= MOD

print(dp[-1])  


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(j) for j in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
 
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit()
  
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)  


import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

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

print(dp[-1])  


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

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

Submission attempts (in order):
#129_C
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
mod=10**9+7
dp=[1 for i in range(n+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])%mid
        
print(dp[n]%mod)

#129_C
n,m=map(int,input().split())
a={int(input()) for _ in range(m)}
mod=10**9+7
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
        
print(dp[n])

Verdicts: Runtime Error

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

Submission attempts (in order):
N, M = map(int, input().split())
mod = 10 ** 9 + 7

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


temp = 0
pos = 0
for i in range(M):
  if pos == i:
    print(0)
    break
    
  temp += fibonacci(i - 1 - pos) % mod
  pos = i + 1
print(temp)

N, M = map(int, input().split())
a = [0] * (N + 1)
for i in range(M):
  a[int(input())] = 1
dp = [0] * (N + 1)
dp[0] = 1
for i in range(N - 1):
  if a[i + 1] == 0:
    dp[i + 1] += dp[i]
  if a[i + 2] == 0:
    dp[i + 2] += dp[i]
print((dp[N] + dp[N - 1]) % (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())
oks = [True]*(n+1)
for i in range(m):
    a = int(input())
    oks[a] = False
print(oks)
dp = [0]*(n+1)
dp[0] = 1
for i in range(n+1):
    for j in range(i+1,min(n+1,i+3)):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= 1000000007
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
for i in range(n):
    if i+1<n+1 and not i+1 in a:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2<n+1 and not i+2 in a:
        dp[i+2] += dp[i]
        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 = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
b.append(int(a[0]))
for i in range(len(a) - 1):
    b.append(int(a[i + 1]) - int(a[i]) - 1)
print(b)
for i in range(max(b)):
    total_act3 = total_act2 + total_act
    total_act2 = total_act
    total_act = total_act3
    c.append(total_act)
print(c)
for i in b:
    total *= c[i - 1]

total *= c[n - int(a[-1]) - 1]
print(total % 1000000007)


n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1

#     if str(i) in a:



#     else:




# print(total % 1000000007)
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))
    print(b)
    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)
    print(c)
    for i in b:
        total *= c[i - 1]
        print(c[i - 1])
    print(total % 1000000007)


n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)


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):
def factorial(x, mod=10**9+7):
    # x!
    
    # ex) factorial(5) = 120
    tmp = 1
    for i in range(1, x+1):
        tmp = (tmp * i)
    return tmp



def step(t):
    total = 0
    buf2 = int(t/2)

    for i in range(buf2+1):
        buf1 = t-(i*2)
        buf12 = buf1 + i
        buf_ue = factorial(buf12)
        buf_sita1 = factorial(buf1)
        buf_sita2 = factorial(i)
        total += int(buf_ue / (buf_sita1*buf_sita2))

    return total


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

for i in range(m):
    a = int(input())
    if a == now:
        total = 0
        break
    elif a == now+1:
        now = a+1
    else:
        print(a-1-now)
        total *= step(a-1-now)
        now = a+1

total *= step(n-now)
total = total%MOD
print(total)

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

a = [True]*(n+1)

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

dp = [0]*(n+1)

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

for i in range(2,n+1):
    if a[i-1]:
        dp[i] += dp[i-1]
    if a[i-2]:
        dp[i] += dp[i-2]
    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):
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

result = 0

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i) 
    result = result % 1000000007 
    print(result)

else:
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)
    
    

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

dp = [0 for i in range(N + 1)]
dp[0] = 1
point = 0
if a[point] == 1:
    dp[1] = 0
    point += 1
else:
    dp[1] = 1
for i in range(2, N + 1):
    if i == a[point]:
        dp[i] = 0
        point += 1
    else:
        dp[i] = (dp[i - 2] + dp[i - 1]) % (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):
import sys
sys.setrecursionlimit(10**10)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 1000000007
def Fib(n, A, MOD, memo={}):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, A, MOD, memo) + Fib(n-2, A, MOD, memo) ) % MOD
        return memo[n]
print(Fib(N, A, MOD))

import sys
sys.setrecursionlimit(10**5+10)
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
MOD = 1000000007
memo = {}
def Fib(n, MOD):
    if n in A:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = ( Fib(n-1, MOD) + Fib(n-2, MOD) ) % MOD
        return memo[n]
print(Fib(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 math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [0]
b.extend(a)
b.extend([N+1])
ans = 1
for i in range(M+1):
    dan = b[i+1] - b[i]
    tori = int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.01)
    ans *= tori
print(ans)

import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
import sympy as sym
def fibo(n):
    if n < 1:
        return 0
    else:
        x = sym.symbols('x',nonnegative=True,integer=True)
        Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
        result=Fib.subs(x,n)
        result=sym.simplify(result) 
        return result

for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan)%1000000007
print(ans)

import fractions

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)
def nCk(n, k):
    return fractions.factorial(n)/(fractions.factorial(k)*fractions.factorial(n-k))
ans=1
for i in range(len(D)):
    if i !=len(D) and i!=0 and D[i]==0:
        temp = 0
    else:
        temp = 0
        for j in range(D[i]//2+1):
            temp += nCk(D[i]-j,j)
#    print(temp)
    ans=(ans*temp)%1000000007
print(int(ans%1000000007))

import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)

Verdicts: Runtime Error

Runtime Error

Runtime Error

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

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

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

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

print(dp)
print(dp[N]%1000000007)

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

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

for next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = (dp[next-1] + dp[next-2])%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 sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    dp = [0]*N
    
    if len(A) != 0:
        out = A.popleft 
    else:
        out = 0
        
    if out != 1:
        dp[0] = 1
    else:
        dp[0] = 0
        if len(A) != 0:
            out = A.popleft 
    if out != 2:
        dp[1] = 1+dp[0]
    else:
        dp[1] = 0
        if len(A) != 0:
            out = A.popleft 

    for i in range(2,N):
        if i+1 == out:
            dp[i] = 0
            if len(A) != 0:
                out = A.popleft()
        else:
            if dp[i-2] != 0 or dp[i-1] != 0:
                dp[i] = dp[i-2] + dp[i-1]

    if dp[N-1] != 0:
        print(dp[N-1]%(10**9 + 7))
    else:
        print(0)
    
if __name__ == '__main__':
    main()

import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map(int, input().split())
    A = deque([int(input()) for i in range(M)])
    if N == 1:
        print(1)
    else:
        dp = [0]*N
        
        if len(A) != 0:
            out = A.popleft() 
        else:
            out = 0

        if out != 1:
            dp[0] = 1
        else:
            dp[0] = 0
            if len(A) != 0:
                out = A.popleft()
        if out != 2:
            dp[1] = 1+dp[0]
        else:
            dp[1] = 0
            if len(A) != 0:
                out = A.popleft()

        for i in range(2,N):
            if i+1 == out:
                dp[i] = 0
                if len(A) != 0:
                    out = A.popleft()
            else:
                if dp[i-2] != 0 or dp[i-1] != 0:
                    dp[i] = dp[i-2] + dp[i-1]

        if dp[N-1] != 0:
            print(dp[N-1]%(10**9 + 7))
        else:
            print(0)
    
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):
#coding:utf-8


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


broken = [0] * (n+1)


dp = [0] * (n+1)

dp[0] = 1



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


if broken[1] == 1:
    dp[2] = 0
else:
    
    dp[2] = 1


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

print(dp[n])



#coding:utf-8


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


broken = [0] * (n+1)


dp = [0] * (n+1)

dp[0] = 1



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


if broken[1] == 1:
    dp[2] = 0
else:
    
    dp[2] = 1


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

print(dp[n])



#coding:utf-8


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


broken = [0] * (n+1)


dp = [0] * (n+1)

dp[0] = 1



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


if broken[1] == 1:
    dp[1] = 0
else:
    
    dp[1] = 1


for i in range(2, n+1):
    if broken[i] == 1:
        
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i] % 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):
def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
cnt=fib_memo(a[0]-1)*fib_memo(n-a[m-1]-1)
for i in range(1,m-1):
  cnt*=fib_memo(a[i]-a[i-1]-1)
print(cnt)
  
  

def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)
  
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
if a:
  cnt=fib(a[0]+1)*fib(n-a[m-1]+1)
  for i in range(1,m):
    cnt*=fib(a[i]-a[i-1])
  print(cnt%(10**9+7))
else:
  print(fib_memo(n+2)%(10**9+7))


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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[1]*(n+1)
dp[0]=1
dp[1]=1
for i in range(m):
  if a[i]==1:
    dp[1]=0
  else:
    dp[a[i]]=0
for i in range(2,n+1):
  if dp[i]:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%(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):
def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
N, M = map(int, input().split())
a = [int(input(i)) for i in range(M)]
m = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        break
    else:
        for j in range(M-1):
            dev = a[j+1]-a[j]
            m += Fib(dev)
        print(m)

def Fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

flag = True
if M == 1:
    print(Fib(a[0])*Fib(N-a[M-1]))
elif M == 0:
    print(Fib(N+1)%1000000007)
else:
    m = Fib(a[0])*Fib(N-a[M-1])
    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            print(0)
            flag = False
            break
    if flag:
        for j in range(M-1):
            dev = a[j+1]-a[j]-1
            m = m*Fib(dev)%1000000007
        print(m%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())

h = []
a = 1
b = 1
mod = 10 ** 9 + 7

for i in range(m):
    h += [int(input()),]

for i in range(1,n+1):
    if i in h:
        a,b = 0,a
        # b %= mod
    else:
        a,b = a + b,a
        # a %= mod
        # b %= mod

print(a % mod)

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

print((a + b) % mod)

Verdicts: Wrong Answer

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

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

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

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

for i in range(2,n+1):
    if i in a:
        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 = list(map(int, input().split()))
A = set(int(input()) for i in range(M))
x = [0] * (n+1)
x[0] = 1

for i in range(1, n+1): 
  if x[i] in A:
    x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2])%(10**9+7)
return x[n]

N, M = map(int, input().split())
A = set(int(input()) for i in range(M))
x = [0] * (N+1)
x[0] = 1
 
for i in range(1, N+1): 
  if i in A: x[i] = 0
  else:
    x[i] = (x[i-1] + x[i-2])%(10**9+7)
    
print(x[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=[]
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 1:
    t,w,v = 0,0,0
    for j in range(len(a)):
        if j+1 == m:
            if n-a[j] >= 3:
                v += 1
                w += n-a[j]
            break
        elif a[j] - t >= 3:
            v += 1
            w += a[j] - t
            t = a[j] + 1
        else:
            t = a[j] + 1
ans = v * 2
t = ans // 2
for k in range(w):
    temp = ans
    ans += t
    t = temp

print(ans % 1000000007)


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

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-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())
bl = set([int(input())-1 for _ in range(m)])
l = [i for i in range(n)]

mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    if i not in bl
        al[i] = (al[i-1] + al[i-2])%mod
        if al[i] == 0:
            print(0)
            exit()

print(al[-1])


n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = (al[i-1] + al[i-2])%mod
    if al[i] == 0:
        print(0)
        exit()

print(al[-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 = set([int(input()) for _ in range(M)])
mod = 10**9+7
dp=[0]*(N+1)
dp[1]=1


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


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

dp = [0]*(N+1)
dp[0]=1
if 1 not in a:dp[1] = 1

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


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

dp = [0]*(N+1)
if 1 not in a:dp[1] = 1


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


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

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

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

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

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


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

dp=[0]*(N+1)

for i in range(N):
  if i+1 not in a:
    dp[i+1]+=dp[i]
  if i+2 < N and i+2 not in a:
    dp[i+2]+=dp[i]
  
print(dp[-1]%1000000007)

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


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


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted