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

Submission attempts (in order):
import sys

input = sys.stdin
N, W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, input()))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)


import sys
N, W = sys.stdin.readline().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, sys.stdin))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
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):
import sys
sys.setrecursionlimit(100000) 

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

for i in a:
    memo[i] = 0

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + memo[1]
            else:
                memo[k] = 0 + memo[1]
        elif k not in a:
            if k-1 not in a or k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
        return memo[k]

print(stair(n))

from functools import lru_cache
@lru_cache(maxsize=100000)

import sys
sys.setrecursionlimit(100000) 

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

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

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

for i in range(n):
    if dp[i]<0:
        continue
    dp[i] %= 10**9+7
    if dp[i+1]>=0:
        dp[i+1] += dp[i]
    if dp[i+2]>=0:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))

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 func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
import sys
sys.setrecursionlimit(1000000)
n,m = map(int, intput().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n))

def func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
n,m = map(int, intput().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n))

def func(n):
    if n==0: return 1
    if n==1: return 1
    if dp[n]!=-1: return dp[n]
    f1 = func(n-1) if n-1 not in a else 0
    f2 = func(n-2) if n-2 not in a else 0
    dp[n] = (f1 + f2) % 1000000007
    return dp[n]
import sys
sys.setrecursionlimit(1000000)
n,m = map(int, input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(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())
print(n,m)
dp = [-1]*(n+1)
for i in range(m):
    dp[int(input())] = 0
dp[0] = 1
if dp[1] != 0:
    dp[1] = 1
for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1]+dp[i-2])%1000000007
print(dp[n])

n, m = map(int, input().split())
dp = [-1]*(n+1)
for i in range(m):
    dp[int(input())] = 0
dp[0] = 1
if dp[1] != 0:
    dp[1] = 1
for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1]+dp[i-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):
n,m=map(int,input().split())
stair_m=[True]*(110000)
for i in range(m):
    a=int(input())
    stair_m[a]=False
dp=[0]*(110000)
dp[0]=1
for i in range(2,n+2):
    #print(i,i-2,dp[i-2])
    if stair_m[i]:
        dp[i]=dp[i-1]+dp[i-2]
    else:
        dp[i]=0
print(dp[n]%1000000007)

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


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

for i in range(1,n+1):
    if stair[i]:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
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 numpy as np
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
mat = np.array([[1, 1],[1, 0]])
n = np.array([[1, 1],[1, 0]])

cnt = 2
if 1 in a:n[0, 1] = 0

while cnt!=N:
    if cnt in a:n[0, 0]=0
    n = np.dot(n, mat) 
    cnt += 1
    if n[0, 0]==0:break

print(n[0, 0]%(10**9+7))

import sys
input = sys.stdin.readline

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

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

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

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

Verdicts: Wrong Answer

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

Submission attempts (in order):
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
if 1 in a and 2 in a:
    print(0)
    exit()
ans = 1
k = 0
if a[-1]!=n:
    a.append(n)

mod = 10**9+7
max = 10**5+1
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in a:
    if i+1 in a:
        print(0)
        exit()
    else:
        if i-k<=2:
            m = 1
        elif i-k==3:
            m = 2
        else:
            m = 0
            f = i-k-1
            for j in range(f//2,-1,-1):
                m += cmb(f-j,j,mod)
        ans *= m
        ans %= mod
        k = i
print(ans%mod)

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
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):
INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    issafe = [0]*m
    for i in range(m):
        a = int(input())
        issafe[a] = False
    dp = [0]*(n+1)
    dp[0],dp[1] = 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]

    print(dp[n]%(10**9+7))


if __name__ == "__main__":
    main()


INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    issafe = [True]*n
    for i in range(m):
        a = int(input())
        issafe[a] = False
    dp = [0]*(n+1)
    dp[0],dp[1] = 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]

    print(dp[n]%(10**9+7))


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):
# ABC 129, c
n, m = map(int, input().split())
dp = [int(el) for el in input().split(' ')]
dp[0] = 1
dp[1] = 1
for j in [int(input()) for j in range(m)]:
    dp[j] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])


# ABC 129, c
n, m = map(int, input().split())
dp = [0 for i in range(n+1)]
dp[0] = 1
dp[1] = 1
for j in [int(input()) for j in range(m)]:
    dp[j] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            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):
st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=0
for i in range(m):
  y=int(input())
  x=-1 if y==1 else x
  ret=(ret*st[y-x-2])%1000000007
  x=y
ret=(ret*st[n-x-1])%1000000007
print(ret)

st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=-1
for i in range(m):
  y=int(input())
  ret=(ret*st[y-x-2])%1000000007
  print(x,y,y-x-2,st[y-x-2])
  x=y
ret=(ret*st[n-x-1])%1000000007
print(x,n,n-x-2,st[n-x-2])
print(ret)

st=[1,1]
for i in range(10**5+1):
  st.append((st[-1]+st[-2])%1000000007)
st.append(0)
n,m=list(map(int,input().split()))
ret=1
x=-1
for i in range(m):
  y=int(input())
  ret=(ret*st[y-x-2])%1000000007
  x=y
ret=(ret*st[n-x-1])%1000000007
print(ret)

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):
import math
def fib(number):
    a, b = 0, 1
    if number == 1:
        return a
    elif number == 0:
        return b
    else:
        for _ in range(number-2):
            a, b = b, a + b
        return b
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-1-tmp
    if number<1:
        print(0)
        exit()
    else:
        ans *= fib(number)
        tmp = i
print(number)

import math
def fib(number):
    a, b = 0, 1
    for _ in range(number-1):
        a, b = b, a + b
    return a
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number+2)
            tmp = i
print((ans*fib(N-tmp+2))%1000000007)


import math
def fib(number):
    a, b = 0, 1
    for _ in range(number):
        a, b = b, a + b
    return b
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number-1)
            tmp = i+1
print((ans*fib(N-tmp))%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):
N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))

def fibo(x2):
    if (x2 == 1) or (x2 == 2):
        return (1)
    else:
        return((fibo(x2-1) + fibo(x2-2)) % (10**9 + 7))

aa = [] 
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
print(aa)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans = 1
    ans_list = []
    for i in range(M-1):
        if aa[i] >= 1:
            ans_list.append(fibo(aa[i]))

    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[M-1]))
    print(ans_list)
    
    for i in range (len(ans_list)):
        ans = (ans * ans_list[i]) % (10**9 + 7)

print(ans)


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

def fibo(x2):
    if (x2 == 1) or (x2 == 2):
        return (1)
    else:
        return((fibo(x2-1) + fibo(x2-2)) // (10**9 + 7))

aa = []
#aa.append(a[0]-)
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans_list = []
    for i in range(M-1):
        if aa[i] >= 1:
            ans_list.append(fibo(aa[i]))

	ans_list.append(fibo(a[1])
	ans_list.append(fibo(N - a[M]))

	ans = (sum(ans_list) // (10**9 + 7))

print(ans)


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

def fibo(n):
    a, b = 1, 1
    if (n == 0) or (n == 1) or (n == 2):
        return 1
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b

aa = [] 
if M >= 2:
    for k in range(M-1):
        aa.append(a[k+1] - a[k] - 1)
#print(aa)
#aa.append(N - a(M))

    if 0 in aa:
        ans = 0

    else:
        ans = 1
        ans_list = []
        for i in range(M-1):
            ans_list.append(fibo(aa[i]))

        ans_list.append(fibo(a[0]))
        ans_list.append(fibo(N - a[M-1]))
    #print(ans_list)
    
        for i in range (len(ans_list)):
            ans = (ans * ans_list[i]) % (10**9 + 7)

elif M == 1:
    ans_list = []
    ans_list.append(fibo(a[0]))
    ans_list.append(fibo(N - a[0]))
    ans = (ans_list[0] * ans_list[1]) % (10**9 + 7)

elif M == 0:
    ans = fibo(N+1) % (10**9 + 7)

print(ans)


Verdicts: Runtime Error

Runtime Error

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

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

dp = [0] * (n + 10)
dp[0] = 1
mod = 1e9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

for i in range(n):
    if ok[i + 1]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if ok[i + 2]:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(dp[n])


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

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

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

if ok[1]:
    dp[1] = 1

for i in range(2, n + 1):
    if ok[i]:
        dp[i] += dp[i - 1]
        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):
N, M = map(int,input().split())
a = [int(input) for _ in range(M)]

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

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

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

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

print(dp[N])


N, M = map(int,input().split())
a = []
dev = 100000007

for _ in range(M):
    aa = int(input())
    a.append(aa)

ans = 0
flag = True
a.append(N+1)

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

def fadd(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 0:
        return 0
    else:
        return fadd(n-1)%dev + fadd(n-2)%dev
    
if flag:
    
    pa = 0 
    for i,na in enumerate(a):
        print(i,na)
        ans += fadd(na - 1 - pa)%dev
        pa = na + 1

print(ans)

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

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

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

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

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

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 _ in range(M)}
print(a)

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

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)


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

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

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)




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

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

for i in range(N):
    c=l[i]%1000000007
    if i<=N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

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

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

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)


Verdicts: Wrong Answer

Runtime Error

Runtime Error

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

Submission attempts (in order):
from math import factorial

def main():
    MOD = 1000000007
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    table = [1]*(N+1)
    for broken in a:
        table[broken] = 0
    table[1] = table[0] * table[1]
    if N > 1:
        for n in range(2, N+1):
            table[n] = ((table[n-2] + table[n-1]) * table[n]) % MOD
    print(table[-1])
main()

Verdicts: Wrong Answer

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

Submission attempts (in order):
BIG = 10**9+7

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

pre = a[0]
dame = False
for i in range(1,len(a)):
    if a[i]==pre:
        dame = True
    pre=a[i]

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

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

print(dp)

if dame:
    print(0)
else:
    print(dp[-1])

BIG = 10**9+7

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

pre = a[0]
dame = False
for i in range(1,len(a)):
    if a[i]==pre:
        dame = True
    pre=a[i]

dp = [0 for i in range(N+1)]
for item in a:
    dp[item]=-1
if a[0]!=0:
    dp[0] = 1
if a[0]!=0:
    if (len(a)>1 and a[1]!=0) or a[0]!=1:
        dp[1] = 2

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

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

#print(dp)

if dame:
    print(0)
else:
    print(dp[-1])

BIG = 10**9+7

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


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

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

print(dp[-1])

Verdicts: Runtime Error

Runtime Error

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

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


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

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


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

Verdicts: Wrong Answer

Runtime Error

Runtime Error

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

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

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

Verdicts: Wrong Answer

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

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

def check(arr):
    for i in range(m-1):
      if a[i] + 1 == a[i+1]: return 0
    dp = [0 for _ in range(n+1)]
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        if i in a: continue
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %= mod
    #print(dp)
    return dp[n]

print(check(n))

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
notbroken = [True for _ in range(n+1)]

for i in a:
  notbroken[i] = False

dp = [0 for _ in range(n+1)]
dp[0] = 1
if notbroken[1]: dp[1] = 1

for i in range(2, n+1):
    if notbroken[i]:
        dp[i] += dp[i-1] + 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):
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]

T = 1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N==1:
        print(1)
    elif N == 2:
        print(2)
    else:
        L = [0 for _ in range(N)]
        if 0 in a:
            L[0] = 0
            L[1] = 1 
        else:
            L[0] = 1
            if 1 in a:
                L[1] = 0
            else:
                L[1] = 2
        for i in range(2,N):
            S = i-2 in a
            T = i-1 in a
            U = i in a
            if U:
                L[i] = 0
            elif T:
                L[i] = L[i-2]%1000000007
            else:
                if S:
                    L[i] = L[i-1]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
    print(L[-1])

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

a = [int(input())-1 for _ in range(M)]
T = 1
for i in range(M-1):
    if a[i]+1==a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N==1:
        print(0)
    else:
        L = [0 for _ in range(N)]
        for i in range(M):
            L[a[i]] = -1
        if L[0] == -1:
            L[1] = 1 
        else:
            L[0] = 1
            if L[1] != -1:
                L[1] = 2
        for i in range(2,N):
            if L[i] != -1:
                if L[i-2] == -1:
                    L[i] = L[i-1]%1000000007
                elif L[i-1] == -1:
                    L[i] = L[i-2]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
        print(L)

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

a = [int(input())-1 for _ in range(M)]
T = 1
for i in range(M-1):
    if a[i]+1 == a[i+1]:
        T = 0
        break
if T == 0:
    print(0)
else:
    if N == 1:
        if M==0:
            print(1)
        else:
            print(0)
    else:
        L = [0 for _ in range(N)]
        for i in range(M):
            L[a[i]] = -1
        if L[0] == -1:
            L[1] = 1
        else:
            L[0] = 1
            if L[1] != -1:
                L[1] = 2
        for i in range(2,N):
            if L[i] != -1:
                if L[i-2] == -1:
                    L[i] = L[i-1]%1000000007
                elif L[i-1] == -1:
                    L[i] = L[i-2]%1000000007
                else:
                    L[i] = (L[i-1]+L[i-2])%1000000007
        print(L[-1])

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())
b = [False]*(m+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0
if n = 1:
    if b[1] == True:
        print(0)
    else:
        print(1)
    exit()
print(up(n))

n, m = map(int, input().split())
b = [False]*(m+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0
if n == 1:
    if b[1] == True:
        print(0)
    else:
        print(1)
    exit()
print(up(n))

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

    
    d = [0] * (n+1)
    
    cnt = 0 
    
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

def main():
	n, m = map(int, input().split())
    a = set(int(input()) for i in range(m))
    mod = 1000000007
 
    
    d = [0] * (n+1)
    
    cnt = 0 
    
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)
 
if __name__ == '__main__':
    main()

def main():
    # n, m = map(int, input().split())
    
    # n, m = map(int, readline().split())
    # a = set(map(int, read().split()))
    n, m = map(int, input().split())
    a = set(int(input()) for i in range(m))
    mod = 1000000007

    
    d = [0] * (n+1)
    
    cnt = 0 
    
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

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):
c_mod=1000000007
n,m = map(int,input().split())

step=[0]*n
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(2,n):
    if step[i]==-1:
        continue
    if step[i-1]!=-1:
        step[i]+=step[i-1]
    if step[i-2]!=-1:
        step[i]+=step[i-2]
print(step[n-1]%c_mod)


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

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

def count(s,e):
    return fib[e-s]
 
c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    
    end=a-1
    ans=ans*count(start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,end)%c_mod
print(ans)

Verdicts: Runtime Error

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

Submission attempts (in order):
N,M = map(int,input().split())
A = set()
for i in range(M):
    A.append(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod
print(count[N])

N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
print(A)
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

N,M = map(int,input().split())
A = set()
for i in range(M):
    A.add(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod
print(count[N])

Verdicts: Runtime Error

Wrong Answer

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

Submission attempts (in order):
n,m = map(int,input().split())
a = [0]
lim = int((1e+9)+7)
def combination(n,k):
    ans = 1
    for i in range(k):
        ans = (ans*(n-i))
        ans = (ans/(i+1))
    return int(ans)

def stair(num):
    ans = 0
    for i in range(num):
        ans = (ans+combination(num-i,i))%lim
    return int(ans)

for _ in range(m):
    a.append(int(input()))
a.append(n+1)
d = []
for i in range(m+1):
    d.append(a[i+1]-a[i])
d[0] += 1
for i in range(len(d)):
    if not(i == 0 or i == len(d)-1):
        if d[i] == 1:
            print(0)
            exit()
ansf = 1
for i in range(1,len(d)):
    if d[i] != 1:
        ansf = (ansf * stair(d[i]-2))%lim
print(ansf%lim)

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
fibo = [1,1]
r = [a[0]-1]

for i in range(m-1):
    r.append((a[i+1]-a[i])-2)
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
else:
    r.append(n-a[-1]-1)

    for i in range(max(r)+2):
        fibo.append((fibo[-1]+fibo[-2])%1000000007)

    ans = 1

    for i in range(n):
        ans = (fibo[r[i]] * ans)%1000000007

    print(ans)

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

for i in range(n):
            fibo.append((fibo[-1]+fibo[-2])%1000000007)

if m:
    r = [a[0]-1]

    for i in range(m-1):
        r.append((a[i+1]-a[i])-2)
        if a[i+1]-a[i] == 1:
            print(0)
            exit()

    else:
        r.append(n-a[-1]-1)

        for i in range(len(r)):
            ans = (fibo[r[i]] * ans)%1000000007

        print(ans)
else:
    print(fibo[n])

Verdicts: Wrong Answer

Runtime Error

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

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

from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+2)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

import sys
sys.setrecursionlimit(10 ** 6)

from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def Fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+1)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

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
dp = [-1]*(n+1)
dp[0]= 1
for i in range(m):
    a = int(input())
    dp[a-1] = 0
#print(dp)
#dp[1] = 1
#dp[2] = 2
for i in range(1,n+1):
    if i <= 1:
        dp[i] = dp[i-1]+1
    elif i>=2 :
        dp[i] = (dp[i-1]+ dp[i-2])%mod
        #print(dp)
print(dp[n])

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

mod = 10**9 + 7
for i in range(m):
    a = int(input())
    dp[a-1] = 0

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

print(dp[n-1])

n,m = map(int,input().split())
L =  [] 
for i in range(m):
    L.append(int(input()))
print(L)
mod = 10**9+7
dp = [0]*(n+1)
dp[0]= 1
dp[1] = 1
#dp[2] = 2
for i in range(1,n+1):
    if 1 in L:
        dp[1] = 0
    if i in L:
        continue
    else:
        if i <= 1:
            dp[i] = dp[i-1]
        elif i>=2 :
            dp[i] = dp[i-1]+ dp[i-2]
        #print(dp)
print(dp[n]%mod)

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

mod = 10**9+7
dp = [-1]*(n+1)
dp[0]= 0
dp[1] = 1
for i in range(m):
    a = int(input())
    dp[a] = 0

for i in range(2,n+1):
    if dp[i] == -1:
        if i <= 2:
            dp[i] = dp[i-1]+1
        elif i>=3 :
            dp[i] = (dp[i-1]+ dp[i-2])%mod

print(dp[n])

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

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

Submission attempts (in order):
n, m = [int(x) for x in input().split()]
a = []
for _ in range(m):
    a.append(int(input()))

mod = 1000000007

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

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

print(dp[n])

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

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

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

print(dp[n])

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

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in range(2, n+2):
    
    
    #         print(0)
    #         sys.exit()
    #     else:
    #         dp[i] = 0
    # else:
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[-1])

import sys
MOD = 10 ** 9 + 7

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

def main():
    ways = [0] * (n + 1)
    ways[0] = 1
    ways[1] = int(not 1 in broken)
    for i in range(2, n + 1):
        ways[i] = (not i in broken) * (ways[i-1] + ways[i-2]) % MOD
    print(ways[n])

if __name__ ==  '__main__':
    main()

Verdicts: Wrong Answer

Accepted