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:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
o = 1
p = 0
for i in range(m):
    t = int(input())
    if t < 3:
        p = t
        pass
    elif t == 3:
        p = t
        o = 2
        pass
    elif t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
        pass
    elif t-1-p == 2:
        p = t
        pass
    elif t-1-p > 2:
        o = o*endFib(t-2-p)
        p = t
if n-p > 2:
    o = o * endFib(n-p-1)
print(o % 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)]
# A = range(M)
B = range(M)
for i in range(M):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == (M - 1):
    diff = N - A[M - 1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    if diff == 0:
      print(0)
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans % 1000000007)

Submission status: Runtime Error

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

a_list = [0] * M

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

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

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

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

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

MOD = 1000000007
#print(new_list)
value = 1
for item in new_list:
    if len(item) == 0:
        continue
    else:
        if (len(item) - 1) % 2 == 0:
            value *= (2 ** ((len(item) - 1) // 2)) % MOD
            value %= MOD
        else:
            value *= ((2 ** ((len(item) - 1) // 2)) + 2 ** (((len(item) - 1) // 2) - 1)) % MOD
            value %= MOD

print(value)

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 = int(ans * 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:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0
    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


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

    ret = 0
    for j in range(M+2):
        if j == 0:
            continue
        elif a[j] - a[j-1] - 1 == 0:
            ret = 0
            break
        else:
            ret = ret + get_pattern(a[j]-a[j-1]-1)

    print(ret % 1000000007)

Submission status: Runtime Error

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

def stair(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return stair(x - 1) + stair(x - 2)

if m == 0:
    s = stair(n + 1)
else:
    s = stair(A[0]) * stair(n - A[m - 1])
    for i in range(m - 1):
        a = A[i + 1] - A[i] - 1
        s = s * stair(a)



print(int(s%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]
            count = count % 1000000007
    print(count % 1000000007)

Submission status: Runtime Error

Solution code:
import scipy.misc as scm

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

a_s = []
flag = False

for i in range(M):
    a_m = int(input())
    a_s.append(a_m)
    if(i > 0 and a_m == a_s[i-1]+1):
        flag = True
        print(0)
        break


if not flag:
    way = 1
    now = 0
    for a in a_s:
        # print("a = " + str(a))

        step = a - 1 - now
        # print("now = " + str(now))
        # print("step = " + str(step))
        w = 0
        for i in range(step//2+1):
            # print(str(step-i) + " C " + str(i))
            # print (scm.comb(step-i, i))
            w += scm.comb(step-i, i)
        if(w != 0):
            way = w * way
        now = a+1
        # print(w)

    step = N - now
    # print("way = " + str(way))
    w = 0
    for i in range(step//2+1):
        # print(str(step-i) + " C " + str(i))
        # print (scm.comb(step-i, i))

        w += scm.comb(step-i, i)
    # print("w = " +str(w))
    if(w != 0):
        way = w * way

    print(int(way % 1000000007))

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

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:
N, M = map(int, input().split())
broken_floors = [int(input()) for _ in range(M)]

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

print(get_num_of_ways(N, broken_floors))

Submission status: Runtime Error

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

for n, i in enumerate(a):
    if n > 0:
        if (a[n] - a[n-1]) == 1:
            print(0)
            exit()

def search(i, n):
    if i in a:
        return 0
    if i == n:
        return 1
    if i > n:
        return 0
    return search(i+1, n) + search(i+2, n)

ans = 1
start = 0
a.append(N+1)
for num in a:
    ans *= search(start, num-1)
    for i in range(1, N):
        start = num + i
        if start not in a:
            break

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
phi = (1 + math.sqrt(5)) / 2

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

Submission status: Runtime Error

Solution code:

import sympy as sym

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)

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 fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

def culcC(num):
    return fib(num) + fib(num-1)
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
elif m == 0:
    print(culcC(n) % 1000000007)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):
#        連続穴
        if stand == a:
            ans = 0
            break
        step_num = a - stand - 1
        c = culcC(step_num)
        ans *= c if c > 0 else 1
        stand = a + 1
        
    # 最後のaからnまでで計算
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 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):
  NMAX = 1000000007
  res = 0
  Mmax = int(K/2)
  for M in range(Mmax+1):
    N=K-M*2
    res = (res+combi(M+N,M))%NMAX
  return res

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

S=[0]*M

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

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

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = [int(input()) for x in range(m) ]
import numpy as np
kaidan = np.zeros(n+1)

kaidan[1] = 1 
kaidan[2] = 2 
if 1 in a_list:
    kaidan[1] = 0
    kaidan[2] = 1
if 2 in a_list: 
    kaidan[2] = 0

for x in range(3,n+1):
    kaidan[x] = kaidan[x-1]+kaidan[x-2]
    if x in a_list:
        kaidan[x]  = 0
print(int(kaidan[n])%1000000007)

Submission status: Runtime Error

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

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

d = [a[0]-1]
for j in range(1,m):
    d.append(a[j]-a[j-1]-2)

d.append(n-a[m-1]-1)


fiblist = [0] * 100000
fiblist[0] = 1
fiblist[1] = 1

for p in range(2,100000):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

#print(d)

if (-1 in d) or (-2 in d):
    print(0)
else:
    ans = 1
    for k in range(m+1):
        ans = (ans * fiblist[d[k]]) % 1000000007

    print(ans)

Submission status: Runtime Error

Solution code:
import sympy
def fibonacci(n):
    n = n+1
    x = sympy.symbols('x',nonnegative=True,integer=True)
    Fib=1/sympy.sqrt(5)*(((1+sympy.sqrt(5))/2)**(n-1)-((1-sympy.sqrt(5))/2)**(n-1))
    result=Fib.subs(x,n)
    result=result.evalf()
    return int(result)
def prod(array):
    ans = 1
    for i in range(len(array)):
        ans *= array[i]
    return ans
data = list(map(int,input().split()))
n = data[0]
m = data[1]
del data
a = [-1]
for i in range(m):#aの入力
    a.append(int(input()))
    if a[i] - a[i-1] == 1:#2段以上連続で穴が空いていたら0を出力して終了
            print(0)
            quit()
a.append(n+1)
b = []
for i in range(m+1):
    b.append(fibonacci(a[i+1]-a[i]-1))
print(prod(b)%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)]
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:
    if a-pre==0:
        print(0)
        exit()
    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:
def culc(m):
    s=0
    if m%2==1:
        m1=1 #1の個数
        m2=m//2 #2の個数
    else:
        m1=0
        m2=m//2
    
    while m2>=0:
        l1=1
        l2=1
        for i in range(m2):
            l1=l1*(m1+i+1)
            l2=l2*(i+1)
        s+=int(l1/l2)
        m1+=2
        m2+=-1
    return s

N,M=map(int,input().split())
a1=-1
b=[]
for i in range(M):

    a2=int(input())
    da=a2-a1
    a1=a2
    if da==1:
        b=[]
        break
    elif da!=0:
        b+=[da-2]

else:
    b+=[N-a2-1]


if b==[]:
    sm=0
else:
    b.sort()
    c=culc(b[0])
    sm=c
    s1=b[0]
    for i in b[1:]:
        if s1==i:
            sm=sm*c
        else:
            c=culc(i)
            sm=sm*c
print(sm%1000000007)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
b = [-1]
ans = 1

def dfs(top, bot):
    if top == bot:
        return 1
    elif top < bot:
        return 0
    else:
        return dfs(top - 1, bot) + dfs(top - 2, bot)
    
for i in range(m):
    broken = int(input())
    b.append(broken)

b.append(n + 1)
##print (b)

for i in range(len(b) - 1):
    if b[i] + 1 in b:
        ans = 0
        break
    else:
##        print (b[i + 1] - 1, b[i] + 1)
        ans *= dfs(b[i + 1] - 1, b[i] + 1)
        
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

before1 = 1
before2 = 0
if len(a)>0:
    ai = a[aindex]

for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        if aindex < len(a)-1:
            aindex += 1
            ai = a[aindex]
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current


print(before1)

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 = []
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)

temp = n-a[-1]-1
if temp>0:
    ans *= count_steps(temp)
print(ans%1000000007)

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

zero_renban = np.array(zero_renban, dtype = 'int64')
zero_renban = np.delete(zero_renban, np.where(zero_renban == 0)[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 *= fib(i)

print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
hoge = input().split()
N = int(hoge[0])
M = int(hoge[1])
broken = []
for i in range(M):
  broken.append(int(input()))

anss = []
safes = []
fibo = [1,2]
safes.append(broken[0]-1)
for i in range(M-1):
  safes.append(broken[i+1] - broken[i] - 1)

safes.append(N-broken[M-1] - 1)

for i in range(len(safes)):
  if safes[i] == 0:
    anss.append(1) # 間が0
  elif safes[i] == 1:
    anss.append(1) # 間が1つ
  elif safes[i] == 2:
    anss.append(2) # 間が2つ
  else:
    for i in range(safes[i] - 2): # 間が3つ以上
      fibo.append(fibo[i] + fibo[i+1])
    anss.append(fibo.pop())
    fibo = [1, 2]

answer = 1
print(safes)
print(anss)
for i in range(len(anss)):
  answer = answer * anss[i]
# print(safes)
  
flag = 0
for i in range(M-1):
  if broken[i+1] - broken[i] == 1:
    flag = 1

if flag == 0:
  print(answer%1000000007)
else:
  print(0)

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() ))
  buf = a[q]
  if buf - a[q] == 1:
    print 0
    exit(0)

now = [0]*100001

if m == 0:
  now[0] = 1
  now[1] = 1
  for q in range(2,n+1):
    now[q] = (now[q-1] + now[q-2]) % 1000000007
  print now[q] % 1000000007
  exit(0)
    
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]) % 1000000007
  
print now[q] % 1000000007

Submission status: Runtime Error

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

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

if min(Ds)==0:
    print(0)
else:
    Fs = [fibo(n) for n in Ds]
    pattern = 1
    for f in Fs:
        pattern *= f
    print(pattern % 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)]+[n+1]
mod=1000000007
ms=[0]*n

def dd(n):
    if ms[n]>0:
        return ms[n]
    if n==1:
        ms[n]=1
        return 1
    if n==2:
        ms[n]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n]=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

print(ans)

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

    if m == 0:
        print(dp[n]%d)

    else:
        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())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(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)
Ans = 10
print(Ans % 1000000007)

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('000*', 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(count % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def serach(locale, num):
    global res
    if locale + num > N:
        return

    if locale + num == N:
        res+=1
        if res >= 1000000007:
            res=res%1000000007
        return

    if locale + num in hole:
        return

    serach(locale+num, 1)
    serach(locale+num, 2)

serach(0,1)
serach(0,2)

print(res)

Submission status: Runtime Error

Solution code:
def up_stairs(At, now):
  
  if now == At:
    return 1
  if now > At:
    return 0

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


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

now_step = 0
ans = 1
for i in range(M):
  A = int(input())
  ans *= up_stairs(A - 1, now_step)
  now_step = A + 1

ans *= up_stairs(N, now_step)
print(int(ans % 1000000007))

Submission status: Runtime Error

Solution code:
from functools import reduce
from operator import mul 
n,m = map(int, input().split())
al = list(map(int, [input() for i in range(m)]))

al.append(n + 1)
pl = []
pre = 0
for elm in al:
    if elm == 1:
        pre = elm + 1
        continue
    if pre == n:
        continue
    max = elm - 1 - pre
    res = 0
    f0 = 0
    f1 = 1
    for i in range(max):
        res = f0 + f1
        f0 = f1
        f1 = res
    pl.append(res)
    pre = elm + 1

print(reduce(mul, pl) % 1000000007)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(100000)

dp = [1,0]
def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 

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

Submission status: Runtime Error

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

b = []
start = 0
for x in a:
    b += [-start+x]
    start = x+1
b  += [-start+n+1]

def steps(N, cnt):
    if N == 2:
        cnt += 1
        return cnt
    if N ==1:
        cnt += 1
        return cnt
    if N > 2:
        cnt = steps(N-1,cnt)
        cnt = steps(N-2,cnt)
        return cnt

if 0 in b:
    print(0)

else:
    ans = 0
    for z in b:
        ans += steps(z, 0)

    print(ans%full)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**9)

if m == 0:
    print(countWays_memo(n))
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    def countWays_memo(n):
        memo = [-1]*(n+1)
        def _countWays(n):
            if n < 0:
                return 0
            elif n == 0:
                return 1
            else:
                if memo[n] > -1:
                    return memo[n]
                else:
                    memo[n] = _countWays(n-1) + _countWays(n-2) 
                    return memo[n]
        return _countWays(n)

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

Submission status: Runtime Error

Solution code:
import sys
hoge = input().split()
N = int(hoge[0])
M = int(hoge[1])
broken = []
for i in range(M):
  broken.append(int(input()))

anss = []
safes = []
fibo = [1,2]
safes.append(broken[0]-1)
for i in range(M-1):
  safes.append(broken[i+1] - broken[i] - 1)

safes.append(N-broken[M-1] - 1)

for i in range(len(safes)):
  if safes[i] == 0:
    anss.append(1) # 間が0
  elif safes[i] == 1:
    anss.append(1) # 間が1つ
  elif safes[i] == 2:
    anss.append(2) # 間が2つ
  else:
    for i in range(safes[i] - 2): # 間が3つ以上
      fibo.append(fibo[i] + fibo[i+1])
    anss.append(fibo.pop())
    fibo = [1, 2]

answer = 1
print(safes)
print(anss)
for i in range(len(anss)):
  answer = answer * anss[i]
# print(safes)
  
flag = 0
for i in range(M-1):
  if broken[i+1] - broken[i] == 1:
    flag = 1

if flag == 0:
  print(answer%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
import math
phi = (1 + math.sqrt(5)) / 2

def counter(n):
    if n == 0:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
if M == 0:
    print(counter(N+1))
    exit()
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
#ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)
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 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 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 = range(M)
B = range(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)
Ans = 10
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = tuple(map(int, input().split()))
ans = 0
a = []
tmp = -10
d = 10**9 + 7

for i in range(M):
    num = (int(input()))
    if ((tmp+1) == num):
        print(0)
        exit()
    a.append(num)
    tmp = num

def stairs(n):
    if (n in a):
        return 0
    if (n == 1):
        return 1
    if (n == 2):
        return 2
    ans = stairs(n-1)%d + stairs(n-2)%d
    return ans

print(stairs(N))

Submission status: Runtime Error

Solution code:
import math

fact_mamo = [-1 for _ in range(100000)]
def c(n, r):
    u = fact_mamo[n]
    if u == -1:
        u = math.factorial(n)
        fact_mamo[n] = u

    d1 = fact_mamo[n-r]
    if d1 == -1:
        d1 = math.factorial(n-r)
        fact_mamo[n-r] = d1

    d2 = fact_mamo[r]
    if d2 == -1:
        d2 = math.factorial(r)
        fact_mamo[r] = d2

    d = d1*d2
    return u//d

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



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

mod = 1000000007
if m == 0:
    print(f(n))
    exit()
ptn = f(a[0]-1)
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        ptn = 0
        break
    ptn = (ptn * f(a[i+1]-1 - a[i]-1)) % mod
ptn = (ptn * f(n - a[len(a)-1]-1)) % mod

print(ptn)