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 fib(n):
	if n<0:
		return 0
	if n in [0, 1]:
		return 1
	return fib(n-1) + fib(n-2)

N, M = map(int, input().split())
if M==0:
	ans = fib(N)
else:
	A = [int(input()) for _ in range(M)]
	A.append(N+1)
	ans = fib(A[0]-1)
	for i in range(M):
		ans = ans * fib(A[i+1]-A[i]-2)

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  global N
  b = bisect.bisect_left(a,x)
  return True if x==a[min(b,N)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Runtime Error

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

ans = int(1)

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

SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]
    SA[i+2] = SA[i+2]%1000000007

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
a = []
ans = 1
start = 1

def fib(x):
    f = (((1 + np.sqrt(5)) / 2)**x - ((1 - np.sqrt(5)) / 2)**x ) / np.sqrt(5)
    return f

for i in range(m):
    a.append(int(input()))
    a.append(n)
print(a)

for j in range(m+1):
    y = a[j] - start + 1
    start = a[j] + 1
    ans = ans * int(fib(y))
    print(y)
    print(fib(y))
    print(ans)

print(ans)

Submission status: Runtime Error

Solution code:
def fibo(x):
    if x>0:
        ll=[0]*x
        ll[0]=1
        if x>1:
            ll[1]=2
            if x>2:
                for y in range(x-2):
                    ll[y+2]=ll[y+1]+ll[y]
        return(ll[x-1])

    else:
        return(0)

N,M=(int(x) for x in input().split())
a=[]
for x in range(M):
    aa=int(input())
    a.append(aa)
ans=[0]*(M+1)
sa=a[0]-1
if M==0:
    print(fibo(N))
else:
    if sa>0:
        ans[0]=fibo(sa)
    else:
        ans[0]=1
    for x in range(M-1):
        sa=a[x+1]-a[x]-1
        if sa>0:
            ans[x+1]=fibo(sa-1)
        else:
            ans[x+1]=0
            break

    saa=N-a[M-1]-1
    ans[M]=fibo(saa)

    kotae=ans[0]%1000000007
    for x in range(M):
        kotae=kotae*int(ans[x+1])%1000000007
    print(kotae%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

if flag >= 1:
    print(0)

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

    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  b = bisect.bisect_right(a,x)
  return True if x==a[max(0,b-1)] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Runtime Error

Solution code:
import sys

def fib(x):
    if x > 1:
        return fib(x-1) + fib(x-2)
    else:
        return 1

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

for k in range(1,M):
    if a[k] - a[k-1] == 1:
        print(0)
        sys.exit()

count = 1
if M > 0:
    stairs = a[0] - 1
    c = fib(stairs) #組み合わせ
    count = count*c

    if M > 1:
        for i in range(1,M):
            stairs = a[i] - a[i-1] - 1
            c = fib(stairs)#組み合わせ
            count = count*c

    stairs = N - a[M-1] - 1
    c = fib(stairs)
    count = count*c

else:
    c = fib(N)
    count = count*c

d = count%1000000007
print(d)

Submission status: Runtime Error

Solution code:
import math

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

for i in range(M+1):
    dist=a[i+1]-a[i]-2
    if dist<0 and a[i]!=-1 and a[i+1]!=N+1:
        ans=0
        break
    
    val=0
    cnt1=dist%2
    cnt2=dist//2
    while cnt2 >= 0:
        val+=math.factorial(cnt1+cnt2)/math.factorial(cnt1)/math.factorial(cnt2)
        cnt2-=1
        cnt1+=2
    ans*=val

    while ans>1000000007:
        ans-=1000000007

print(int(ans))

Submission status: Runtime Error

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    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

fact = [0] * (M+2)

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) :
            if fact[j] != 0 :
                step2 = fact[j]
            else :
                step2 = math.factorial(j)
                fact[j] = step2
            if fact[length-2*j] != 0 :
                step1 = fact[length-2*j]
            else :
                step1 = math.factorial(length-2*j)
                fact[length-2*j] = step1
            if fact[length - j] != 0 :
                step3 = fact[length-j]
            else :
                step3 = math.factorial(length - j)
                fact[length - j] = step3
            count += step3 // step1 // step2
        ans *= count

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

Submission status: Runtime Error

Solution code:
def fibo(x):
    if x>0:
        ll=[0]*x
        ll[0]=1
        if x>1:
            ll[1]=2
            if x>2:
                for y in range(x-2):
                    ll[y+2]=ll[y+1]+ll[y]
        return(ll[x-1])

    else:
        return(0)

N,M=(int(x) for x in input().split())
a=[]
for x in range(M):
    aa=int(input())
    a.append(aa)
ans=[0]*(M+1)
sa=a[0]-1
if m==0:
    print(fibo(N))
else:
    if sa>0:
        ans[0]=fibo(sa)
    else:
        ans[0]=1
    for x in range(M-1):
        sa=a[x+1]-a[x]-1
        if sa>0:
            ans[x+1]=fibo(sa-1)
        else:
            ans[x+1]=0
            break

    saa=N-a[M-1]-1
    ans[M]=fibo(saa)

    kotae=ans[0]%1000000007
    for x in range(M):
        kotae=kotae*int(ans[x+1])%1000000007
    print(kotae%1000000007)

Submission status: Runtime Error

Solution code:
def func(i):
  global num
  if min([abs(j-i) for j in a]) == 0:
    return 0
  if i == n:
    num += 1
    return 0
  elif i == n+1:
    return 0
  func(i+1)
  func(i+2)

n, m = map(int, input().split())
a = [0 for i in range(m)]
for i in range(m):
  a[i] = int(input())
print(n, m)
print(a)
num = 0
func(0)
num = num % 1000000007
print(num)

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):
  if i == 0:
    p[i] = int(input())
  else:
    p[i] = int(input())
    if (p[i] -p[i-1]) ==1:
      flag = 1
      break
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)):
    if not s[f] == 0:
      goukei += goukei*fib(s[f]+2)
  print(goukei%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

for i in range(len(a_null)-1):
    if a_null[i] + 1 == a_null[i+1]:
        print(0)
        sys.exit()
a = np.zeros(N+1)
for i in a_null:
    a[a_null] = 1

zero_index = np.where(a == 0)[0]
zero_renban = []
zero = 0
for i in range(len(zero_index)-1):
    if zero_index[i] + 1 == zero_index[i+1]:
        zero += 1
        if i +1 == len(zero_index)-1:
            zero_renban.append(zero+1)
    else:
        zero_renban.append(zero+1)
        zero = 0

memo = np.zeros(10**6)
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]

ans = 1
for i in zero_renban:
    ans *= int(fib(i))

print(int(ans%1000000007))

Submission status: Runtime Error

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

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

for i in range(3, n+1):
    pattern[i]=2*pattern[i-2]+pattern[i-3]

judge=False
for i in range(m-1):
    if a[i+1]-a[i]==1:
        judge=True
ans=1
med=0
num=1

if judge:
    print("0")
else:
    for i in range(n):
        if i+1 in a:
            num=0
            ans*=med
    
        else:
            med=pattern[num]
            num+=1


ans*=med

print(ans)

Submission status: Runtime Error

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

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    a_list = a_list.pop(0)
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            a_list = a_list.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now
        if i+1 in a_list:
            a_list = a_list.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

Submission status: Runtime Error

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

# N : 階段の段数, M : 壊れている段の数
N, M = map(int, input().split())
a = []
for n in range(M):
    a.append(int(input()))

ccs = {}


def culcContinueSitu(n):
    # n段連続で使える階段がある場合の登り方を数える
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n >= 3:
        if n in ccs:
            return ccs[n]
        # 最初の1段目で飛ばすとき：culcContinueSitu(n-2)を数えれば良い
        # 最初の1段目で飛ばさないとき：culcContinueSitu(n-1)を数えれば良い
        ans = culcContinueSitu(n-2) + culcContinueSitu(n-1)
        ccs[n] = ans
        return ans


if M > 0:
    num_case = 1
    start = 0
    end = N
    for i in range(M):
        if i >= 1 and a[i]-a[i-1] <= 1:
            num_case = 0
            break
        if i >= 1:
            start = a[i-1] + 1
        end = a[i] - 1
        if end == 0:
            continue
        num_case *= culcContinueSitu(end - start)
    if N - a[M-1] > 1 and num_case != 0:
        start = a[M-1] + 1
        end = N
        num_case *= culcContinueSitu(end - start)
else:
    num_case = culcContinueSitu(N)

print(num_case % 1000000007)

Submission status: Runtime Error

Solution code:
zimport sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		sys.exit()
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		sys.exit()
	for k in range(2,N):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if a == N - 1:
		print(ans%1000000007)
	else:
		print(ans%1000000007)
main()

Submission status: Runtime Error

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    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

fact = [0] * (M)

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) :
            if fact[j] != 0 :
                step2 = fact[j]
            else :
                step2 = math.factorial(j)
                fact[j] = step2
            if fact[length-2*j] != 0 :
                step1 = fact[length-2*j]
            else :
                step1 = math.factorial(length-2*j)
                fact[length-2*j] = step1
            if fact[length - j] != 0 :
                step3 = fact[length-j]
            else :
                step3 = math.factorial(length - j)
                fact[length - j] = step3
            count += step3 // step1 // step2
        ans *= count

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from math import factorial


N, M = map(int, input().split())
a=[]
for i in range(M):
    tmp = int(input())
    if 0 < i:
        if a[-1]+1 == tmp:
            print(0)
            exit()
    a.append(tmp)
p = 0
a.append(N)
cnt = 0
data = {}
for sep in a:
    ls = list(range(p, sep))
    p = sep + 1
    l = len(ls) - 1
    print(l, ls)
    tmp = 0
    for i in range(l // 2 + 1):
        two = i
        one = l - i*2
        tmp += factorial(l) / (factorial(two) * factorial(one))
    cnt += tmp
    print('cnt:', cnt)
    
print(int(cnt % 1000000007))

Submission status: Runtime Error

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

def t(current, n):
    if current == n:
        return 1
    if current in a:
        return 0
    p1, p2 = 0, 0
    if current + 1 not in a:
        p1 = t(current + 1, n)
    if current + 2 <= n and current + 2 not in a:
        p2 = t(current + 2, n)
    return p1 + p2

result = 1
a.append(n - 1)
for index in range(len(a)):
    if index == 0:
        a1 = 0
    else:
        a1 = a[index - 1] + 1
    a2 = a[index] + 1
    p_step1 = t(a1 + 1,  a2)
    p_step2 = t(a1 + 2,  a2)
    result = (result * (p_step1 + p_step2)) % 1000000007
 
print(result)

Submission status: Runtime Error

Solution code:

import sys
from functools import lru_cache
sys.setrecursionlimit(12000)

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.append(n+1)
prv=0
ans=1
for ai in a:
  if(ai==prv):
    ans=0
    break
  ans*=fib(ai-1-prv)
  while(ans>10**9+7):
    ans%=10**9+7

  prv=ai+1

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
b=0
c=0
d=1
e=0
for i in range(m):
    a.append(int(input()))
for j in range(m-1):
    if(a[j]+1==a[j+1]):
        print('0')
        break    
z=list(set(a))
z=sorted(z)
z.append(0)     
for i in range(n):
    if(z[b]==i+1):
        b+=1    
        continue    
    else:
        c=d+e
        e=d
        d=c
print({0}.format(c%100000007)

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

def combination(n,r,n_b):

    nCr = n_b // factorial(r) // factorial(n - r)
    return(nCr)

n, m = [int(i) for i in input().split()]
a = [-1]
for i in range(m):
    a.append(int(input()))
    if a[-1] - a[-2] == 1:
        print(0)
        sys.exit()
a.append(n+1)
# print(a)

ans = 1
for i in range(len(a)-1):
    # print('i',i,ans)
    a_begin = a[i]
    a_end = a[i+1]
    # print(a_begin,a_end)
    num_stair = a_end - a_begin - 2
    max_num_two_up = num_stair // 2
    # print(num_stair,max_num_two_up)
    ans_tmp = 0
    n_b = factorial(num_stair-j)
    for j in range(max_num_two_up+1):
        ans_tmp += combination(num_stair-j,j,n_b)
    ans *= ans_tmp

ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP
from sys import setrecursionlimit(1000000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


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

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

Submission status: Runtime Error

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

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    a_list = alist.pop(0)
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            a_list = alist.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now
        if i+1 in a_list:
            a_list = alist.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

Submission status: Runtime Error

Solution code:
import math
def f(k):
    aaa = 1/math.sqrt(5)*(((1+math.sqrt(5))/2)**k-((1-math.sqrt(5))/2)**k)%1000000007
    return aaa
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(f(n-1))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(n-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        for w in newlist:
            ans = 1
            ans = ans*f(w-1)%1000000007      
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect
def f(x,a):
  b = bisect.bisect_left(a,x)
  return True if x==a[b] else False
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Runtime Error

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


for i in range(1,m):
    if array[i]-array[i-1] == 1:
        print(0)
        sys.exit()
sequence = [1,1]
for i in range(10**5 ):
    sequence.append(sequence[i+1]+sequence[i])


count = sequence[array[0]]
for i in range(1,m):
    count *= sequence[array[i]-array[i-1]]

count *= sequence[n- array[m-1]]

print(count%1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  9 21:02:21 2019

@author: hisaki
"""


import numpy as np

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
    
def func( x , y ):
    bet = y -x
    two_num = int(bet/2)
    s  = 0
    for i in range(two_num):#2の個数分ループ        
        s += cmb(bet-i,i)
        
    return s


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

a = np.zeros(N,dtype = 'int64')

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

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

s = np.ones(M)

for i in range(M):
    if i+1==M:#最後の計算
        s[i] = func(a[i]+1,N-1)
    
    else:
        s[i] = func(a[i]+1,a[i+1]-1)


s_multi = 1
for i in s:
    i = int(i)
    s_multi *= s[i]

print (int(s_multi))
#print(s_multi%1000000007)

Submission status: Runtime Error

Solution code:
def kaidan(n):
    steps = [0] * (n+1)
 
    steps[1] = 1
    steps[2] = 2
    steps[3] = 3
    for i in range(4, n+1):
        steps[i] = steps[i-1] + steps[i-2] + steps[i-3]
 
    return steps[n]
  
 
a = input()
a = a.split(" ")
N = int(a[0])
M = int(a[1])
 
cns = []
 
d_list = []
for i in range(M):
    d_list.append(int((input())))
    
# print(d_list)
ddd = kaidan(N)
for i  in(d_list):
    an = kaidan(i)
    bn  = kaidan(N+1-i)
    cn = an* bn -2
    cns.append(cn)
    
answer = ddd - sum(cns)
print(answer%1000000007)

Submission status: Runtime Error

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

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1

if A[0]==1:
    j=1
    flag=True
else:
    j=0
    flag=False
for x in range(2, N + 1):
    if x==A[j]:
        case[x] = 0
        j=(j+1)%M
        flag=True
    elif flag==True:
        case[x] = case[x - 2]
        flag=False
    else:
        case[x] = (case[x - 1] + case[x - 2]) % 1000000007
        flag=False

print(case[N])

Submission status: Runtime Error

Solution code:
import math
import functools
import operator
N,M= list(map(int,input().split()))
a = []
for i in range(M):
    an = int(input())
    a.append(an)
#print("a=",a)

#実質的に歩く階段の数
toS=N-M
check = 0
#連番の場合存在しない
for i in range(1,M-1):
    if a[i] == a[i-1]+1 or a[M-1] == N:
        check = 1
#        print(0)

#間の階段の数
dela = [a[0]]
for i in range(1,M):
#    print("i=",i)
    delan = a[i]-a[i-1]
    dela.append(delan)

dela.append(N-a[M-1])
#("dela=",dela)


number = 0
#2の個数を選ぶ(dela[i]=4なら(1,1,2),(1,2,1),(2,1,1),(2,2)の組み合わせ
kumiawase = []
for i in range(len(dela)):
    if dela[i] >=3:
        for j in range(dela[i]//2):
            twonum = j+1 #2の個数
            rownum= dela[i]- twonum
#            print("twonum,rownum,j=",twonum,rownum,j,dela[i])
            number = number + (math.factorial(rownum))/(math.factorial(twonum))
        kumiawase.append(int(number))
        number = 0
#    print("i,delalen=",i,len(dela))
#print("kumiawase=",kumiawase)
result = 1
for i in range(len(kumiawase)):
    result =result*kumiawase[i]
if check ==0:
    print(result%1000000007)

Submission status: Runtime Error

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

list_Stairs = []

for i in range(M):
    list_Am.append(int(input()))
# print(str(list_Am))

## Anにはスタート合わせて何段あるかが入る
for j,An in enumerate(list_Am):
    if j == 0:
        list_Stairs.append(An)
    else:
        list_Stairs.append(An-list_Am[j-1]-1)
list_Stairs.append(N-list_Am[-1])
        
# print(str(list_Stairs))

## スタートを0としてn段目までか（スタート合わせてn+1段ある）
def endFib(n, a1 = 1, a2 = 1):
    if (n < 2): 
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)% 1000000007

result = 1
if 0 in list_Stairs:
    result = 0
else:
    for Stair in list_Stairs:
        # print("段数："+str(Stair))
        # print(str(endFib(Stair-1)))
        result = result * endFib(Stair-1)
        result = result % 1000000007

print(str(result))

"""
if __name__ == "__main__":
    for i in range(10):
        print(str(endFib(i)))
"""

Submission status: Runtime Error

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

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

wa = (10**9) + 7

def Fib(n):
    if n==0:
        return 0 #F0
    elif n==1:
        return 1 #F1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 0 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo





ans = 1



if M!= 1:
    length = a[0]
    ans *= Fib(length+1)

    for i in range(0,M-1):
        length = a[i+1]-a[i]-1
        # print(length)
        if length == 0:
            ans *= 0
        else:
            ans *= Fib(length+1)
        # print(ans)


    
if M==1:
    length = a[0]
    ans *= Fib(length+1)




length = N-a[-1]


ans *= Fib(length+1)

print(ans%wa)

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
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1]:
    ans = 0
  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

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
N, aM = map(int, input().split())
A = [int(input()) for _ in range(aM)]

for i in range(1, aM):
    if A[i] - A[i - 1] == 1:
        print(0)
        exit(0)

M = {}


def re(n, N):
    if N - n in M:
        return M[N - n]
    if n == N - 1:
        return 1
    elif n > N - 1:
        return 0
    a = re(n + 1, N) + re(n + 2, N)
    M[N - n] = a
    return a


ka = []
if aM >= 1:
    if A[-1] != N:
        A.append(N)
    l = [0]
    for a in A:
        ka.append(a - l[-1])
        #l.append(a)
        l.append(a + 1)
else:
    ka = [N]

print(ka)
res = 1
for a in ka:
    res *= (re(0, a) % 1000000007)
print(res%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
BIG_NUM = 10**9+7
def stairs_n(n):
    if n <= 3:
        return n
    else:
        return stairs_n(n-1)+stairs_n(n-2)

#print(stairs_n(30))

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

if m == 0:
    print(stairs_n(n)%BIG_NUM)
else:


    a_list = [int(input()) for _ in range(m)]
    a_list.append(n)
    a_list.insert(0,1)
    a_np = np.array(a_list)
    diff_a_np = np.diff(a_np)-1
    ans = 1
    # print(a_np)
    # print(diff_a_np)
    for num in diff_a_np:
        ans *= stairs_n(num)

    print(ans%BIG_NUM)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
 
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1
 
count = 0
for i in range(n+1):
    if  i !=  A[count]:
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % (10 ** 9 + 7)
        elif i == 1:
            dp[i] += dp[i-1] % (10 ** 9 + 7)
    else:
            count += 1
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

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

if n == 1:
    print(1)

elif n == 2 and a[-1] ==1:
    print(1)
    
elif n == a[-1]:
    print(0)
    
else:
    c = 0
    t = a[c]-1
    x, y = 0, 1
    for i in range(n):
        if x == 0 and y == 0:
            break
        elif i == t:
            x, y = y, 0
            if a[c]-1 == a[-1]-1:
                continue
            else:
                c += 1
                t = a[c]-1
        else:
            x, y = y, x + y
    print(y%1000000007)

Submission status: Runtime Error

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

import functools
import operator

def fib(n):
	a, b = 0, 1
	for i in range(n):
		a, b = b, a + b
	return b
if m == 1:
	print(fib(hoge[0]-1)*fib(n-hoge[0]-1))
else:
	hogex = [x - y for (x, y) in zip(hoge2, hoge[:-1])]

	if 1 in hogex:
		print(0)
	else:
		hoger = [hoge[0]] + hogex
		hogem = list(map(lambda x: x -2,hoger))
		fibli = list(map(fib,hogem))
		res = functools.reduce(operator.mul, fibli) % 1000000007
	print(res)