Problem:


Score : 300 points

Problem Statement

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.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

now = 0

if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if N >= 2:
    if 2 not in A:
        tmp[2] = tmp[1] + 1
    
    else:
        now += 1

if now >= M:
    now = 0

for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

now = 0

if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if N >= 2:
    if 2 not in A:
        tmp[2] = tmp[1] + 1
    
    else:
        now += 1

if now == M:
    now -= 1

for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

now = 0

if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if N >= 2:
    if 2 not in A:
        tmp[2] = tmp[1] + 1
    
    else:
        now += 1


for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

now = 0

if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if 2 not in A and N >= 2:
    tmp[2] = tmp[1] + 1
    
else:
    now += 1


for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

if 1 not in A:
    tmp[1] = 1
    
if 2 not in A and N >= 2:
    tmp[2] = tmp[1] + 1

now = 0
for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M - 1:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

if 1 not in A:
    tmp[1] = 1
    
if 2 not in A and N >= 2:
    tmp[2] = tmp[1] + 1

now = 0
for i in range(3, N+1):
    
    if i != A[now]:
        tmp[i] = tmp[i-1] + tmp[i-2] 
        
    else:
        if now < M:
            now += 1
        

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

if 1 not in A:
    tmp[1] = 1
    
if 2 not in A:
    tmp[2] = tmp[1] + 1

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

    
print(tmp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
li = []
for i in range(M):
  li.append(int(input()))

# 例外処理
if li[-1] == N:
  print(0)
  sys.exit()

step_li = [0, 1]
result = 0
for i in range(2, N+2):
  if i-1 not in li:
    step_li.append(step_li[i-1] + step_li[i-2])
  else:
    step_li.append(0)
    
print(step_li[-1] % 1000000007)

Submission status: Runtime Error

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

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

for i in b:
    total *= c[i - 1]

print(total % 1000000007)

Submission status: Runtime Error

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

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

for i in b:
    total *= c[i - 1]
    if i - 1 == -1:
        total = 0

print(total % 1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

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

# a[i] = 0 の床は踏めない
a = np.ones(n+1, dtype=np.bool)
for _ in range(m):
    a[int(input())] = 0

mod = 1e9 + 7

# pos[i]はi段目まで登る場合の数
pos = np.zeros(n+1)
pos[0] = 1
for i in range(n):
    if i == n - 1:
        pos[i+1] += pos[i]
    else:
        if a[i+1]:
            pos[i+1] += pos[i]
        if a[i+2]:
            pos[i+2] += pos[i]

print(int(pos[n] % mod))

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
b.append(int(a[0]))
for i in range(len(a) - 1):
    b.append(int(a[i + 1]) - int(a[i]) - 1)
for i in range(max(b)):
    total_act3 = total_act2 + total_act
    total_act2 = total_act
    total_act = total_act3
    c.append(total_act)
for i in b:
    total *= c[i - 1]

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

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
b.append(int(a[0]))
for i in range(len(a) - 1):
    b.append(int(a[i + 1]) - int(a[i]) - 1)
print(b)
for i in range(max(b)):
    total_act3 = total_act2 + total_act
    total_act2 = total_act
    total_act = total_act3
    c.append(total_act)
print(c)
for i in b:
    total *= c[i - 1]

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
b=0 in range(N)
for i in range(M):
    a.append(int(input()))
j=M-1
if j>=0 and a[0]==1:
    f1=0
    f2=1
elif j>=0 and a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if j==-1 or ((n-1)!=a[j] and (n-2)!=a[j]):
            return (f(n-1,a,j)+f(n-2,a,j))%100000007
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif j>0 and (n-1)==a[j]:
            return f(n-2,a,j-1)%100000007
        elif (n-1)==a[j]:
            return f(n-2,a,j)
        elif (n-2)==a[j]:
            return f(n-1,a,j)%100000007
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j)%100000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
b=0 in range(N)
for i in range(M):
    a.append(int(input()))
j=M-1
if j>=0 and a[0]==1:
    f1=0
    f2=1
elif j>=0 and a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if j==-1 or ((n-1)!=a[j] and (n-2)!=a[j]):
            return (f(n-1,a,j)+f(n-2,a,j))%100000007
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
            return f(n-2,a,j-1)%100000007
        elif (n-2)==a[j]:
            return f(n-1,a,j)%100000007
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j)%100000007)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
b=0 in range(N)
for i in range(M):
    a.append(int(input()))
j=M-1
if j>=0 and a[0]==1:
    f1=0
    f2=1
elif j>=0 and a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if j==-1 or ((n-1)!=a[j] and (n-2)!=a[j]):
            return f(n-1,a,j)+f(n-2,a,j)
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
            return f(n-2,a,j-1)
        elif (n-2)==a[j]:
            return f(n-1,a,j)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
b=0 in range(N)
for i in range(M):
    a.append(int(input()))
j=M-1
if a[0]==1:
    f1=0
    f2=1
elif a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if (n-1)!=a[j] and (n-2)!=a[j]:
            return f(n-1,a,j)+f(n-2,a,j)
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
            return f(n-2,a,j-1)
        elif (n-2)==a[j]:
            return f(n-1,a,j)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

Submission status: Runtime Error

Solution code:
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])

Submission status: Runtime Error

Solution code:
import queue
from collections import deque



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

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

oneBreak = False
for m in range(M):
    inp = int(input())
    if inp == 1:
        oneBreak = True
    else:
        A.append(inp)


DP = [0] * (N+1)

DP[0] = 1

if(oneBreak):
    DP[1] = 0
else:
    DP[1] = 1
#壊れている階段の時は判定をスキップ（DPテーブルは0のまま）

if(M != 0):
    nowA = A.popleft()
    for n in range(2,N + 1):
        if(nowA == n):
            if(len(A) != 0):
                nowA = A.popleft()
            else:
                nowA = -1
        else:
            DP[n]  = (DP[n-1] + DP[n-2])

else:
    for n in range(2,N+1):
        DP[n] = DP[n-1] + DP[n-2]


print(DP[n]%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
    ans *= num_way(end-start)
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
    print(end,start)
    ans *= num_way(end-start)
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import queue

"""
129-C
もうすこし　がんばろう

""""


N,M = map(int,input().split(" "))
A = queue.Queue()

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

oneBreak = False
for m in range(M):
    inp = int(input())
    if inp == 1:
        oneBreak = True
    else:
        A.put(inp)


DP = [0] * (N+1)

DP[0] = 1

if(oneBreak):
    DP[1] = 0
else:
    DP[1] = 1
#壊れている階段の時は判定をスキップ（DPテーブルは0のまま）

if(M != 0):
    nowA = A.get()
    for n in range(2,N + 1):
        if(nowA == n):
            if(not A.empty()):
                nowA = A.get()
            else:
                nowA = -1
        else:
            DP[n]  = (DP[n-1] + DP[n-2])

else:
    for n in range(2,N+1):
        DP[n] = DP[n-1] + DP[n-2]


print(DP[n]%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m=map(int, input().split()) 
broken_list = np.array([int(input()) for i in np.arange(m)])

stages = np.append(broken_list, n+1)-np.append(0,broken_list)-2
if stages[0]==-1:
    stages[0]=0
stages
def fib(n):
    if n<0:
        return 0
    else:
        f = ((1 + 5**0.5) / 2)**(n+1) / 5**0.5 + 0.5
        return int(f)
      
fibs = [fib(n)%1000000007 for n in stages]
result = 1
for i in fibs:
    result *= i
    result%=1000000007
    
print(result)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1:
      return 1
    elif stair == 0:
      return 1
    elif stair == 2:
      return 2
    elif memo[stair] != "EMPTY":
      return memo[stair]
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = []
mod = 10**9+7
for i in range(m):
    temp = int(input())
    a.append(temp)

a.append(0)

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
k = []
count_sub = 0
steps = []
j = 0
for i in range(m):
    k.append(int(input())) 
    if len(k)>1 and k[i]-k[i-1]==1:
        count_sub = 1
        
if count_sub ==1:
    steps = [0 for i in range(n)]  
else:
    for i in range(n+1):
        if k[j]==i:
            steps.append(0)
            if j < len(k)-1:
                j = j + 1
        elif i ==0:
            steps.append(1)
        elif i ==1:
            steps.append(1)  
        else:
            steps.append(steps[i-1]+steps[i-2])
 
print(steps[-1]%(1000000007))

Submission status: Runtime Error

Solution code:
import numpy as np

n,m=map(int, input().split()) 
broken_list = np.array([])
for i in np.arange(m):
    broken_list = np.append(broken_list,int(input()))

stages = np.append(broken_list, n+1)-np.append(0,broken_list)-2
if stages[0]==-1:
    stages[0]=0
stages
def fib(n):
    if n<0:
        return 0
    else:
        f = ((1 + 5**0.5) / 2)**(n+1) / 5**0.5 + 0.5
        return int(f)
      
fibs = [fib(n)%1000000007 for n in stages]
result = 1
for i in fibs:
    result *= i
    result%=1000000007
    
print(result)

Submission status: Runtime Error

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

a.append(0)

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
j=M-1
if a[0]==1:
    f1=0
    f2=1
elif a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    if n>2:
        if (n-1)!=a[j] and (n-2)!=a[j]:
            if n>3 and n-3==a[j]:
                return f(n-1,a,j)+f(n-2,a,j-1)
            else:
                return f(n-1,a,j)+f(n-2,a,j)
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
             if n>3 and j>0 and n-3==a[j-1]:
                return f(n-2,a,j-1)
             else:
                return f(n-2,a,j)
        elif (n-2)==a[j]:
            return f(n-1,a,j-1)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
j=M-1
if a[0]==1:
    f1=0
    f2=1
elif a[0]==2:
    f1=1
    f2=1
else:
    f1=1
    f2=2
def f(n,a,j):
    print("a")
    if n>2:
        if (n-1)!=a[j] and (n-2)!=a[j]:
            if n>3 and n-3==a[j]:
                return f(n-1,a,j)+f(n-2,a,j-1)
            else:
                return f(n-1,a,j)+f(n-2,a,j)
        if j>0 and a[j]==a[j-1]+1:
            return 0
        if j+1<M and a[j+1]==a[j]+1:
            return 0
        elif (n-1)==a[j]:
             if n>3 and j>0 and n-3==a[j-1]:
                return f(n-2,a,j-1)
             else:
                return f(n-2,a,j)
        elif (n-2)==a[j]:
            return f(n-1,a,j-1)
    elif n==1:
        return f1
    else:
        return f2
print(f(N,a,j))

Submission status: Runtime Error

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

a.append(0)

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

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=map(int, input().split()) 
broken_list = np.array([])
for i in np.arange(m):
    broken_list = np.append(broken_list,int(input()))
    
stages = np.append(broken_list, n+1)-np.append(0,broken_list)-1
stages

def fib(n):
    if n==0:
        return 0
    else:
        f = ((1 + 5**0.5) / 2)**(n+1) / 5**0.5 + 0.5
        return int(f)
      
fibs = [fib(n)%1000000007 for n in stages]

result = 1
for i in fibs:
    result *= i

print(result)

Submission status: Runtime Error

Solution code:
mod = 1000000007

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

if nums[0] == 1:
	del nums[0]
else:
	dp[1] = 1
	

for i in range(2, n + 1):
	#print(i, dp, nums)
	if len(nums) ==  0:
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	else:
		for j in range(len(nums)):
			if nums[j] > i:
				dp[i] = (dp[i - 1] + dp[i - 2]) % mod
				break
			elif nums[j] == i:
				del nums[:(j + 1)]
				break
#print(nums)
#print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
def fio(x,y):
    return x+y

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

n = [0,1,2]

for i in range(1,100000):
    n.append(fio(n[i],n[i+1]))

last_break = 0
ans = 1
ans = ans * n[a[0]-last_break-1]
ans = ans % 1000000007
last_break = a[0]

if a[0] == 1:
    ans = 1
    
for i in range(1,m):
    ans = ans * n[max(0,a[i]-last_break-2)]
    ans = ans % 1000000007
    last_break = a[i]
    
ans = ans * n[n_a-last_break-1]
ans = ans % 1000000007
if m == 0:
    ans = n[n_a]
    ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

stairs = [0] * (N + 1)

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])

    #print(stairs)

print(stairs[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(stair):
  memo = ["EMPTY"]*(stair+1)
  def _fib(stair):
    if stair == 1 or stair == 0:
      return 1
    elif stair == 2:
      return 2
    else:
      memo[stair] = _fib(stair-1)+_fib(stair-2)
      return memo[stair]
  return _fib(stair)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if(end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

import numpy as np

stairs = list(np.zeros(N + 1))

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])

    #print(stairs)

print(stairs[-1] % 1000000007)

Submission status: Runtime Error

Solution code:

a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
try:
	max = 0
	min = a[0]+100
	for x in c:
	    if x>max:
	        max=x
	    if x<min:
	        min=x
	        
	#print(c)
#pr	int(max," ",min)
	if min==0:
   		print(0)
	else:
    	num=[0]*(max)
  		for x in range(max):
        	if x==0:
            	num[0]=1
        	elif x==1:
            	num[1]=1
        	else:
            	num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    	answer=1
    	for x in c:
        	answer *=num[x-1]
        	answer%=1000000007
    	print(answer)
except:
	print(0)

Submission status: Runtime Error

Solution code:
try:
    a = list(map(int, input().split()))
    #print(a)
    b=[0]*a[1]
    c=[0]*(a[1]+1)
    b[0]=int(input())
    c[0]=b[0]-0
    for x in range(a[1]-1):
        b[x+1]=int(input())
        c[x+1]=b[x+1]-b[x]-1
    c[-1]=a[0]-b[-1]
    max = 0
    min = a[0]+100
    for x in c:
        if x>max:
            max=x
        if x<min:
            min=x
        
    #print(c)
    #print(max," ",min)
    if min==0:
        print(0)
    else:
        num=[0]*(max)
        for x in range(max):
            if x==0:
                num[0]=1
            elif x==1:
                num[1]=1
            else:
                num[x]=num[x-1]+num[x-2]
            #print("num[",x,"]=",num[x])
        
        answer=1
    
        for x in c:
            answer *=num[x-1]
            if answer==0:
                print(0)
                break
            else:
                answer%=1000000007
        print(answer)
    except:
        print(0)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

import numpy as np

stairs = list(np.zeros(N + 1))

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i > 2:
      
        if i in a:

        	stairs[i] = 0

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])

    #print(stairs)

print(stairs[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    try:
        for x in c:
            answer *=num[x-1]
            if answer==0:
                print(0)
                break
            else:
                answer%=1000000007
        print(answer)
    except:
        print(0)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    try:
        num=[0]*(max)
        for x in range(max):
            if x==0:
                num[0]=1
            elif x==1:
                num[1]=1
            else:
                num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
    except:
        print(0)
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

Solution code:
# C
# Typical Stairs

N_M = input()

N = int(N_M.split(" ")[0])
M = int(N_M.split(" ")[1])

a = []

for i in range(M):

    a.append(int(input()))

#print(a)

import numpy as np

stairs = list(np.zeros(N + 1))

if 1 in a:

    stairs[1] = 0
    stairs[2] = 1

elif 2 in a:

    stairs[1] = 1
    stairs[2] = 0

elif 1 in a and 2 in a:

    stairs[1] = 0
    stairs[2] = 0

else:

    stairs[1] = 1
    stairs[2] = 2

for i in range(N + 1):
    
    if i in a:

        stairs[i] = 0
    
    elif i > 2:

        stairs[i] = int(stairs[i - 1] + stairs[i - 2])%1000000007

    #print(stairs)

print(stairs[-1])

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
try:
    b=[0]*a[1]
    c=[0]*(a[1]+1)
    b[0]=int(input())
    c[0]=b[0]-0
    for x in range(a[1]-1):
        b[x+1]=int(input())
        c[x+1]=b[x+1]-b[x]-1
    c[-1]=a[0]-b[-1]
    max = 0
    min = a[0]+100
    for x in c:
        if x>max:
            max=x
        if x<min:
            min=x
except:
    print(0)
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
#print(a)
try:
    b=[0]*a[1]
    c=[0]*(a[1]+1)
    b[0]=int(input())
    c[0]=b[0]-0
    for x in range(a[1]-1):
        b[x+1]=int(input())
        c[x+1]=b[x+1]-b[x]-1
    c[-1]=a[0]-b[-1]
    max = 0
    min = a[0]+100
except:
    print(0)
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
        if answer==0:
            print(0)
            break
        else:
            answer%=1000000007
    print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

def num_way(n):
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 2:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)

N, M = map(int,input().split())
a = deque([0])
path_poss = 1
ans = 1
for m in range(M):
  start = a.popleft()
  buff = int(input())
  end = buff-1
  if (end-start) <= -1:
    path_poss = 0
    break
  a.append(buff+1)
  ans *= num_way(end-start)
  ans %= 1000000007

if path_poss == 0:
  print(0)
else:
  start = a.popleft()
  end = N
  if (end-start) <= -1:
    path_poss = 0
  if path_poss == 0:
    print(0)
  else:
  	ans *= num_way(end-start)
  	print(ans%1000000007)