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
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 2)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 <= n:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 <= n:
        if dp[i + 2] != -1 and dp[i] != -1:
            dp[i + 2] += dp[i] % mod
            dp[i + 2] %= mod
if dp[n] = -1:
    print(0)
else:
    print(dp[n] % mod)


import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 2)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 <= n:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 <= n:
        if dp[i + 2] != -1 and dp[i] != -1:
            dp[i + 2] += dp[i] % mod
            dp[i + 2] %= mod
if dp[n] == -1:
    print(0)
else:
    print(dp[n] % mod)


Verdicts: Runtime Error

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

Submission attempts (in order):
class MyClass:
    patternCount = 0

    def skip(self, maxNum, currentIndex):
        if currentIndex >= maxNum or currentIndex in brokenIndexList:
            return
        
        if maxNum -1 == currentIndex:
            self.patternCount += 1
            return

        self.skip(maxNum, currentIndex + 1)
        self.skip(maxNum, currentIndex + 2)

maxNum, brokenCount= map(int, input().split())

brokenIndexList = []
for i in range(brokenCount):
    brokenIndexList.append(int(input()))

if maxNum == 0:
    print(0)

c = MyClass()
c.skip(maxNum, -1)

print(c.patternCount)


maxNum, brokenCount= map(int, input().split())
brokenIndexSet= set([int(input()) for i in range(brokenCount)])

ans = [0]*(maxNum+2)

ans[maxNum] = 1

for i in reversed(range(maxNum)):
    if i in brokenIndexSet:
        ans[i] = 0
    else:
        ans[i] = (ans[i+1] + ans[i+2]) % 1000000007 

print(ans[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 = [0] * m
dp = [1, 1]

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

for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit(0)

x = 0
for i in range(1, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])


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

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

for i in range(1, n+1):
    if i not in a:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
# print(dp)
print(dp[-1])


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

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

for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()

x = 0
for i in range(1, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])


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

for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit(0)


for i in range(2, n+1):
    if i != a[x]:
        dp.append((dp[-1] + dp[-2]) % 1000000007)
    else:
        dp.append(0)
        if x < len(a)-1:
            x += 1
# print(dp)
print(dp[-1])


Verdicts: 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):
import sys

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

if M = 0:
    print(fibo(N))
    sys.exit()

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % 1000000007)

import sys

mod = 10**9 + 7

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []
 
if M == 0:
    print(fibo(N) % mod)
    sys.exit()
 
for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1
 
for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % 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 math import factorial
N,M=list(map(int,input().split()))
dansa=[int(input()) for _ in range(M)]
ans=1
flag=True
if dansa[0]==0:
    print("0")
else:
    if len(dansa)>1:
        for i in range(M-1):
            if dansa[i]+1==dansa[i+1]:
                print("0")
                flag=False
                break
if flag:
    dansa.insert(0,0)
    dansa.append(N)
    for i in range(M+1):
        tmp=dansa[i+1]-dansa[i]-1
        arr=[i for i in range(int(tmp/2)+1)]
        #print("tmp:{}".format(tmp))
        hoge=0
        """
        if tmp%2==0:
            arr=[j*2 for j in range(0,int(tmp/2+1))]
            
        else:
            arr=[j*2+1 for j in range(0,int((tmp+1)/2))]
        """
        #print(arr)
        #if tmp%2==0:
        for k in arr:
            n=tmp-k
            hoge+=factorial(n) / factorial(k) / factorial(n-k)
            
        print(hoge)
        ans=ans*hoge
        print(ans)
    #print(int(ans%1000000007))
    print(ans)



from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))

n,m=input_list()
c=[True for _ in range(n+1)]
mod=10**9+7

for _ in range(m):
    num=int(input())
    c[num]=False

fib=[1,1]
if not c[1]:
    fib[1]=0

for i in range(2,n+1):
    if c[i]:
        fib.append((fib[i-1]+fib[i-2])%mod)
    else:
        fib.append(0)


print(fib[-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):
W,H,x,y = [int(i) for i in input().split()]
flag=0
if W==x*2 and H==y*2:
    flag=1



print(W*H/2,flag)




W,H,x,y = [int(i) for i in input().split()]
flag=0
if W==x+x and H==y+y:
    flag=1



print(W*H/2,flag)





N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

for i in range(M):
    a.append(int(input()))

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007



N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

for i in range(M):
    a.append(int(input()))

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007)

Verdicts: Runtime Error

Runtime Error

Runtime Error

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

Submission attempts (in order):
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
dp[0] = 1
cou = 0
co = 0
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 !=  lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
lis.append(0)
dp[0] = 1
cou = 0
co = 0
if lis[0] == 1:co += 1
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 != lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

Verdicts: Runtime Error

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

Submission attempts (in order):
import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x)
        dp[i] %= mod
    return dp[i]

n,m = (int(a) for a in input().split())
bad = set()
for _ in range(m):
  a = int(input())
  bas.add(a)
print(dfs(n,dict(),bad))


import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
  	if i == 0:
      return 1
    if i in dp:
      return dp[i]
	dp[i] = 0;
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x)
        dp[i] %= mod
	return dp[i]
  
n = int(sys.stdin.next())
m = int(sys.stdin.next())
bad = set()
for _ in range(m):
  a = int(sys.stdin.next())
  bas.add(a)
print(dfs(n,dict(),bad))


import sys
sys.setrecursionlimit(200000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))


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

mod = 1000000007;


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


dp[0] = 1
dp[1] = 1


for _ in range(M) :
    broken[int(input())] = -1


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

print(dp[-1])


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

mod = 1000000007;


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


dp[0] = 1
dp[1] = 1


for _ in range(M) :
    broken[int(input())] = -1


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

print(dp[-1])

Verdicts: Wrong Answer

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

Submission attempts (in order):
def fibona(x):
    import math
    return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1)))//math.sqrt(5)

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):
        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()
        nobori = broken - 1 - (mae + 1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            #print(i, broken, nobori, ans) 
            mae = broken
    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(ans)

        
        



if __name__ == "__main__":
    main()


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]

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = 0

   infi = 10 **9 + 7
   for num in mlis:
       ans *= fibona(num-mae)
       ans %= infi
       mae = num + 1

    nobori = n - mae + 1
    ans *= fibona(nobori) 
    ans %= infi
    print(int(ans))
    



if __name__ == "__main__":
    main()

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 fibona(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]

def main():
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = 0

    infi = 10 ** 9 + 7
    for num in mlis:
        ans *= fibona(num-mae)
        ans %= infi
        mae = num + 1

    nobori = n - mae + 1
    ans *= fibona(nobori) 
    ans %= infi
    print(int(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):
mod = 10**9+7
n,m = map(int,input().split())

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

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

for i in range(m):
    if dp[i] != -1:
        if dp[i+1] != -1:
            dp[i+1] += dp[i]
        if dp[i+2] != -1:
            dp[i+2] += dp[i]

print(dp[n]%mod)

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

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

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

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

print(dp[n]%mod)


Verdicts: Wrong Answer

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

Submission attempts (in order):
n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 1)
pat[0] = 1
pat[1] = 1
for i in range(m):
    pat[i] = -1

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

print(pat[n])


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

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

print(pat[n])


n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 2)
pat[0] = 1
pat[1] = 1

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

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

print(pat[n])


Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
import sys
input = sys.stdin.readline

def basic_step_ptn_nums(x): 
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) 
        dp[:2] = 1, 1 
        for i in range(2, x+1):
            dp[i] = dp[i-1] + dp[i-2] 
        print(dp[-1])

basic_step_ptn_nums(8)


import sys
input = sys.stdin.readline

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

def ptn_num(x): 
    dp = [0] * (x+1) 
    if 1 in broken: 
        dp[:2] = 1, 0
    else:
        dp[:2] = 1, 1 

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

ptn_num(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):
MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
A[1]=2
for i in range(m):
  A[int(input())-1]=0
if A[0]==0:
  A[1]=1


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

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



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])

MOD=10**9+7
n,m=map(int,input().split())
A=[1 for i in range(n)]
if n!=1:
  A[1]=2
  for i in range(m):
    A[int(input())-1]=0
  
  if A[0]==0 and A[1]!=0:
    A[1]=1



  for i in range(2,n):
    if A[i]!=0:
      A[i]=(A[i-1]+A[i-2])
      A[i]%=MOD

    
  print(A[n-1])
  
else:print(1)

Verdicts: Runtime Error

Runtime Error

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

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

A = []

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

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[N])


from sys import exit

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

_a = -1
A = []
ans = 0

for _ in range(M):
    a_ = int(input())
    if _a + 1 == a_:
        print(0)
        exit()
    _a = a_
    A.append(_a)

step = [] * N
step[0] = 1

for s in range(1, N + 1):
    if s in A:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = (step[s - 1] + step[s - 2]) % 1000000007

print(step[N])


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

A = [False] * (N + 1)

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

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[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):
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor(left + right)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle - 1
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 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):
from collections import defaultdict
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dict = defaultdict(int)
for a in A:
    dict[a] += 1

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if dict[1] == 0 else dp[1] = 0
for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])

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

mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
if dict[1] == 0:
    dp[1] = 1

for i in range(1, N):
    if dict[i] == 0 and dict[i-1] == 0:
        dp[i+1] += ((dp[i-1] + dp[i]) % mod)
    elif dict[i] == 0:
        dp[i+1] += (dp[i] % mod)
    elif dict[i-1] == 0:
        dp[i+1] += (dp[i-1] % mod)

print(dp[-1])



Verdicts: Runtime Error

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

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
    
X = [0]*(N+2)

for i in range(2, N+2):
    if X[i] not in A:
        X[i] = min(X[i-1], X[i-2]) + 1

print(X[N+1]%mod)

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

mod = 1000000007

A = []
for i in range(M):
    A.append(int(input()))
A=set(A)
    
DP = [0]*(N+2)
DP[1] = 1

for i in range(2, N+2):
    if i-1 not in A:
        DP[i] =  DP[i-1]%mod + DP[i-2]%mod

print(DP[N+1]%mod)

Verdicts: Wrong Answer

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

Submission attempts (in order):
def main():
  N, M= map(int, input().split())
  a =[str(input()) for _ in range(M)]
  DP = [0]*(N+1)
  num = 1000000007
  DP[0] = 1
  for i in range(N):
    if str(i) in a:
      DP[i] = (DP[i-1] + DP[i-2]) % num
  print(DP[-2]%num)
if __name__ == "__main__":
    main()

def main():
  N, M= map(int, input().split())
  a =[str(input()) for _ in range(M)]
  DP = [0]*(N+1)
  num = 1000000007
  DP[0] = 1
  for i in range(N):
    if str(i) in a:
      DP[i] = (DP[i-1] + DP[i-2]) % num
  print(DP[-1]%num)
if __name__ == "__main__":
    main()

N, M, = map(int, input().split())
a = set([int(input()) for _ in range(M)])
DP = [0]*(N+2)
num = 1000000007
DP[0] = 1
for i in range(N):
  if i in a:
    DP[i] = 0
  else:
    DP[i] = DP[i] % num 
    if i < N:
      DP[i+1] += DP[i]
      DP[i+2] += DP[i]
print(DP[-2]%num)


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_lst = []
for _ in range(M):
    broken_lst.append(int(input()))

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = broken_lst[0]

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken or i + 2 == last_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])


N, M = map(int, input().split())
broken_lst = [1]*(N+1)
for _ in range(M):
    broken_lst[int(input())] = 0

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


for i in range(0, N-1):
    counter_arr[i+1] += counter_arr[i] * broken_lst[i+1]
    counter_arr[i+1] %= 10**9 + 7
    counter_arr[i+2] += counter_arr[i] * broken_lst[i+2]
    counter_arr[i+2] %= 10**9 + 7

counter_arr[-1] += counter_arr[-2] * broken_lst[-1]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])


Verdicts: Runtime Error

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

Submission attempts (in order):
n, m = map(int,input().split())
a = list(int(input()) for _ in range(m))
dp = [[] for _ in range(n + 1)]
dp[0] = 1
# j = 0
if m = 0:
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    print(dp[n])
    exit()
if a[0] == 1:
    dp[1] = 0
    j = 1
else:
    dp[1] = 1
    j = 0
for i in range(2, n + 1):
    # print(i, dp)
    if j < m:
        if a[j]  == i:
            dp[i] = 0
            j += 1
            continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

n, m = map(int,input().split())
a = list(int(input()) for _ in range(m))
dp = [[] for _ in range(n + 1)]
dp[0] = 1
# j = 0
if m == 0:
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    print(dp[n])
    exit()
if a[0] == 1:
    dp[1] = 0
    j = 1
else:
    dp[1] = 1
    j = 0
for i in range(2, n + 1):
    # print(i, dp)
    if j < m:
        if a[j]  == i:
            dp[i] = 0
            j += 1
            continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

Verdicts: Runtime Error

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

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

mod = 1000000007

dp = [0] * (N + 1)

if len(dp) <= 2:
  return 1

dp[-1] = 1
dp[-2] = 1 if N - 1 not in A else 0

for i in range(N-2, -1, -1):
  if i not in A:
    dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % mod)


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

mod = 1000000007

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

for i in range(N-1, -1, -1):
  if i not in A:
    dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % 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())
data = []
for i in range(M):
    data.append(int(input()))
dp = [-1] * (N + 1)
dp[0] = 1
dp[1] = 1
for i in data:
    dp[i] = 0
if 1 in data:
    dp[1] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if dp[i] != 0:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
print(dp[N] % mod)

def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == -1:
        print(0)
        exit()
    else:
        return 0
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1
if 1 in data:
    dp[1] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if not i in data:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
print(dp[N] % mod)

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

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

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

Submission attempts (in order):
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
A.append(N+1)
out = 1
s = [1,2]
if A[0] != 1:
    hoge = [A[0]-2]
else:
    hoge = []

for i in range(N-M):
    s.append(s[i]+s[i+1])

for k in range(M):
    if A[k+1]-A[k]-2 != int(-1):
        hoge.append(A[k+1]-A[k]-3)
    else:
        out = 0
        break

print(hoge)

for j in hoge:
    out *= s[j]
    out = out%10000000007

print(out%10000000007)

N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
A.append(N+1)
m=0
if A[0] != 1:
    s=[1,1]
else:
    s = [1,0]
    m = 1

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


print(s[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())
cnt = 0
lists = []
kaidan = list(range(N+1))
ans = []
for i in range(M):
    a = int(input())
    lists.append(a)

def dfs(i):
    if i == N:
        return cnt + 1
    
    if i > N:
        return False

    if i in lists:
        return False
    
    if dfs(i+1):
        return dfs(i+1)
    
    if dfs(i+2):
        return dfs(i+2)

    return False

m = dfs(0)
print(m+m)

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

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

Verdicts: Runtime Error

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, b, c = list(map(int, input().split()))
a = [int(input()) for i in range(m)]

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m > 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    print(i)
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)


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

mod = pow(10, 9)+7
point = [0]*(n+1)
point[0] = 1
j = 0
if 1 in a:
    point[1] = 0
    if m >= 2:
        j += 1
else:
    point[1] = 1

if m == 0:
    a = [0]

for i in range(2, n+1):
    if i == a[j]:
        if j < m-1:
            j += 1
    else:
        point[i] = point[i-1]+point[i-2]
        point[i] %= mod

print(point[-1] % mod)


Verdicts: Wrong Answer

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

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

print(a)

mod = 10 ** 9 + 7

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

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

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

mod = 10 ** 9 + 7

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

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

Verdicts: Wrong Answer

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

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

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

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

j = 0
sum = []

for i in range(M+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

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

j = 0
sum = []

for i in range(N+1):
    if j < M and i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Verdicts: Runtime Error

Runtime Error

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

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


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


R = len(a) - 1
for i in range(R):
    x = a[i + 1] - a[i] -1
    pattern.append(fibonacci(x))


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


s1 = fibonacci(a[0])
s2 = fibonacci(N - a[-1])


ans = ans * s1 * s2 % 1000000007


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

print(ans)


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

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

print(dp[N] % MOD)


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

for i in a:
    dp[i] = 0

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

print(dp[N] % MOD)


Verdicts: Runtime Error

Runtime Error

Accepted