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:
def main(A, dp, n):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2)
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * n
D[0], D[1] = 1, 1
for _ in range(m):
    D[int(input())] = -1
for i in range(2, n):
    if D[i] == -1:
        continue
    if D[i-1] != -1:
        D[i] += D[i-1]
    if D[i-2] != -1:
        D[i] += D[i-2]
    D[i]%=MOD
ans = 0
if D[n-1] != -1:
    ans += D[n-1]
if D[n-2] != -1:
    ans += D[n-2]
print(ans % MOD)

Submission status: Runtime Error

Solution code:
def main(A, dp, n):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2)
print(ans)

Submission status: Runtime Error

Solution code:
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
"""
python3 main.py < input.txt
"""

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""
def genArr2(h,w): return [0]*(h*w)
def setArr2(A,ij,x): A[ij[0]*W + ij[1]] = x
def getArr2(A,ij): return A[ij[0]*W + ij[1]]
H,W=map(int, input().split())
S=genArr2(H,W)
for i in range(H):
        s=input()
        l=list(s)
        for j in range(W):
                setArr2(S,(i,j),l[j])

SWR=genArr2(H,W)
for i in range(H):
        setArr2(SWR, (i, 0), 0 if getArr2(S, (i, 0)) == "#" else 1)
        for j in range(1,W):
                if getArr2(S,( i, j)) == "#": setArr2(SWR, (i, j), 0)
                else: setArr2(SWR, (i, j), getArr2(SWR, (i, j-1)) + 1)
SWL=genArr2(H,W)
for i in range(H):
        setArr2(SWL, (i, W-1), 0 if getArr2(S, (i, W-1)) == "#" else 1)
        for j in range(W-2,-1,-1):
                if getArr2(S,( i, j)) == "#": setArr2(SWL, (i, j), 0)
                else: setArr2(SWL, (i, j), getArr2(SWL, (i, j+1)) + 1)
SHB=genArr2(H,W)
for j in range(W):
        setArr2(SHB, (0, j), 0 if getArr2(S, (0, j)) == "#" else 1)
        for i in range(1,H):
                if getArr2(S,( i, j)) == "#": setArr2(SHB, (i, j), 0)
                else: setArr2(SHB, (i, j), getArr2(SHB, (i-1, j)) + 1)
SHT=genArr2(H,W)
for j in range(W):
        setArr2(SHT, (H-1, j), 0 if getArr2(S, (H-1, j)) == "#" else 1)
        for i in range(H-2, -1, -1):
                if getArr2(S,( i, j)) == "#": setArr2(SHT, (i, j), 0)
                else: setArr2(SHT, (i, j), getArr2(SHT, (i+1, j)) + 1)

ans=0
for n in range(H*W):
        ij=(n//W,n%W)
        x=getArr2(SWR, ij) + getArr2(SWL, ij) + getArr2(SHB, ij) + getArr2(SHT,ij) - 3
        ans=max(ans,x)
print(ans)

Submission status: Runtime Error

Solution code:
def main(A, dp, n):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
dp[N], dp[N-1] = 1, 1
ans = main(A, dp, N-2)
print(ans)

Submission status: Runtime Error

Solution code:
def main(A, dq, n):
    if n == -1:
        return dq[0]

    if (n in A) == False: 
        dp[n] = dp[n + 1] + dp[n + 2]
    return main(A, dq, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
dp[N], dp[N-1] = 1, 1
ans = main(A, dp, N-2)
print(ans % mod)

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(100000)

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

#variable

#function
@lru_cache(maxsize=1000)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return (rootCount(position-1)+rootCount(position-2)) % 1000000007
#class

#main function
def main():
    print(rootCount(N))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def combi(N,R):
  res = 1
  DE = [0]*R
  NU = [0]*R
  for r in range(R):
    DE[r] = (R-r)
    NU[r] = (N-r)
  for d in range(R):
    for n in range(R):
      if NU[n]%DE[n]==0:
        NU[n] = int(NU[n]/DE[n])
  for n in range(R):
    res *= NU[n]%1000000007
  return int(res)
  
def calc_pat(K):
  NMAX = 1000000007
  res = 0
  Mmax = int(K/2)
  for M in range(Mmax+1):
    N=K-M*2
    res = (res+combi(M+N,M))%NMAX
  return res

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

S=[0]*M

flg = False
for n in range(M):
  S[n] = int(input())
  if n>0 and S[n-1]+1==S[n]:
    flg = True

if flg:
  print(0)
else:
  res = 1
  for n in range(M):
    if n==0:
      K = S[n]-1
    else:
      K = S[n]-S[n-1]-2

    if K>1:
      res = (res*calc_pat(K))%NMAX
      
  K = N - S[n] -1
  res = (res*calc_pat(K))%NMAX
  
  print(res)

Submission status: Runtime Error

Solution code:
import math
N,M = [int(x) for x in input().split()]
a = [int(input()) for j in range(M)]
 
def combinations_count(n, r):
        return math.factorial(n)//(math.factorial(n - r) * math.factorial(r))
 
def keisan(n,r):
    count = 0
    while n >= r:
 
        count += combinations_count(n,r)
        n -= 1
        r += 1
 
    return count
result = 1
 
for i in range(M):
    if a[i] - a[i-1] == 1:
        result = 0
        break
    elif i == 0:
        result *= keisan(a[i]-1,0)
    else:
        result *= keisan(a[i]-a[i-1]-2,0)
 
else:
    result *= keisan(N - a[M-1]-1,0)
 
print(int(result)%1000000007)

Submission status: Runtime Error

Solution code:
def main(A, dq, n):
    if n == -1:
        return dq[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dq, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * 10**5
A = [int(input()) for _ in range(M)] 
dp[N], dp[N-1] = 1, 1
ans = main(A, dp, N-2)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy
N,M=map(int,input().split())
a=[0]*M
tori=[0]*N
for num in range(M):
    a[num]=int(input())
count=0

def saiki(gen):
    global count
    if gen+1==N:
        count=count+1
        return
    else:
        saiki(gen+1)
    if gen+2==N:
        count=count+1
        return
    else:
        saiki(gen+2)

def fib(mae,hutatu,gen):
    global tori
    tori[gen-1]=mae+hutatu
    if(gen==N):
        return tori[gen-1]
    fib(tori[gen-1],tori[gen-2],gen+1)

tori[0]=1
tori[1]=2
if(1 in a):
    tori[0]=0
    tori[1]=1
if(2 in a):
    tori[1]=0
gen=3
while(gen<=N):
    tori[gen-1]=(tori[gen-2]+tori[gen-3])%1000000007
    if(gen in a):
        tori[gen-1]=0
    #print(tori[gen-1])
    gen=gen+1

print(tori[N-1])
#print(fib(1,1,3))

Submission status: Runtime Error

Solution code:
H,W = (int(i) for i in input().split())
s = [[-1] * (W + 2) for i in range(H+2)]
t = [[-1] * (W + 2) for i in range(H+2)]
 
for i in range(1, H+1):
    SS = input()
    for j in range(W):
        if SS[j] == "#":
            s[i][j+1] = -1
            t[i][j+1] = -1
        else:
            s[i][j+1] = 0
            t[i][j+1] = 0
 
tmp = []
num = 0
for i in range(1, H+1):
    for j in range(1, W+2):
        if s[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    s[i][tp] = num
                tmp = []
                num =0
        else:
            tmp.append(j)
            num += 1
 
tmp = []
num = 0
for j in range(1, W+1):
    for i in range(1, H+2):
        if t[i][j] == -1 :
            if num != 0:
                for tp in tmp:
                    t[tp][j] = num
                tmp = []
                num =0
        else:
            tmp.append(i)
            num += 1
 
ref = 0
for i in range(H+2):
    for j in range(W+2):
        ref = max(s[i][j] + t[i][j], ref)
 
print(ref-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

def fib(n):
    if n == 0:
        return 0
    else:
        a0 = 0
        a1 = 1
        for i in range(n-1):
            b = a1
            a1 += a0
            a0 = b
        return a1

count = 1
b = 0
for i in range(m):
    a = int(input())
    if a == 1:
        b = 1
        continue
    if num == 1:
        count *= 0
        break
    if b == 0:
        num = a - b
    else:
        num = a - b - 1
    count *= fib(num)
    b = a 
#     print(b, count, num)
    
count *= fib(n - b)

print(count%1000000007)

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(100000)

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

#variable

#function
#@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return rootCount(position-1)+rootCount(position-2)
#class

#main function
def main():
    print(rootCount(N)%1000000007)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


dp = [-1]*(n+1)
dp[0] = 1
for i in para :
    dp[i] = 0

def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if dp[cnt] != 0 :  
                dp[cnt] = (dp[cnt-1] + dp[cnt-2]) % mod
                cnt += 1
            else :
                cnt += 1
        return dps(cnt,cantvisit)
dps(1,para)
print("{}".format(dp[-1]%mod))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5 + 1)

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

def get_num_of_ways(floor_number, broken_floors):
  memo = [-1 for _ in range(floor_number + 1)]
  
  def _fibo(n, skip):
    if n in skip:
      # Be careful n can be 1
      return 0
    if n <= 1:
      return 1
    if memo[n] >= 0:
      return memo[n]
    ways = _fibo(n - 1, skip) + _fibo(n - 2, skip)
    ways %= 1000000007
    memo[n] = ways
    return ways
    
  return _fibo(floor_number, broken_floors)

print(get_num_of_ways(N, broken_floors))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(100000)

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

#variable

#function
@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return rootCount(position-1)+rootCount(position-2)
#class

#main function
def main():
    print(rootCount(N)%1000000007)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np
from math import factorial
from scipy.special import comb
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)
# [floating point \- How to manage division of huge numbers in Python? \- Stack Overflow](https://stackoverflow.com/questions/27946595/how-to-manage-division-of-huge-numbers-in-python)


def get_pattern(num):
    ret = 0

    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            # tmp = factorial(n) // factorial(r) // factorial(n - r)
            tmp = comb(n, r, exact=True)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]

    ret = 1

    # M = 0 以外のとき
    for j in range(M):

        if j == 0:
            # 0マス目からa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern(a[j]-1)
        elif a[j] - a[j-1] == 1:
            # 危険個所が連続していてパターン最後まで移動できるパターンなし
            ret = 0
            break
        else:
            # a[j-1]+1マスからa[j]-1マスまで移動するパターン数
            ret = ret * get_pattern((a[j]-1) - (a[j-1]+1))

        if j == M - 1:
            # a[j]+1マスからNマスへの移動パターン
            ret = ret * get_pattern(N - (a[j] + 1))

    # M = 0　のとき
    if M == 0:
        ret = get_pattern(N)

    print(ret % 1000000007)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(100000)

dp = [-1]*(n+1)
dp[0] = 1
for i in para :
    dp[i] = 0

def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if dp[cnt] != 0 :  
                dp[cnt] = (dp[cnt-1] + dp[cnt-2]) % mod
                cnt += 1
            else :
                cnt += 1
        return dps(cnt,cantvisit)
dps(1,para)
print("{}".format(dp[-1]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000) 

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

for i in a:
    memo[i] = 0

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

print(stair(n))

Submission status: Runtime Error

Solution code:
NM = [int(i) for i in input().split()]
a = [0] * NM[0]
for _ in range(NM[1]):
    a[int(input) - 1] = -1

for i in range(NM[0]):
    if (i == 0):
        if(a[i] != -1):
            a[i] = 1
        else:
            a[i] = 0
    elif(i == 1):
        if(a[i] != -1):
            a[i] = a[i - 1] + 1
        else:
            a[i] = 0
    else:
        if(a[i] != -1):
            a[i] = a[i-1] + a[i - 2]
        else:
            a[i] = 0

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

Submission status: Runtime Error

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

if 0 in A:
    ans[1]=1
elif 1 in A:
    ans[0]=1
else:
    ans[0]=1
    ans[1]=2

for n in range(N):
    if n>1:
        if n+1 in A and n in A:
            print(0)
            break
        elif n+1 in A:
            ans[n]=0
        else:
            ans[n]=ans[n-1]+ans[n-2]
            ans[n] %= 1000000007
else:
    print(ans[N-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
i=0
nn=[]
j=-1

while i!=m:
    a=int(input())
    nn.append(a-j-1)
    if a-j==1:
        if j!=0:
            break
    j=a
    i=i+1
nn.append(n-a)

t=1
if a-j==1:
    t=0
    print(0)
else:
    #print(nn)
    pass
i=0
j=1
ans=1
while i!=len(nn):
    x=nn[i]
    ans_sub=1
    if x==3:
        ans_sub=2
        i=i+1
        ans_sub = int(ans_sub)
        ans = (ans * (ans_sub % 1000000007)) % 1000000007
    else:

        while (x-(1+2*j))>0:
            y=x-(1+(2*j))
            #print(y)
            #print(pow(j+1,y))
            nnt=((pow(j+1,y)-y)/(j+1))+y
            ans_sub=ans_sub+nnt
            j=j+1
            #print(nnt)
        i=i+1
        j=1
        ans_sub=int(ans_sub)
        ans=(ans*(ans_sub%1000000007))%1000000007
if t==1:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.special as scm

def co(a,b):
    ans = 1
    for k in range(min(a-b,b)):
        ans = ans * (a-k) // (k+1)
    return ans

def comb(N):
    if N == 1:
        return 1
    else:
        sum0 = 0
        for i in range(N//2+1):
            sum0 = (sum0+int(scm.comb(N-i, i, exact=True)))%1000000007
        return sum0

def main():
    n, m = map(int, input().split())
    a = [-1]
    for i in range(m):
        a0 = int(input())
        a.append(a0)
    a.append(n+1)
    a = np.array(a)
    a = np.diff(a) -2
    # if a[0] == 0:
    #     a[0] = 1
    # if a[-1] == 0:
    #     a[-1] = 1
    if -1 in a:
        print(0)
        return
    sum1 = 1
    for i in a:
        sum1 = (sum1*comb(i))%1000000007
    print(int(sum1))
    return

main()

Submission status: Runtime Error

Solution code:
def mulmod(x,y,p):
    return x*y % p

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

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

    return _fib(n)

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)

for i in a:
    result = mulmod(fib_memo(i-pos),result,1000000007)
    pos = i+1

result = mulmod(fib_memo(n-pos+1),result,1000000007)

print(result)

Submission status: Runtime Error

Solution code:
d = {}

def step(N,M):
	if N == 0:
		return 1
	if N < 0:
		return 0

	if N-1 in d.keys():
		step_1 = d[N-1]
	else:
		step_1 = step(N-1,M)
		d[N-1] = step_1
	if N-2 in d.keys():
		step_2 = d[N-2]
	else:
		step_2 = step(N-2,M)
		d[N-2] = step_2
		
	if N - 1 in M and N - 2 in M:
		return 0
	if N - 1 in M:
		return step_2
	if N - 2 in M:
		return step_1
	return (step_1 + step_2) % 1000000007


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

print(step(N, a))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
broken_data = [int(input()) for _ in range(M) ]
ans = 0
 
memo = [-1] * (N+1)
def countWays(n):
    if n < 0 or (n in broken_data):
        return 0
    elif n == 0:
        return 1
    else:
        if memo[n] > -1:
            return memo[n]
        else:
            memo[n] = ( countWays(n-1) + countWays(n-2) ) % 1000000007
            return memo[n]
 
print(countWays(N))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

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

Submission status: Runtime Error

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

s=[0]*n
if a[0]==1 and a[1] == 1:
  s[0] = 0
  s[1] = 0
elif a[0] == 1:
  s[0] = 0
  s[1] = 1
elif a[1] == 1:
  s[0] = 1
  s[1] = 0
else:
  s[0] = 1
  s[1] = 2
  
for i in range(2,n):
  #壊れている
  if a[i] == 1:
    s[i] = 0
  else:
    s[i] = s[i-1]+s[i-2]
print(s[n-1]%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.special as scm

def co(a,b):
    ans = 1
    for k in range(min(a-b,b)):
        ans = ans * (a-k) // (k+1)
    return ans

def comb(N):
    if N == 1:
        return 1
    else:
        sum0 = 0
        for i in range(N//2+1):
            sum0 = (sum0+scm.comb(N-i, i, exact=True))%1000000007
        return sum0

def main():
    n, m = map(int, input().split())
    a = [-1]
    for i in range(m):
        a0 = int(input())
        a.append(a0)
    a.append(n+1)
    a = np.array(a)
    a = np.diff(a) -2
    # if a[0] == 0:
    #     a[0] = 1
    # if a[-1] == 0:
    #     a[-1] = 1
    if -1 in a:
        print(0)
        return
    sum1 = 1
    for i in a:
        sum1 = (sum1*comb(i))%1000000007
    print(int(sum1))
    return

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * (num + 1)
    for i in range(num + 1):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern


def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    stepsList[0] = a[0]
    for j in range(1, M):
        stepsList[j] = a[j] - a[j - 1] - 1
        if stepsList[j] == 0:
            return 0
    stepsList[M] = N - a[M - 1]
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k] - 1]
        else:
            total = (total * pattern[stepsList[k] - 1]) % MOD
        # print("#", k, stepsList[k], pattern[stepsList[k] - 1], total)

    return total


ans = solve()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())

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

if M == 0:
    print(fib(N))

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)


new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007


count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)

Submission status: Runtime Error

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

if 1 in A:
    ans[0]=0
    ans[1]=1
else:
    ans[0]=1
    ans[1]=2

for n in range(N):
    if n>1:
        if n+1 in A and n in A:
            print(0)
            break
        elif n+1 in A:
            ans[n]=0
        else:
            ans[n]=ans[n-1]+ans[n-2]
            ans[n] %= 1000000007
else:
    print(ans[N-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * num
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern


def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    stepsList[0] = a[0]
    for j in range(1, M):
        stepsList[j] = a[j] - a[j - 1] - 1
        if stepsList[j] == 0:
            return 0
    stepsList[M] = N - a[M - 1]
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k] - 1]
        else:
            total = (total * pattern[stepsList[k] - 1]) % MOD
        # print("#", k, stepsList[k], pattern[stepsList[k] - 1], total)

    return total


ans = solve()
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.special as scm

def co(a,b):
    ans = 1
    for k in range(min(a-b,b)):
        ans = ans * (a-k) // (k+1)
    return ans

def comb(N):
    if N == 1:
        return 1
    else:
        sum0 = 0
        for i in range(N//2+1):
            sum0 = (sum0+scm.comb(N-i, i))%1000000007
        return sum0

def main():
    n, m = map(int, input().split())
    a = [-1]
    for i in range(m):
        a0 = int(input())
        a.append(a0)
    a.append(n+1)
    a = np.array(a)
    a = np.diff(a) -2
    # if a[0] == 0:
    #     a[0] = 1
    # if a[-1] == 0:
    #     a[-1] = 1
    if -1 in a:
        print(0)
        return
    sum1 = 1
    for i in a:
        sum1 = (sum1*comb(i))%1000000007
    print(int(sum1))
    return

main()

Submission status: Runtime Error

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

s=[0]*n
if a[0] == 1:
  s[0] = 0
  s[1] = 1
elif a[1] == 1:
  s[0] = 1
  s[1] = 0
elif a[0]==1 and a[1] == 1:
  s[0] = 0
  s[1] = 0
else:
  s[0] = 1
  s[1] = 2
  
for i in range(2,n):
  #壊れている
  if a[i] == 1:
    s[i] = 0
  else:
    s[i] = s[i-1]+s[i-2]
print(s[n-1]%1000000007)

Submission status: Runtime Error

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

if 1 in A:
    ans[0]=0
    ans[1]=1
else:
    ans[0]=1
    ans[1]=2

for n in range(N):
    if n>1:
        if n+1 in A and n in A:
            print(0)
            break
        elif n+1 in A:
            ans[n]=0
        else:
            ans[n]=ans[n-1]+ans[n-2]
            ans[n] %= 10**9+7
else:
    print(ans[N-1])

Submission status: Runtime Error

Solution code:
#ABC129C-TypicalStairs.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(100000)

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

#variable

#function
@lru_cache(maxsize=None)
def rootCount(position):
    if position < 0:
        return 0
    elif position == 0:
        return 1
    elif position in A:
        return 0
    else:
        return rootCount(position-1)+rootCount(position-2)
#class

#main function
def main():
    print(rootCount(N)%1000000007)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)N, M = map(int, input().split())

broken = []
for _ in range(M):
  broken.append(int(input()))

mod = 10 ** 9 + 7
f2, f1 = 0, 1
for i in range(1, N + 1):
  if i in broken:
    if i - 1 in broken:
      print(0)
      exit()
    f2 = f1
    f1 = 0
    continue
  f = f2 + f1
  f2 = f1
  f1 = f
print(f % mod)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import factorial

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

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp += factorial(n) / factorial(i) / factorial(n - i)

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()
    else:
        continue

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007

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

count = 1
for item in new_list:
    if not item or len(item) == 1:
        continue
    else:
        count *= (fib(len(item) - 1) % MOD)
        count %= MOD
        #print(count)
print(count)