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 numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

for i in range(m):
    a1=int(input())
    a.append(a1)

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*(n+1)
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        #dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

Submission status: Runtime Error

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

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

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib(diff-1)
    sum %= 1000000007
    a_p = a

if (N - a_p == 1):
    print('0')
    exit()

sum *= fib(N - a_p)

print(sum % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

loop(N)
print(dp[N])

Submission status: Runtime Error

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

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]

for i in range(m+1):
    if a[i+1] - a[i] < 2:
        if a[i+1] == 1 or a[i+1] == n: pass
        else :
            ans = 0
            break
    else :
        ans *= fib(a[i+1]-(a[i]+1))

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = list(map(int, input().split()))
s = [0 for i in range(n+1)]
t = [-1 for i in range(n+1)]
for i in range(m):
    x = int(input())
    s[x] = 1

def dx(r):
    global t
    if t[r]>=0:
        return t[r]
    x=0
    y=0
    #print(i)
    if s[r+1]==0 and r==n-2:
        return 2
    if s[r+1]==1 and r==n-2:
        return 1
    if r==n-1:
        return 1
    if r==n:
        return 0
    if s[r+1] == 0:
        x=dx(r+1)
    if s[r+2] == 0:
        y=dx(r+2)
    #print([i,x,y])
    t[r]=(x+y)%1000000007
    return (x+y)%1000000007

ans=dx(0)

print(ans)

Submission status: Runtime Error

Solution code:
def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

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

time_f=[]

for i,v in enumerate(a):
    if i == 0:
        print (fib(a[i]))
        time_f = fib(a[i])
    else:
        # print((a[i]-a[i-1]-1))
        print (fib(a[i]-a[i-1]-1))
        time_f *=fib(a[i]-a[i-1]-1)


print(time_f%1000000007)

Submission status: Runtime Error

Solution code:
def kaidan(i):
    global ans
    if ls.count(i+1)==0:
        if i+1==n:
            ans+=1
        else:
            kaidan(i+1)
    if ls.count(i+2)==0:
        if i+2==n:
            ans+=1
        elif i+2<n:
            kaidan(i+2)

k=0
ls=[]
ans=0

n,m=map(int,input().split())
for j in range(m):
    a=int(input())
    ls.append(a)

kaidan(0)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
cache = {1: int(1), 2: int(2)}


def calc(_n):
    if _n in cache:
        return cache[_n]
    else:
        x = int(calc(_n - 1) + calc(_n - 2))
        cache[_n] = x
        return x


N, M = map(int, raw_input().split())
prev_a = int(-1)
ans = int(1)
for i in range(0, M):
    a = int(input())
    if a == 1:
        prev_a = 1
    elif prev_a + 1 == a:
        ans = 0
        break
    else:
        ans = ans * calc(a - prev_a - 2)
        prev_a = a

if ans == 0:
    print(ans)
else:
    if prev_a + 1 == N:
        ans = ans
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
md = 1000000007
dp=[]
def countways(n,broken,ix):
	global dp,md
	if(dp[ix]!=-1):
		return dp[ix]

	ways = 0
	if(ix+1<=n and broken[ix+1]==0):
		ways+=countways(n,broken,ix+1)
	if(ix+2<=n and broken[ix+2]==0):
		ways+=countways(n,broken,ix+2)
	dp[ix]=(ways%md)
	return dp[ix]

n,m = list(map(int,raw_input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(raw_input())]=1
print(countways(n,broken,0)%md)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
lst=[]
lst.append(a[0])
lst.append(0)
for j in range(m-1):
  lst.append(a[j+1]-a[j]-1)
  lst.append(0)
lst.append(n-a[m-1])
l=len(lst)
for k in range(l-1):
  if lst[k]==0 and lst[k+1]==0:
    print(0)
    break
  else:
    if lst[k]>1:
      lst[k]-=1
if lst[l-1]>1:
  lst[l-1]-=1
for p in range(l):
  if lst[p]==0:
    del lst[p]
totl=1
for q in range(len(lst)):
  totl*=lst[q]
  totl=totl%1000000007
print(totl)

Submission status: Runtime Error

Solution code:
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)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
s =[0]*(b+1)
flag = 0
p = [0]*b
goukei = 0
for i in range(b):
  p[i] = int(input())
for k in range(1,b):
  if (p[k] - p[k-1]-1) == 0:
    flag = 1
for l in range(b+1):
  if l == 0:
    s[l] = p[l] -1
  elif l == b:
    s[l] = a - p[l-1]
  else:
    s[l] = p[l] - p[l-1]-1
counter = 0
def fib(n):
    memo = [0] * n
    memo[0:2] = [0, 1]
    for i in range(2, n):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n-1]
if flag == 0:
  for f in range(len(s)):
    goukei += fib(s[f]+2)
  print(goukei%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
def dfs(i):
    global kaidan
#    print(i, kaidan)
    if(kaidan[i] == -1): return 0
    if(kaidan[i] > 0):
        return kaidan[i]
    if(i == N):
        kaidan[i] = 1
        return kaidan[i]
    if(i > N): return 0
    kaidan[i] += dfs(i+1)
    kaidan[i] += dfs(i+2)
    return kaidan[i]

N, M = map(int, input().split())
kaidan = [0 for i in range(N+2)]
#print(kaidan)

for i in range(M):
    idx = int(input())
    kaidan[idx] = -1

dfs(0)
print(kaidan[0] % 1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
from math import factorial as fac

N,M=  map(int, input().split())
broken_steps=[]

for m in range(M):
    broken_steps.append(int(input()))

for i in range(len(broken_steps)-1):
    if broken_steps[i+1]-broken_steps[i]==1:
        print("{}".format(0))
        FLG=True

if FLG!=True:        
    count=0
    for two_step in range(M,N//2+1):
        one_step=N-two_step*2
        count+=fac(two_step+one_step)/(fac(two_step)*fac(one_step))

    print("{}".format(count%1000000007))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

loop(N)
print(dp)

Submission status: Runtime Error

Solution code:
N_M = [int(e) for e in input().split()]
div = 1000000007
a=[]
flag=1
for i in range(N_M[1]):
  a.append(int(input()))
  if(i>=1 and a[i]==a[i-1]+1):
    print(0)
    flag=0

def num(stair):
  number=0
  if(stair==0):
    return 1
  elif(stair==1):
    return 1
  elif(stair==2):
    return 2
  elif(stair>2):
    number += num(stair-1)
    number += num(stair-2)
  return number

if(flag==1):
  stair = []
  for i in range(N_M[0]+1):
    stair.append(i)
  stairs = [[]]
  start=0
  for i in range(len(a)+1):
    if(i==len(a)):
      stairs.append(stair[start:N_M[0]+1])
      break
    stairs.append(stair[start:a[i]])
    start=a[i]+1
  stairs = [x for x in stairs if x]
  answers = []
  for i in range(len(stairs)):
    answers.append(num(len(stairs[i])-1))

  answer=1
  for i in range(len(answers)):
    answer *= answers[i]
  print(answer%div)

Submission status: Runtime Error

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

# フィボナッチ数列の関数
def fibonacci(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b

# 段の切れ目ごとの場合の数を算出
R = len(a) - 1
for i in range(R):
    x = a[i + 1] - a[i] -1
    pattern.append(fibonacci(x))

# 段の切れ目ごとの場合の数の積
for i in range(len(pattern)):
    ans = ans * pattern[i] % 1000000007

# 1段目まで、最終弾までの数
s1 = fibonacci(a[0])
s2 = fibonacci(N - a[-1])

# かける
ans = ans * s1 * s2 % 1000000007

# 2弾続けて壊れている場合はNG
for i in range(M - 1):
    if a[i] + 1 == a[i + 1]:
        ans = 0

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Runtime Error

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


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


cnt = [fib(i) for i in range(1, n)]
if m == 0:
    print(cnt[n])
    exit()

l = [int(input()) for _ in range(m)]
l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Runtime Error

Solution code:



N, M = map(int, input().split())
# 壊れている床番号
a = []
for _ in range(M):
    a.append(int(input()))
# ルートの総数
root = 0
# 今いる階段の段数
now = 0


def isSafe(now):
    """
    1, 2段先共になければ0
    1段先だけあれば1
    2段先だけあれば2
    1, 2段先共にあれば3
    """
    now_1 = not (now-1) in a
    now_2 = not (now-2) in a    
    return now_1 + now_2*2

def step(N):
    # N段を登る移動方法数
    if N <= 1 and (1 in a):
        return 1
    if N==2:
        if 2 in a:
            return step(1)
        return 2
    if isSafe(N)==1:
        return step(N-1)
    elif isSafe(N)==2:
        return step(N-2)
    elif isSafe(N)==3:
        return step(N-1)+step(N-2)
    else:
        return 0


print(step(N))

Submission status: Runtime Error

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

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


def dfs(step):
    if dp[step] >= 0:
        return dp[step]
    if step - 1 in a and step - 2 in a:
        return 0
    cnt = 0
    if step <= 0:
        return 1
    if step - 1 >= 0 and step - 1 not in a:
        cnt = (cnt + dfs(step - 1)) % mod
    if step - 2 >= 0 and step - 2 not in a:
        cnt = (cnt + dfs(step - 2)) % mod
    dp[step] = cnt
    return dp[step]


print(dfs(n))

Submission status: Runtime Error

Solution code:
from math import factorial
N,M=map(int,input().split())
list1=[]
ANS=0
A=int(input())
DAN=A
B=DAN-DAN//2
for k in range(B):
  a = factorial(B) / factorial(k) / factorial(B - k)
  ANS+=a
for i in range(1,M):
  A=int(input())
  list1+=[A]
  DAN=A-list1[i-1]-1
  B=DAN-DAN//2
  if A==list1[i-1] or A==list1[i-1]+1:
    print(0)
    break  
  for k in range(B):
    a = factorial(B) / factorial(k) / factorial(B - k)
    ANS+=a
DAN=N-A-1
B=DAN-DAN//2
for t in range(B):
  a = factorial(B) / factorial(t) / factorial(B - t)
  ANS+=a
print(int(ANS)%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np


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

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

sq = []
for k in range(M+1):
    if k == 0:
        sq.append(a[k])
    
    elif k == M:
        sq.append(N-a[k-1])

    elif a[k] == a[k-1] +1:
        sq.append(0)
    
    else:
        sq.append(a[k] - a[k-1]-1)

ans = 1
for p in sq:
    if p == 0:
        print(0)
        break

    else:
        q = int((1/np.sqrt(5))*  ( (((1+np.sqrt(5))/2)**p) -  (((1-np.sqrt(5))/2)**p)  ))%1000000007
        ans *= q
        

if p!=0:
    print(int(ans)%(1000000007))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = []
for i in range(M):
    As.append(int(input()))
    
Ds = []
for i in range(M):
    if i==0:
        Ds.append(As[0])
    else:
        Ds.append(As[i]-As[i-1])
Ds.append(N-As[-1])

def fibo(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    S = [1, 2]
    for i in range(2, n):
        S.append(S[-2]+S[-1])
    return S[-1]

Fs = [fibo(n) for n in Ds]

pattern = 1
for f in Fs:
    pattern *= f

print(f % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
pat = [0] * (N+1)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = []
    if len(A) > 1:
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

Submission status: Runtime Error

Solution code:
def up_stairs(now):
  
  if now == N or (now + 1) == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0

    return up_stairs(now + 1) + up_stairs(now + 2)


N,M = (int(x) for x in input().split())

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

print(int(up_stairs(0) % 1000000007))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % 1000000007)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
mod = 10 ** 9 + 7

B = ['.'] * (N + 1) 
for a in A:
    B[a] = '#'
    
dp = [0] * (N + 1)
if B[1] == '.' and B[2] == '.':
    dp[1] = 1
    dp[2] = 2
elif B[1] == '#' and B[2] == '.':
    dp[2] = 1
elif B[1] == '.' and B[2] == '#':
    dp[1] = 1
    
for i in range(3, N + 1):
    if B[i] == '.':
        dp[i] = (dp[i - 2] + dp[i - 1]) % mod
    
print(dp[N])

Submission status: Runtime Error

Solution code:
def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
        
        
        
        
n, m = [int(i) for i in input().split()]
a = [int(input()) for i in range(m)]
MOD = 1000000007

#出来ない判定
for i in range(m-1):
    if (a[i+1] - a[i]) == 1:
        print(0)
        exit()

#壊れてる床前後で組み合わせ

allnum = 1
i = 0
for b in range(m):
    #print(b, i, allnum)
    buf= Fib(a[b]-1 - i + 2)
    allnum *= buf
    i = a[b]+1
    #print(b, i, allnum)

buf = Fib(n - i + 2)
# print(n, i, buf)

allnum *= buf

print(allnum%MOD)

Submission status: Runtime Error

Solution code:
#coding: utf-8
def factorial(n):
	output = 1
	for i in range(1,n+1):
		output = output*i
	return output

def diff(w, sign, N):
	diff = 0
	for i in range(N):
		diff = diff + w[i]*sign[i]
	return abs(diff)

def target(sign, cnt, N, factwo):
	num = cnt
	for i in reversed(range(N)):
		temp = num - factwo[i]
		if(temp >= 0):
			sign[i] = 1
		else:
			sign[i] = -1
		num = temp

N = int(input())
line = input()
w = []
sign = []
factwo = []
for i in range(N):
	factwo.append(2**i)

for i in range(N):
	w.append(int(line.split()[i]))
	sign.append(1)

cnt = 0
temp = diff(w, sign, N)

while(cnt<factorial(N)):
	target(sign, cnt, N, factwo)
	x = diff(w, sign, N)
	if(temp > x):
		temp = x
	cnt = cnt + 1
	if(diff == 0):
		break

print(temp)

Submission status: Runtime Error

Solution code:
CONST = 1000000007
n, m = map(int, input().split())
a_list = [int(input()) for _ in range(m)]
index = 1
prev_p, p = 1, 1
while index < n:
    if index == 1:
        if index in a_list:
            p = 0
        pass
    elif index in a_list:
        prev_p = p
        p = 0
        if index + 1 in a_list:
            pp = 0
            break
    else:
        prev_p = p
        p = (p + pp) % CONST
    pp = prev_p
    index += 1

print((pp + p) % CONST)

Submission status: Runtime Error

Solution code:
from scipy.special import comb


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += comb(num_step-j, j, exact=True)
    return pats


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)

Submission status: Runtime Error

Solution code:
n,m  = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
    
fib = [0,1,1,2]
for i in range(n-m):
    x = fib[i+3] + fib[i+2]
    fib.append(x)

a2 = [a[0],n-sum(a[-1:])]
for i in range(m-1):
    a2.append(a[i+1]-a[i]-1)
a3 = []
for i in range(len(a2)):
    a3.append(fib[a2[i]])
#ans = 1
import functools
import operator
ans = functools.reduce(operator.mul, a3)
#for i in range(len(a3)):
#    ans = ans * a3[i]
ans = ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from functools import lru_cache
import sys


@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


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

    S = [0]
    for i in range(0, M):
        S.append(a[i] - S[-1])
    S.append(N - a[-1])

    res = 1
    for i in S:
        if i >= 3:
            res *= fib(i) % 1000000007
    print(res % 1000000007)

Submission status: Runtime Error

Solution code:
def up_stairs(now):
  
  if now == N or (now + 1) == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  if (now + 1) in a:
    return up_stairs(now + 2)
  elif (now + 2) in a:
    return up_stairs(now + 1)
  else:
    return up_stairs(now + 1) + up_stairs(now + 2)


N,M = (int(x) for x in input().split())

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

print(int(up_stairs(0) % 1000000007))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
    
l = [int(input()) for _ in range(m)]
l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


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


cnt = [fib(i) for i in range(1, n)]
if m == 0:
    print(cnt[n])
    exit()

total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Runtime Error

Solution code:
mod = 1000000007

import numpy

def fib_matr(n):
    return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0]

# for i in range(20):
#     print(int(fib_matr(i)), end=" ")


def calculate(n, b):
    diff = [b[i+1] - b[i] - 1 for i in range(len(b)-1)]
    diff.insert(0, b[0])
    diff.append(n - b[-1])
    sum = 1
    for d in diff:
        if d == 0:
            return 0
        sum *= fib_matr(d)%mod
        sum = sum%mod
    return sum


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

print(calculate(n, b))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

a = [int(input()) for i in range(m)]
a.append(n+1)

ar = list(range(n+1))

tmp = 0
ans = 1
counter = 0

# def fib1(n):
#     global counter
#     counter += 1
#     if n in [0, 1]:
#         return 1
#     return fib1(n - 1) + fib1(n - 2)
from functools import lru_cache
counter = 0
@lru_cache(maxsize=1024)
def fib1(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib1(n - 1) + fib1(n - 2)

for i in range(len(a)):
    cnt = len(ar[tmp:a[i]])
    ans = (ans*(fib1(cnt-1)%1000000007))%1000000007
    if i+1 < len(a):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
    tmp = a[i]+1

print(ans)

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
    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:
n,m = list(map(int, input().split()))
s = [0 for i in range(n+1)]
t = [-1 for i in range(n+1)]
for i in range(m):
    x = int(input())
    s[x] = 1

def dx(r):
    global t
    if t[r]>=0:
        return t[r]
    x=0
    y=0
    #print(i)
    if r==n-2:
        return 2
    if r==n-1:
        return 1
    if r==n:
        return 0
    if s[r+1] == 0:
        x=dx(r+1)
    if s[r+2] == 0:
        y=dx(r+2)
    #print([i,x,y])
    t[r]=(x+y)%1000000007
    return (x+y)%1000000007

ans=dx(0)

print(ans)

Submission status: Runtime Error

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

def factorial(x):
  if x == 0:
    return 1
  else:
    return x * factorial(x-1)

def C(x,y):
    return factorial(x)//(factorial(x-y)*factorial(y))

def f(x):
    if x == 0:
        return 1
    else:
        ret = 0
        for i in range(x//2+1):
            ret += C(x-i,i)
        return ret

b = []
for i in range(m+1):
    b.append(a[i+1]-a[i]-2)

ans = 1
if -1 in b:
    print(0)
else:
    for j in b:
        ans *= (f(j)%1000000007)
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum)

Submission status: Runtime Error

Solution code:
import math

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

a = [-1] * (M+2)

for i in range(1,M+1) :
    a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            step2 = math.factorial(j)
            step1 = math.factorial(length-2*j)
            count += math.factorial(length - j) / step1 / step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

Submission status: Runtime Error

Solution code:
def up_stairs(now):
  
  if now == N or (now + 1) == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  if (now + 1) in a:
    return up_stairs(now + 2)
  elif (now + 2) in a:
    return up_stairs(now + 1)
  else:
    return up_stairs(now + 1) + up_stairs(now + 2)


N,M = (int(x) for x in input().split())

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

print(int(up_stairs(N, a, 0) % 1000000007))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
if m == 0:
    x = a[m+1]-a[i]-1
    ans = int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007
else:
  for i in range(m):
  	a[i+1] = int(input())
  for i in range(m+1):
    if a[i]+1 == a[i+1] and i != 0 and i != m:
      ans = 0
      break
    else:
      x = a[i+1]-a[i]-1
      ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 1000000007

last_ana = int(input())
blocks = [last_ana]

for _ in range(1, m):
    ana = int(input())
    blocks.append(ana - last_ana - 1)
    last_ana = ana

blocks.append(n - last_ana)

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)

    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % 1000000007)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
broken_lst = []
for _ in range(M):
    broken_lst.append(int(input()))

counter_arr = [0]*(N+1)

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

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

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

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

print(counter_arr[-1])

Submission status: Runtime Error

Solution code:
import math

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

result = 0

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

if M == 0:
    for i in range(math.floor((N-1)/2) + 1):
        result += cmb(N - List[M-1]-1-i,i) 
    result = result % 1000000007 
    print(result)

else:
    List = [int(input()) for i in range(M)]
    
    for i in range(math.floor((List[0]-1)/2) + 1):
        result += cmb(List[0]-1-i,i) 
            
    for i in range(M-1):
        if List[i+1] - List[i] == 1:
            result = 0
            break
        else:
            tmp = 0
            for j in range(math.floor((List[i+1]-List[i]-2)/2) + 1):
                tmp += cmb(List[i+1]-List[i]-2-j,j)
            result = result * tmp

    tmp = 0
    for i in range(math.floor((N - List[M-1]-1)/2) + 1):
        tmp += cmb(N - List[M-1]-1-i,i) 

    result = result * tmp
    result = result % 1000000007 
    print(result)