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

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        tmp += cmb(n, r, exact=True)
        dif = n-r
        n -= 1
        # print("tmp",tmp,n,r)
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    print("n",n)
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        print(n,r)
        tmp += cmb(n, r)
        dif = n-r
        print("tmp",tmp,n,r)
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

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

print(dp[N]%mod)

Verdicts: Runtime Error

Runtime Error

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

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

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

pos = 0
count = 1
dp = [0] * (n+1)
dp[0] = 1

for i in range(N+1):
    if (i+1) in A and (i+2) in A:
        print(0)
        exit()
    if (i+1) not in A:
        dp[i+1] += dp[i]
    if (i+2) not in A:
        dp[i+2] += dp[i]

print(dp[n])

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
A = set(ir() for _ in range(M))
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    if i+2 not in A and i+2 <= N:
        dp[i+2] += dp[i]
    if i+1 not in A:
        dp[i+1] += dp[i]

print(dp[-1]%MOD)


Verdicts: Runtime Error

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

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

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

for i in range(n):
    if i == 0:
        mat[i] = 1
    if mat[i] == -1:
        continue
    if i + 1 < n+1:
        if mat[i+1] != -1:
            mat[i+1] += mat[i]
    if i + 2 < n+1:
        if mat[i+2] != -1:
            mat[i+2] += mat[i]
if mat[-1] => 0:
    print(mat[-1]%1000000007)
else:
    print(0)
 

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

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

for i in range(n):
    if i == 0:
        mat[i] = 1
    if mat[i] == -1:
        continue
    if i + 1 < n+1:
        if mat[i+1] != -1:
            mat[i+1] += mat[i]
    if i + 2 < n+1:
        if mat[i+2] != -1:
            mat[i+2] += mat[i]
    print(mat)
if mat[-1] => 0:
    print(mat[-1]%1000000007)
else:
    print(0)
 

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

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

for i in range(n):
    if i == 0:
        mat[i] = 1
    if mat[i] == -1:
        continue
    if i + 1 < n+1:
        if mat[i+1] != -1:
            mat[i+1] += mat[i]
    if i + 2 < n+1:
        if mat[i+2] != -1:
            mat[i+2] += mat[i]
if mat[-1] >= 0:
    print(mat[-1]%1000000007)
else:
    print(0)

Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
import numpy as np


def main(n, m, a):
    dp = np.zeros(n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0

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

    return dp[-1]


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        A.add(int(input()))

    print(main(N, M, A))


import numpy as np


def main(n, m, a):
    dp = np.zeros(n + 1)
    dp[0] = 1
    dp[1] = 1 if 1 not in a else 0

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

    return dp[-1]


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = set()
    for _ in range(M):
        A.add(int(input().strip()))

    print(main(N, M, A))


import math

MOD = int(math.pow(10, 9)) + 7
N, M = map(int, input().split(' '))
broken_steps = {int(input()) for _ in range(M)}

dp = [0] * (N + 1)

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

for step in range(2, N + 1):
    if step not in broken_steps:
        dp[step] = (dp[step - 1] + dp[step - 2]) % MOD

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 = map(int, input().split())
if N == 1:
    print(1)
    exit()

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

import bisect
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
broken = [0]*(N+1)
for i in range(M):
    broken[a[i]] = 1
if M == 0:  a.append(0)
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if broken[i] == 1:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
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 = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1]:
    ans = 0
  else:
    x = a[i+1]-a[i]-1
    ans = ans * 1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)%1000000007

if m == 0:
    x = a[m+1]-a[i]-1
    ans = 1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)%1000000007

print(ans)


n,m = map(int,input().split())
a = list(range(m+2))
a[0] = 0
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1] and i != 0:
    ans = 0
    break
  else:
    x = a[i+1]-a[i]-1
    if x == 0 or x == 1:
      ans = ans%1000000007
    else:
      ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

print(ans)

n,m = map(int,input().split())
a = list(range(m+2))
a[0] = 0
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1] and i != 0 and i != m:
    ans = 0
    break
  else:
    x = a[i+1]-a[i]-2
    if x == 0 or x == 1:
      ans = ans%1000000007
    elif x == 2:
      ans = ans*2%1000000007
    else:
      ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

print(ans)


n,m = map(int,input().split())
b = [] 
for i in range(n+1):
  if i == 0 or i == 1:
    b.appned(1)
  else:
    b.append(b[i-2]+b[i-1])

ans = 1
if m != 0:
  a = list(range(m))
  for i in range(m):
    a[i] = int(input())
    if i == 0:
      ans = ans*b[a[i]-1]%1000000007
    else:   
      ans = ans*b[a[i]-a[i-1]-2]%1000000007
  ans = ans*b[n-a[m-10]-1]%1000000007
  print(ans)
else:
  print(b[n]%1000000007)

n,m = map(int,input().split())
b = [] 
for i in range(n+1):
  if i == 0 or i == 1:
    b.append(1)
  else:
    b.append(b[i-2]+b[i-1])

ans = 1
if m != 0:
  a = list(range(m))
  for i in range(m):
    a[i] = int(input())
    if i == 0:
      ans = ans*b[a[i]-1]%1000000007
    else:
      if a[i] == a[i-1]+1:
        ans = 0
      else:
        ans = ans*b[a[i]-a[i-1]-2]%1000000007
  ans = ans*b[n-a[m-1]-1]%1000000007
  print(ans)
else:
  print(b[n]%1000000007)

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):
MOD=10**9+7
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,1]
elif 2 in a:
  ans=[1,0]

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

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

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

Verdicts: Runtime Error

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

Submission attempts (in order):
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n, m = intinput()
a = {int(sys.stdin.readline()) for _ in range(m)}
print(a)
memo = [0 for x in range(n + 4)]
memo[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
    if i + 1 not in a:
        memo[i + 1] = (memo[i + 1] + memo[i]) % mod
    if i + 2 not in a:
        memo[i + 2] = (memo[i + 2] + memo[i]) % mod

import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())


n, m = intinput()
a = {int(sys.stdin.readline()) for _ in range(m)}
memo = [0 for x in range(n + 4)]
memo[0] = 1
mod = 10 ** 9 + 7
for i in range(n):
    if i + 1 not in a:
        memo[i + 1] = (memo[i + 1] + memo[i]) % mod
    if i + 2 not in a:
        memo[i + 2] = (memo[i + 2] + memo[i]) % mod
print(memo[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 noboru(m):
    if (m == 1):
        return 1
    elif (m == 2):
        return 2
    else:
        return noboru(m-1)+noboru(m-2)

def func(N, M, a):
    ans = 1
    if (a[0] == 1):
        ans *=1
    else:
        ans *= noboru(a[0]-1)
    for i in range(1, M):
        if (a[i] == a[i-1]+1):
            return 0
        else:
            ans *= noboru(a[i] - 2 - a[i-1])
    ans *= noboru(a[M] - 1 - a[i])
    return ans % 1000000007

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

CONST = 1000000007

def noboru(n):
    a1 = 1
    a2 = 2
    ans = 0
    if (n == 0 or n == 1): return a1
    elif (n == 2): return a2
    else:
        for i in range(1, n-1):
            ans = a2 + a1
            a1 = a2
            a2 = ans
        return a2

def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos)) % CONST
    return ans

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

Verdicts: Runtime Error

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

Submission attempts (in order):
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
broken=[False]*(n+1)
dp=[1]+[0]*100010
for i in range(m):
    broken[i]=True
for i in range(1,n+1):
    if broken[i]:
        dp[i]=0
    else:
        try:
            dp[i]=dp[i-1]+dp[i-2]
        except:
            dp[i]=dp[i-1]
        dp[i]%=1000000007
print(dp[n])

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


n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input()))
def stairs(n):
  memo=["a"]*n
  def count(n):
    if n in out:
      return 0
    elif n<=2:
      return n
    else memo[n-1]!="a":
      return memo[n-1]%(10e9+7)
    return (memo[n-2]+memo[n-3])%(10e9+7)
  return count(n)
print(stairs(n)%(10e9+7))

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


n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input())
from functools import lru_cache

@lru_cache(maxsize=10**5)
def fib_memoized(n):
    if n < 2:
        return n
    elif n in out:
        return 0
    else:
        return fib(n - 1) + fib(n - 2)
print(fib_memorized(n))

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))


Verdicts: Wrong Answer

Runtime Error

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(' '))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()

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-1]+dp[i-2])%mod

print(dp[n])

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

out=0
for i in range(0,N,1):
  if i in A:
    continue
  if i==N:
    out+=1
  for j in range(i,N,2):
    if j in A:
      continue
    if j==N:
      out+=1
  
print(out%1000000007)

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

out=0
for i in range(0,N,1):
  if i in A:
    continue
  if i==N-1:
    out+=1
  for j in range(i,N,2):
    if j in A:
      continue
    if j==N-1:
      out+=1
  
print(out%1000000007)

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

if 1 in a:
  fibo=[1,0]
else:
  fibo=[1,1]
mod=10**9+7
for i in range(2,n-1):
  if i in a:
    fibo[i-1]=0
  f=(fibo[-2]+fibo[-1])%mod
  fibo.append(f)

print(fibo[-1])

import sys
n,m=map(int,input().split())
if m > 0:
  a = set(map(int, sys.stdin))
else:
  a = set()

fibo=[0]*(n+1)
fibo[0]=1
fibo[1]=1 if 1 not in a else 0
mod=10**9+7
for i in range(2,n+1):
  if i in a:
    continue
  fibo[i]=(fibo[i-2]+fibo[i-1])%mod

print(fibo[-1])

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

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

Submission attempts (in order):
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()


import math
import numpy as np

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

diff = np.array(A)[1:] - np.array(A)[:-1]
if any(diff == 1) :
    print(0)
else :
    S = []
    if M > 0 :
        A.insert(0, 1)
        A.insert(N-1, N + 1)
        D = list(np.array(A)[1:] - np.array(A)[:-1] - 1)
    else :
        D = [N + 1]
    R = []
    for d in D :
        P = d - 1
        K = int(P / 2)
        T = 1
        for k in range(1, K+1) :
            T += combinations_count(P - k, k)
        R.append(T)
    ans = R[0]
    #print(R)
    for r in R[1:] :
        #print(ans)
        ans = ans * r % (10 ** 9 + 7)
    print(ans)



MOD = 1000000007
def main():
    n, m = [int(x) for x in input().split()]
    pattern = [1]
    broken = -1
    brokencnt = 0
    if brokencnt < m:
        broken = int(input())
        brokencnt += 1
    for i in range(1, n + 1):
        if i == broken:
            pattern.append(0)
            if brokencnt < m:
                broken = int(input())
                brokencnt += 1
            continue
        if i == 1:
            pattern.append(pattern[i - 1])
        if i > 1:
            pattern.append((pattern[i - 1] + pattern[i - 2]) % MOD)
    print(pattern[n])
main()

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):
MOD = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
broken = [False for _ in range(N+1)]

dp = [0 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
	broken[int(input())] = True
for i in range(1, N+1):
	if broken[i]:
		continue
	if i == 1:
		dp[i] = dp[i-1]
	else:
		dp[i] = dp[i-1] + dp[i-2]
		dp[i] %= MOD
print(dp[N])


MOD = 10 ** 9 + 7

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

broken = [False for _ in range(N+1)]
for _ in range(M):
	broken[int(input())] = True

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

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


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

for i in range(m):
    a = int(input())
    broken[a] = 1
dp = [0]*(n+1)
dp[0] = 1
mod = 1000000007
for i in range(1, n+1):
    if broken[i]:
        continue
    
    dp[i] = (dp[i-1] + dp[i-2]) % mod
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):
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
interval_max = 0
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
    interval_max = max(interval_max, a[i+1] - a[i])
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

step = [0]*interval_max
step[0] = step[1] = 1
for i in range(2,interval_max):
    step[i] = (step[i-2] + step[i-1])
print(a, interval_max)
sum_step = 1
for i in range(len(a)-1):
    sum_step *= step[a[i+1] - a[i] - 1]
sum_step = sum_step % 1000000007
print(sum_step)



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

a.append(-1) 
a_i = 0




step = [0] * (n+2)
step[-1] = -1 
step[0] = 1 

for i in range(1, n+1):
    if a[a_i] == i:
        step[i] = -1 
        a_i += 1
    else:
        if step[i-2] == step[i-1] == -1:
            print(0) 
            exit()
        elif step[i-2] == -1 or step[i-1] == -1:
            step[i] = max(step[i-2], step[i-1]) 
        else:
            step[i] = (step[i-2] + step[i-1]) % MOD 

print(step[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

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

print(a)
#while True:
#    try:

#        a += i
 #   except EOFError:
 #       break

num=[0,0,1,2]

for i in range(4,n+1):
	num.append(1)
	num[i]=num[i-1]+num[i-2]

#print(num)

list=[]
count=0
y=1
ans=1
for i in range(n):
	if(y==0 and i in a):
		print("0")
		break
	elif 1 in a and i==1:
		list.append(1)
		y=0
		count=1
	elif i in a:
		list.append(count-1)

		count=1
		y=0
	elif(i==n-1):
		count+=1
		y=1
		list.append(count-1)
		#print(list)
		for j in range(len(list)):
			ans=ans*num[list[j]+1]
	else:
		y=1
		count+=1
print(ans%1000000007)



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


num=[1,1,2]


mod=1000000007

count=0
jud=1
ans=1
for i in range(n+1):
	
	if i>2:
		num.append(1)
		num[i]=(num[i-1]+num[i-2])%mod

	if(jud==0 and a[i]==1):
		print("0")
		break
	elif a[i]==1:
		ans=(ans%mod)*(num[count-1]%mod)
		count=0
		jud=0
	elif(i==n):
		count+=1
		ans=(ans%mod)*(num[count-1]%mod)
		print(ans%mod)
	else:
		jud=1
		count+=1



Verdicts: Wrong Answer

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

Submission attempts (in order):
import math
phi = (1 + math.sqrt(5)) / 2

def counter(n):
    if n == 1:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = round(phi**(a[0]) / math.sqrt(5)) % (10**9+7)
print(ans)
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)

ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)

print(ans)

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 0
        for _ in range(n-1):
            (a, b) = (a+b, a)
        return a % (10 ** 9 + 7)


def counter(n):
    if n == 0:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
if M == 0:
    print(counter(N+1))
    exit()
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
print(ans)

Verdicts: Runtime Error

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

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

flag = 0
if m > 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1

if flag >= 1:
    print(0)


else:
    def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b

    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

import sys
sys.setrecursionlimit(10000)

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b if n >= 0 else 0

if M == 0:
    ans = fib(N) % (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Verdicts: Runtime Error

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

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

ans = int(1)

A = [0]*(M+1)
A[0]=N
if M!=0:
    A[0] = a[0] - 1
    A[M] = N - a[M-1]-1
    for i in range(M-1):
        A[i+1] = a[i+1] - a[i]- 2
        if A[i+1]==-1:
            ans = 0


SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
if N>2:
    for i in range(N - 1):
        SA[i + 2] = SA[i + 1] + SA[i]
        SA[i + 2] = SA[i + 2] % 1000000007

for i in range(M+1):
    if A[i]>=0:
        ans *= SA[A[i]]
        ans = ans%1000000007


print(ans)


def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()


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 _ in range(M)]
mod=10**9+7
#Dynamic Programming
dp=[0]*(N+1)
dp[0]=1
if 1 not in a:
	dp[1]=1
else:
	dp[1]=0
for i in range(2,N+1):
	if i in a:
		continue
	dp[i]=(dp[i-1]+dp[i-2])%mod
print(ans)

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

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

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

b = [0]*N

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

if 2 not in a:
    if b[0] == 1:
        b[1] = 2
    else:
        b[1] = 1

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

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

MOD = 1000000007

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

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

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

print(b[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):
#from itertools import accumulate

n, m = map(int, input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())
    
    if i>=2 and a[-2]+1 == a[-1]:
        print(0)
        exit()

l = [1] * (n+1)

for i in range(n+1):
    if i in a:
        l[i] = 0
    elif i > 2:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)

#from itertools import accumulate

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

l = [1] * (n+1)

for i in range(n+1):
    if i in a:
        l[i] = 0
    elif i > 2:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)

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

l = [0] * (n+1)
for i in range(m):
  a = int(input())
  l[a] = -1

for i in range(n+1):
  if not l[i] == -1:
    if i == 0 or i == 1:
      l[i] = 1
    else:
      l[i] = max(l[i-2], 0) + max(l[i-1], 0)

print(l[-1] % 1000000007)

Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
n, m = map(int, input().split())
broken = [0] * (n + 1)

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

dp = [0] * (n + 1)
mod = 1000000007

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

print(dp[n])

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

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

dp = [0] * (n + 1)
dp[0] = 1
mod = 1000000007

for i in range(1, 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())

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

wa = (10**9) + 7



dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)!=0:
    a.reverse()
    now_a = a.pop()
if len(a)==0:
    now_a = -1
for i in range(1,N+1):
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

print(dp[N]%wa)





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

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

wa = (10**9) + 7



dp = [0]*(N+1)
dp[0]=1
now_a = 0
if len(a)==0:
    now_a = -1
if len(a)!=0:
    a.reverse()
    now_a = a.pop()

for i in range(1,N+1):
    # print(now_a)
    if i==1:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1] + dp[i-2]
    if i == now_a:
        dp[i]=0
        if len(a)!=0:
            now_a = a.pop()
        else:
            now_a = -1

# print(dp)

print(dp[N]%wa)





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 collections import deque


def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 1
    # Second Fibonacci number is 1 
    elif n==2: 
        return 2
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 
        

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

A = deque()

for _ in range(M):
    A.append(int(input()))

pos = 0
diff = []
la = None

for a in A:
    if la and a - la == 1:
        print(0)
        exit()
    d = (a) - pos
    diff.append(d)
    pos = a
    la = a


diff.append(N - pos)
diff = list(filter(lambda x: False if x <= 0 else True, diff))
F = [Fibonacci(d) for d in diff]

_sum = 1
for f in F:
    _sum *= f

print(_sum // 1000000007)

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

broken = [0 for _ in range(n+1)]
for i in range(m):
    a = int(input())
    broken[a] = True

    
mod = 1000000007
dp = [0 for _ in range(n+2)]

dp[n] = 1
for i in range(n-1, -1, -1):
    if(broken[i]):
        dp[i] = 0
        continue

    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Verdicts: Runtime Error

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

Submission attempts (in order):
n, m = map(int, input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]
b = []
ans, mod = 1, 10**9+7
for i in range(m+1):
    b.append(a[i+1]-a[i]-1)
print(b)
for i in range(m+1):
    diff = b[i]
    dp = [1, 1]
    if i != 0 and diff == 0:
        print(0)
        exit()
    for j in range(diff-2):
        dp.append(dp[j]+dp[j+1])
    ans *= dp[-1]
    ans %= mod
print(ans)

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

for i in range(m+1):
    diff = b[i]
    dp = [1, 1]
    if i != 0 and diff == 0:
        print(0)
        exit()
    for j in range(diff-2):
        dp.append(dp[j]+dp[j+1])
    ans *= dp[-1]
    ans %= mod
print(ans)

Verdicts: Wrong Answer

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

Submission attempts (in order):
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  a=[int(input()) for _ in [0]*m]
  mod=pow(10,9)+7
  ans=[0]*n
  ans[0]=1
  for i in range(n):
    if a.count(i+1)==1:
      ans[i]=0
    else:
      if i==1:
        ans[i]=ans[0]+1
      else:
        ans[i]=(ans[i-1]%mod+ans[i-2]%mod)%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  for i in range(2,n+1):
    if ans[i]>0:
      ans[i]=(ans[i-1]+ans[i-2])%mod
  print(ans[-1])
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):
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
b = [0, 1]
c = []
ans = 1

for _ in range(n):
    b.append(b[-1] + b[-2])

if m == 0:
    ans = b[n + 1]
else:
    c.append(a[0])
    for i in range(m - 1):
        c.append(a[i + 1] - a[i] - 1)
        c.append(n - a[m - 1])

        for i in c:
            ans *= b[i]

print(ans % 1000000007)


n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
b = [0, 1]
c = []
ans = 1

for _ in range(n):
    b.append(b[-1] + b[-2])

if m == 0:
    ans = b[n + 1]
else:
    c.append(a[0])
    for i in range(m - 1):
        c.append(a[i + 1] - a[i] - 1)
    c.append(n - a[m - 1])

    for i in c:
        ans *= b[i]

print(ans % 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 numpy as np
import math

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

aList = [int(input()) for _ in range(M)]

aList.insert(0,-1)
aList.append(N+1)

#print(aList)

aArray = np.array(aList)

katamari = []

for i in range(M+1):
    katamari.append(aArray[i+1] - aArray[i] - 1)



ans = 1
for i in range(M):
    ans *=  (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** katamari[i] - ((1 - math.sqrt(5)) / 2) ** katamari[i])

print(int(ans) % 1000000007)

import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0

print(brk_stair)

dp[0] = 1
dp[1] = 1 * brk_stair[1]

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

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


import numpy as np
import math

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

aList = [int(input()) for _ in range(M)]

trg = np.ones(N+1, dtype = np.int64)
dp = np.zeros(N+1, dtype = np.int64)

for a in aList:
    trg[a] -= 1

for i in range(1, N+1):
    if(i <= 2):
        dp[i] = 1 * trg[i]
    
    else:
        dp[i] = (dp[i-1] + dp[i-2]) * trg[i]

print(dp[N] % 1000000007)


import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0



dp[0] = 1
dp[1] = 1 * brk_stair[1]

for i in range(2, N + 1):
    dp[i] = (dp[i - 1] + dp[i-2]) * brk_stair[i]
    if(dp[i] > 1000000007):
        dp[i] = dp[i] % 1000000007

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


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Accepted