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:
N, M = map(int, input().split())
now = 0
count = 1
flag = True
for _ in range(M):
        a = int(input())
        if a == now:
                print(0)
                flag = False
                break
        else:
                dif = a - now - 1
                x = int(dif / 2)
                y = 0
                for i in range(x+1):
                        z = 1
                        j = dif - 2*i
                        for k in range(i):
                                z *= (i+j-k)/(i-k)
                        y += z
                count *= y
                now = a + 1
if flag:
        dif = N - now
        x = int(dif/2)
        y = 0
        for i in range(x+1):
                z = 1
                j = dif - 2*i
                for k in range(i):
                        z *= (i+j-k)/(i-k)
                y += z
        count *= y
        print(int(count%1000000007))

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append((fib[-1] + fib[-2]) % MOD)
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1] % MOD
  
  print(ans % MOD)

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)]
A = [0] * M
B = [0]*(M)
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:
import sys
import numpy as np

X = (1+np.sqrt(5))/2
Y = (1-np.sqrt(5))/2
Z = np.sqrt(5)

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

def cases(N):
    if N == 0:
        print('0')
        sys.exit()
    return int((np.power(X, N)-np.power(Y, N))/Z+0.1)
    
    
if __name__ == '__main__':
    N, M = InputToInt()
    result = 1
    oldA = -1
    for i in range(M):
        A = int(input())
        result *= cases(A - oldA - 1)
        result %= 1000000007
        oldA = A
    result *= cases(N - A)
    print(result % 1000000007)

Submission status: Runtime Error

Solution code:
def combi(N,R):
  res = 1
  for r in range(R):
    res *= (N-r)/(R-r)
  return int(res)
  
def calc_pat(K):
  res = 0
  Mmax = int(K/2)
  for M in range(Mmax+1):
    N=K-M*2
    res = res+combi(M+N,M)
  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 sys
sys.setrecursionlimit(10000)
N,M=map(int,input().split())
L=[int(input()) for _ in range(M)]
ans=0

def dfs(i):
	global ans
	if i==N:
		ans+=1
		return True
	if i>N:return False
	if i in L:return True
	if dfs(i+1)==False:return True
	if dfs(i+2)==False:return True

dfs(0)
print(ans%1000000007)

Submission status: Runtime Error

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

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

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        tmp += cmb(n, r, exact=True)
        dif = n-r
        n -= 1
        # print("tmp",tmp,n,r)
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

sys.setrecursionlimit(N * 2)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)


def d(n):
    if n < 1:
        return 0
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]
    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Submission status: Runtime Error

Solution code:
import re
import math

def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

n,m = map(int, input().split())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('0+', steps)
b = len(re.findall('11', steps))
# print(steps)
count = 1
for i in a:
    count *= fib(len(i)+1) % 1000000007

if b != 0:
    print(0)
else:
    print(round(count % 1000000007))

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append(fib[-1] + fib[-2])
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1] % MOD
  
  print(ans % MOD)

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


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

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=1000)
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)%1000000007)

Submission status: Runtime Error

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

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

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

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


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:
def _comb(N,M):
    if not N:return(0)
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
if N-1 in A:pass
else:A.append(N+1)
if 1 in A:pre=-1
else:pre=0
count=1
for a in A:
    count*=sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)])
    pre=a+1
print(count%1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial
N,M=list(map(int,input().split()))
dansa=[int(input()) for _ in range(M)]
ans=1
flag=True
if dansa[0]==0:
    print("0")
else:
    if len(dansa)>1:
        for i in range(M-1):
            if dansa[i]+1==dansa[i+1]:
                print("0")
                flag=False
                break
if flag:
    dansa.insert(0,0)
    dansa.append(N)
    for i in range(M+1):
        tmp=dansa[i+1]-dansa[i]-1
        arr=[i for i in range(int(tmp/2)+1)]
        #print("tmp:{}".format(tmp))
        hoge=0
        """
        if tmp%2==0:
            arr=[j*2 for j in range(0,int(tmp/2+1))]
            
        else:
            arr=[j*2+1 for j in range(0,int((tmp+1)/2))]
        """
        #print(arr)
        #if tmp%2==0:
        for k in arr:
            n=tmp-k
            hoge+=factorial(n) / factorial(k) / factorial(n-k)
            
        print(hoge)
        ans=ans*hoge
        print(ans)
    #print(int(ans%1000000007))
    print(ans)

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)
    kaidan[i] %= 1000000007
    return kaidan[i]

N, M = map(int, input().split())
kaidan = [0 for i in range(1000000)]
#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:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
if m != 0:
  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
    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:
n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))


def count_steps(NN):

    steps = [0] * (NN + 3)
    steps[1] = 1
    steps[2] = 2
    for i in range(3, NN + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
    return steps[NN]

if a[0] == 1:
    ans = 1
else:
    ans = count_steps(a[0]-1)

for i in range(1, len(a)):
    temp = a[i]-a[i-1]-2
    if temp < 0:
        ans = 0
    elif temp==0:
        ans *= 1
    else:
        ans *= count_steps(temp)

ans *= count_steps(n-a[-1]-1)
print(ans%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_np = np.array(a_list)
    diff_a_np = np.diff(a_np)-1
    ans = 1
    # print(a_np)
    # print(diff_a_np-1)
    ans *= (a_list[0])
    for num in diff_a_np:
        ans *= stairs_n(num)

    print(ans%BIG_NUM)

Submission status: Runtime Error

Solution code:
n,m = map(int,raw_input().split())
a = []
buf = -111
for q in range(m):
  a.append(int( raw_input() ))
  if buf - a[q] == 1:
    print 0
    exit(0)

now = [0]*100001
now[0] = 1
if a[0] == 1: now[1] = 0
else: now[1] = 1

for q in range(2,n+1):
  if q in a: continue
  now[q] = now[q-1] + now[q-2]
  
print now[q] % 1000000007

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]
mod=1000000007
ms=[0]*n

def dd(n):
    if ms[n-1]>0:
        return ms[n-1]
    if n==1:
        ms[n-1]=1
        return 1
    if n==2:
        ms[n-1]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n-1]=m
    return m

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

if m!=0:
    ans=(ans%mod)*(dd(n-al[-1]-1)%mod)%mod
else:
    ans=dd(n)%mod
print(ans)

Submission status: Runtime Error

Solution code:
import functools
import operator

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)]
if A[0] == 1:
    A.pop(0)
    A.insert(0, 2)
    A.append(N)
    sabun = [A[i+1]-A[i] for i in range(M)]
else:
    A.insert(0, 0)
    A.append(N)
    sabun = [A[i+1]-A[i] for i in range(M+1)]
# print(sabun)
if min(sabun) == 0:
    print("0")
else:
    ans = [fib(i) for i in sabun]
    # print(ans)
    result = functools.reduce(operator.mul, ans)
    print(int(result%1000000007))

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)
sum %= 1000000007
print(sum)

Submission status: Runtime Error

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

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

sl = []
cnt = -1
for i in range(M):
    a = int(input())
    b = (a - 1) - (cnt + 1)
    if b == -1:
        print(0)
        break
    sl.append(max(b, 1))
    cnt = a
else:
    sl.append(max(N - (a + 1), 1))
    ans = 1
    for s in sl:
        p = 0
        for i in range(s):
            j = s - i
            if (i <= j):
                p += combinations_count(j, i)
            else:
                break
        ans *= p
        ans = ans % 1000000007
    print(ans % 1000000007)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append(fib[-1] + fib[-2])
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1])
  ans *= fib[N - a[-1] - 1]
  
  print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys

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

for i in range(1,len(a)-2):
    if a[i+1]-a[i]==1:
        print(0)
        sys,exit()

b = []
for i in range(1,len(a)):
    if i == 1:
        b.appned(a[1]-1-a[0])
    elif i == len(a)-1:
        b.append(a[i]-(a[i-1]+1))
    else:
        b.append(a[i]-1-(a[i-1]+1))

dp = []
for i in range(10**6):
    if i == 0:
        dp.append(1)
        continue
    if i == 1:
        dp.append(1)
        continue
    if i == 2:
        dp.append(2)
        continue
    dp.append((dp[i-1]+dp[i-2])%mod)

for i in range(len(b)):
    l = b[i]
    ans = (ans*dp[l])%mod
    
print(b)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)
for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        tmp += comb(n, r, exact=True)
        dif = n-r
        n -= 1
        # print("tmp",tmp,n,r)
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import functools

@functools.lru_cache(None)
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:
import re
import math

def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

n,m = map(int, input().split())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('0+', steps)
b = len(re.findall('11', steps))
# print(steps)
count = 1
for i in a:
    count *= fib(len(i)+1)

if b != 0:
    print(0)
else:
    print(round(count % 1000000007))

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)
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:
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) :
            if length - 2 * j < 0 :
                break
            step2 = math.factorial(j)
            step1 = math.factorial(int(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:
import sys

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

sys.setrecursionlimit(N * 2)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


B = [-1] * (N + 1)


def d(n):
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]

    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Submission status: Runtime Error

Solution code:
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return (fib(n - 1) + fib(n - 2)) % (10 ** 9 + 7)

def counter(n):
    if n == 1:
        return 0
    else:
#        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return fib(n)
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans = fib(a[0])
for i in range(1,M):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
ans = ans * fib(N - a[-1]) % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
N,M =map(int,input().split())
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 sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fibmemo={1:1,2:1}
for i in range(3,100000):
    fibmemo[i]=fibmemo[i-1]+fibmemo[i-2]
def fib(n):
    return fibmemo[n]

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
m=fib(a[0])
tmp=a[0]
for i in a:
    if i+1 in a:
        print(0)
        sys.exit()
    if a[0]==i:
        continue
    m=fib(i-tmp-1)*m%mod
    tmp=i
m=fib(n-tmp)*m%mod
print(m)

Submission status: Runtime Error

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

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

wa = (10**9) + 7

import sympy as sym #sympyのインポート
def Fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True) #変数xの宣言(非負の整数)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) #一般項の式
    result=Fib.subs(x,n) #xにnを代入
    result=result.evalf() #式を浮動小数点数として評価
    return int(result)





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
        ans *= Fib(length+1)


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

# print(ans)

length = N-a[-1]
# print(length)

ans *= Fib(length+1)

print(ans%wa)

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]*100001
    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:
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)

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

print(stair(n))

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)
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:
N, M = map(int, input().split())
bre = []
flag = 0
A = []
for i in range(M):
    bre.append(int(input()))
#print(bre)
A.append(bre[0] - 1)
count = 0
if len(bre) >= 2:
    for i in range(len(bre) - 1):
        a = bre[i + 1] - bre[i]
        A.append(a - 2)
        if a == 1:
            #print(0)
            flag = 1
A.append(N - bre[len(bre) - 1] - 1)

if flag == 0:
    suu = [0, 1, 2]
    for i in range(2, max(A)):
        suu.append(suu[i] + suu[i-1] )
    #print(suu)
    for i in A:
        if count == 0:
            count = suu[i]
        else :
            count *= suu[i]
    print(count % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

N,M =map(int,input().split())
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
        print(ans)
        sys.exit()

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:
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 _comb(N,M):
    if not N:return(0)
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N+1)
count=1
if 1 in A:pre=-1
else:pre=0
for a in A:
    count*=sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)])
    pre=a+1
print(count%1000000007)

Submission status: Runtime Error

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

x = [0]*(N+1)
y = [1]*(N+1)
idx = 0
for i in range(N+1):
    if i == a[idx]:
        y[i] = 0
        idx += 1
        if idx >= M:
            break
x[0] = 1
if y[1] == 0:
    x[1] = 0
else:
    x[1] = 1

for i in range(2, N+1):
    if y[i] == 0:
        x[i] = 0
    else:
        x[i] = (x[i-1] + x[i-2]) % 1000000007
print(x[N])

Submission status: Runtime Error

Solution code:

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

if M >= 1:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])
else:
    B.append(N-1)

ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)

Submission status: Runtime Error

Solution code:
def _comb(N,M):
    if not N:return(0)
    count=1
    for i in range(0,M):
        count*=N-i
    for i in range(1,M+1):
        count/=i
    return(int(count))

N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N+1)
count=1
if 1 in A:pre=-1
else:pre=0
for a in A:
    count*=sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)])
    print(sum([_comb(a-1-pre-i,i) for i in range((a-1)-pre)]),a)
    pre=a+1
print(count%1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=1000)
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())
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:
      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

print(ans)