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

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_set, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_set:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_set, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_set, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N*2)

    answer = 1
    if a[-1::] == N:
        answer = 0

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

    if answer != 0:
        answer = calc_state_number(N, 0, set(a), memo)

    print(answer)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

now = 0
count = 1
mod = 7+10**9
for i in a:
    count *= fib(i-now)
    count = count%mod
    if now == i:
        print(0)
        quit()
    now = i+1

count *= fib(N-now+1)

print(count%mod)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

now = 0
count = 1
for i in a:
    count *= fib(i-now)
    if now != 0 and now+1 == i:
        print(0)
        quit()
    now = i+1

count *= fib(N-now+1)

mod = 7+10**9
print(count%mod)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[0]*M
for i in range(M):
  a[i]=int(input())
dp=[1]*(N+1)
mod=10**9+7
if M !=0:
  j=0
  if a[j]==1:
    j=j+1
    dp[1]=0
  for i in range(2,N+1):
    if j==0:
      if i==a[j]:
        dp[i]=0
        if j < M-1:
          j=j+1
        else:
          a[j]=-1
      else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    else:
      if i==a[j] and i-1 !=a[j-1]:
        dp[i]=0
        if j < M-1:
          j=j+1
        else:
          a[j]=-1
      elif i==a[j] and i-1 ==a[j-1]:
        dp[N]=0
        break
      elif i-2 ==a[j-1]:
        dp[i]=dp[i-1]
      elif i-1 ==a[j-1]:
        dp[i]=dp[i-2]
      elif i-1 !=a[j-1] and i-2 !=a[j-1]:
        dp[i]=(dp[i-1]+dp[i-2])%mod
else:
  for i in range(2,N+1):
    dp[i]=(dp[i-1]+dp[i-2])%mod 
print(dp[N]%mod)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[0]*M
for i in range(M):
  a[i]=int(input())
dp=[1]*(N+1)
mod=10**9+7
j=0
if a[j]==1:
  j=j+1
  dp[1]=0
for i in range(2,N+1):
  if j==0:
    if i==a[j]:
      dp[i]=0
      if j < M-1:
        j=j+1
      else:
        a[j]=-1
    else:
      dp[i]=(dp[i-1]+dp[i-2])%mod
  else:
    if i==a[j] and i-1 !=a[j-1]:
      dp[i]=0
      if j < M-1:
        j=j+1
      else:
        a[j]=-1
    elif i==a[j] and i-1 ==a[j-1]:
      dp[N]=0
      break
    elif i-2 ==a[j-1]:
      dp[i]=dp[i-1]
    elif i-1 ==a[j-1]:
      dp[i]=dp[i-2]
    elif i-1 !=a[j-1] and i-2 !=a[j-1]:
      dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)

Submission status: Runtime Error

Solution code:

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = [INT() for _ in range(M)]

b = [0] * (N + 2)
# 壊れているところが1
for i in A:
    b[i] = 1

dp = [0] * (N + 2)
# for i in range():

dp[0] = 1

if b[1] == 1:
    # あなあいてるのでそのルートは考えられない
    dp[1] = 0
else:
    dp[1] = 1

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

ans = dp[i] % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N*2)

    answer = 1
    if a[-1::] == N:
        answer = 0

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

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)

    print(answer)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        return 0
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N+2)

    answer = 1
    if a[-1::] == N:
        answer = 0

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

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)

    print(answer)

Submission status: Runtime Error

Solution code:
def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        return 0
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N+2)

    answer = 1
    if a[-1::] == N:
        answer = 0

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

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)
    
    print(answer)

Submission status: Runtime Error

Solution code:
ini=input().split()
ini=[int(i) for i in ini]
N=ini[0]
M=ini[1]

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

#print(a)
ans=1
def fib(n):
    
    atai = 1
    atai2 = 2
   # global atai,atai2
    if n==1:
        atai2=1
        return atai2
    if n==2:
        atai2=2
        return atai2
    else:
        for i in range(1,n):
            temp=atai2
            atai2=atai+temp
            atai=temp
        return atai2
#print(N,M)
for i in range(M+2):
    b=a[i+1]-a[i]-1
    # if i==M:
    #     ans=ans*fib(N-a[i]-1)
    #     print("iff",ans,fib(N-a[i]-1))
    if b==0 and a[1]!=1:
        ans=0
        break
    if b>0:
        ans=ans*fib(b)
#        if ans>1000000007:
        ans=ans % 1000000007
#        print("if",ans,fib(b))
#        print(ans,fib(b),c[i])

ans=ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

num = [0 for i in range(N)]
for i in range(M):
    num[a[i] - 1] = 1000000008
if num[0] == 0:
    num[0] = 1
if num[1] == 0:
    num[1] = 1 + min(1000000007, num[0])
    num[1] = num[1] % 1000000007
for i in range(2, N):
    if num[i] < 1000000008:
        num[i] = min(1000000007, num[i - 1]) + min(1000000007, num[i - 2])
        num[i] = num[i] % 1000000007
print(num[N - 1])

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
a = [int(input()) for _ in range(m)]
if 1 in a:
    ans = [0,1]
elif 2 in a:
    ans = [1,0]
else:
    ans = [1,2]
if n == 1:
    print(ans[0])
    sys.exit()
elif n == 2:
    print(ans[1])
    sys.exit()
else:
    for i in range(2,n):
        if i+1 not in a:
            ans.append((ans[i-1]+ans[i-2])%1000000007)
        else:
            ans.append(0)
    print(ans[len(ans)-1]%1000000007)

Submission status: Runtime Error

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

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

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = [(a[i+1] - a[i]) - 2 for i in range(len(a)-1)]

ans = 1
for j in danns:
    ans *= comb(j) % 1000000007
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = [0] * n
num[0] = int(0 not in broken)
num[1] = int(1 not in broken)

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
num = {0: int(0 not in broken), 1: int(1 not in broken)}

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
        
print((num[n-1]+num[n-2])%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
num = {0: int(0 not in broken), 1: int(1 not in broken)}

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = num[i-1] + num[i-2]
        
print((num[n-1]+num[n-2])%(1000000007))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = {0: int(0 not in broken), 1: int(1 not in broken)}

for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = num[i-1] + num[i-2]
        
print((num[n-1]+num[n-2])%(1000000007))

Submission status: Runtime Error

Solution code:
def step(n, A):
    memo = A
    def _step(n):
        if memo[n] != -1:
            return memo[n]
        elif n == 1:
            return 1
        elif n == 2:
            if memo[1] == 0:
                return 1
            else:
                return 2
        memo[n] = (_step(n-1) + _step(n-2))%(10**9+7)
        return memo[n]
    return _step(n)

N, M = map(int, input().split())
A = [-1] * (N+1)
for _ in range(M):
    idx = int(input())
    A[idx] = 0
print(step(N, A))

Submission status: Runtime Error

Solution code:
def step(n, A):
    memo = A
    def _step(n):
        if memo[n] != -1:
            return memo[n]
        elif n == 1:
            return 1
        elif n == 2:
            if memo[1] == 0:
                return 1
            else:
                return 2
        memo[n] = _step(n-1) + _step(n-2)
        return memo[n]
    return _step(n)

N, M = map(int, input().split())
A = [-1] * (N+1)
for _ in range(M):
    idx = int(input())
    A[idx] = 0
print(step(N, A)%(10**9+7))

Submission status: Runtime Error

Solution code:
import logging
from math import factorial

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

steps_memo =[0 for _ in range(100000)]
def cal_steps(num):
    steps_memo[0] = 1
    steps_memo[1] = 1

    for i in range(2, num):
        steps_memo[i] = steps_memo[i - 1] + steps_memo[i - 2]

    return steps_memo[num - 1]
    
def main():
    N, M = (int(x) for x in input().split())
    a_s = [int(input()) for _ in range(M)]

    logging.info(a_s)
    
    a_s.append(N + 1)
    a_s.insert(0, -1)
    diff_a = [a_s[i + 1] - a_s[i] - 1 for i in range(M + 1)]

    if diff_a[0] == 0:
        diff_a[0] = 1
    
    logging.info(diff_a)

    
    answer = 1
    for i in diff_a:
        answer *= int(cal_steps(i))

    print(answer % (10 ** 9 + 7))
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import logging
from math import factorial

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

steps_memo =[0 for _ in range(10000)]
def cal_steps(num):
    steps_memo[0] = 1
    steps_memo[1] = 1

    for i in range(2, num):
        steps_memo[i] = steps_memo[i - 1] + steps_memo[i - 2]

    return steps_memo[num - 1]
    
def main():
    N, M = (int(x) for x in input().split())
    a_s = [int(input()) for _ in range(M)]

    logging.info(a_s)
    
    a_s.append(N + 1)
    a_s.insert(0, -1)
    diff_a = [a_s[i + 1] - a_s[i] - 1 for i in range(M + 1)]

    if diff_a[0] == 0:
        diff_a[0] = 1
    
    logging.info(diff_a)

    
    answer = 1
    for i in diff_a:
        answer *= int(cal_steps(i))

    print(answer % (10 ** 9 + 7))
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
v=[a[0]-1]
ans=1

def x(z):
    if z>1:
        return x(z-1)+z-2
    else:
        return 2
if m==1:
    v.append(n-a[0]-1)
    
else:
    for i in range(m-1):
        v.append(a[i+1]-a[i]-1)
    v.append(n-a[m-1]-1)
    
if v[1:].count(0)>=1:
    print(0)
    exit()

for i in range(m+1):
    if v[i]==1 or v[i]==0:
        pass
    else:
        ans*=x(v[i])
        if ans>=1000000007: 
            ans=ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(30000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))

Submission status: Runtime Error

Solution code:
import bisect
M = 1000000007

# def dfs(i):
#     if i >= n - 1:
#         return 1
#     if dp[i] is not None:
#         return dp[i]
#     if i <= maxv and a[bisect.bisect_left(a, i)] == i:
#         dp[i] = 0
#         return 0
#     r = (dfs(i + 1) + dfs(i + 2)) % M
#     dp[i] = r
#     return r

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.sort()
maxv = max(a)
# dp = [None] * n
# print(dfs(0) % M)

dp = [1] * (n + 2)
for i in range(n - 2, -1, -1):
    if i <= maxv and a[bisect.bisect_left(a, i)] == i:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + dp[i + 2]) % M

print(dp[0] % M)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = [1]*n
#kubaru_dp = [1]*n

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

# l = [1,1,1,0,1,1,1]
for i in range(2,n+1):
    if l[i]==0:
        continue
    l[i] = l[i-1]+l[i-2]
else:
    print(l[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
from scipy.special import comb

def routeCombCount(distance):
  comb_count = 1
  max_skippable_count = distance // 2

  if max_skippable_count == 0:
    return 1

  for skippable_count in range(1, max_skippable_count + 1):
    step_count = distance - skippable_count
    comb_count += comb(step_count, skippable_count, exact=True)

  return comb_count

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

count = 1
aim_stage = N
now_stage = 0
before_broken = -1
for i in range(M):
  broken = int(input())
  if broken == before_broken + 1:
    count = 0
    break

  aim_stage = broken - 1
  distance = aim_stage - now_stage

  count *= routeCombCount(distance)

  before_broken = broken
  now_stage = broken + 1

distance = N - now_stage
count *= routeCombCount(distance)

print(count % 1000000007)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

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

factorial = {0: 1}
f = 1
for i in range(1, N):
    f *= i
    factorial[i] = f

c = {}
def nCr(n, r):
    if (n, r) in c:
        return c[(n, r)]
    a = factorial[n] // (factorial[n - r] * factorial[r])
    c[(n, r)] = a
    return a

d = {}
def step(n):
    if n in d:
        return d[n]
    a = 0
    for k in range(n // 2 + 1):
        a += nCr(n - k, k)
    d[n] = a
    return a

ans = 1
for i in range(M + 1):
    n = a[i + 1] - a[i] - 2
    if n < 0:
        ans = 0
    else:
        ans *= step(n)
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
N = []
v = []
def rec(n):
	global N
	global v
	if v[n] != -1:
		return v[n]

	if N[n] == 1:
		v[n] = 0
	elif n == 1:
		v[n] = 1
	elif N[n-1] == 1:
		v[n] = rec(n-2)
	else:
		v[n] = rec(n-2) + rec(n-1)
	# print("v:", v[n])
	return v[n]

def main():
	global N, v
	n, m = map(int, input().strip().split())
	N = [0] * (n+1)
	v = [-1] * (n+1)
	v[0] = 1
	for i in range(m):
		a = int(input().strip())
		N[a] = 1
	# print(v)
	# print(N)
	print(rec(n) % (10**9+7))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = []
v = []
def rec(n):
	global N
	global v
	if v[n] != -1:
		return v[n]

	if N[n] == 1:
		v[n] = 0
	elif n == 1:
		v[n] = 1
	elif N[n-1] == 1:
		v[n] = rec(n-2)
	else:
		v[n] = rec(n-2) + rec(n-1)
	# print("v:", v[n])
	return v[n]

def main():
	global N, v
	n, m = map(int, input().strip().split())
	N = [0] * (n+1)
	v = [-1] * (n+1)
	v[0] = 1
	for i in range(m):
		a = int(input().strip())
		N[a] = 1
	# print(v)
	# print(N)
	print(rec(n) % (10**9+7))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

def steps(n):
    if memo[n] != -1:
        return memo[n]
    if n-1 not in broken:
        one = memo[n-1] if memo[n-1] != -1 else steps(n-1)
    else:
        one = 0
        
    if n-2 not in broken:
        two = memo[n-2] if memo[n-2] != -1 else steps(n-2)
    else:
        two = 0
    
    memo[n] = one + two
    return memo[n]

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

print(steps(n) % (10**9+7))

Submission status: Runtime Error

Solution code:

def cul_1to2(i):
	if i == 1:
		if i not in denger_list:
			ppre_step,pre_step,now_step = pre_step,0,1

		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,0,0

	if i == 2:
		if i not in denger_list:
			if 1 in denger_list:
				ppre_step,pre_step,now_step = pre_step,now_step,1	
			else:
				ppre_step,pre_step,now_step = pre_step,now_step,2
		if i in denger_list:
			ppre_step,pre_step,now_step = pre_step ,now_step,0

	return ppre_step,pre_step,now_step


N,M = map(int,input().split())
step_list = list(range(N+1))
denger_list = list()
for i in range(M):
	denger_list.append(int(input()))


ppre_step = None
pre_step  = None
now_step  = 0

for i in range(N+1):
	if i == 0:
		continue

	if i <= 2:
		ppre_step,pre_step,now_step = cul_1to2(i)
	
	else:
		if i not in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = ppre_step + pre_step
		elif i in denger_list:
			ppre_step = pre_step
			pre_step  = now_step
			now_step  = 0 


print(now_step%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

if M == 0:
    A = []
else:
    A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

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

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

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

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

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

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*N
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

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

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

A = [0]*M

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

A.append(N+1)

# DP version
DP = [0]*N
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

# DP version
DP = [0]*N
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )

Submission status: Runtime Error

Solution code:
import sys
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

# DP version
DP = [0]*N
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
DP[2] = 2

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )