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 = [int(e) for e in input().split()]
div = 1000000007
a=[]
for i in range(N_M[1]):
  a.append(int(input()))

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]

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

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 = int(input())
    try:
        if _a == a[-1]:
            continue
    except:
        pass
    a.append(_a)
a.append(n + 1)
m = len(a)

memo = {0: 1, 1: 1, 2: 2}
def chk(n):
    if n in memo:
        return memo[n]
    else:
        make(n)
        return memo[n]

def make(n):
    if n in memo:
        return
    make(n - 1)
    make(n - 2)
    memo[n] = (memo[n-1] + memo[n-2]) % 1000000007

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

cur = 0
tot = 1
#from sys import stderr
#for k in range(100):
#    print(f'0-{k}: {chk(k)}', file=stderr)

for i in range(m):
    nxt = a[i] - 1
    add = chk(nxt - cur)
    #print(f'{cur}-{nxt}: {add}', file=stderr)
    tot *= add
    tot %= 1000000007
    cur = nxt + 2
print(tot % 1000000007)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10030)

memo=[0]*10**5
memo[0]=1
memo[1]=1

def fib(n):
#  print(n)
  ret=0
  if n==0 or n==1:
    return 1
  if memo[n-1]!=0:
    ret+=memo[n-1]
  else:
    ret+=fib(n-1)
  if memo[n-2]!=0:
    ret+=memo[n-2]
  else:
    ret+=fib(n-2)
  while(ret>10**9+7):
    ret%=10**9+7
  memo[n]=ret
  return ret


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 = [int(input()) for _ in range(M)]
mod = 10 ** 9 + 7

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

Submission status: Runtime Error

Solution code:
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(1,M) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

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

    ans = 1

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

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

Submission status: Runtime Error

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

#連続する壊れていない階段の数を求める
li_new = [-1]*(m+1)
li_new[0] = li[0]
for i in range(1,m):
    li_new[i] = li[i] - (li[i-1]+1)
li_new[m] = n - li[m-1]
#print(li_new)

#必用な部分までのフィボナッチ数をリストに保存
fib = [0] * (max(li_new)+1)
fib[0] = 0
fib[1] = 1
fib[2] = 1
for i in range(3,max(li_new)+1):
    fib[i] = fib[i-2] + fib[i-1]
#print(fib)

#連続する壊れていない階段の数ごとのフィボナッチ数の積
ans = 1
for i in li_new:
    ans *= fib[i]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:

a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
    print(answer%1000000007)

Submission status: Runtime Error

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

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n -2)

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)
    a_p = a

sum *= fib(N - a_p)

print(sum % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [int(input())for i in range(0,m)]
div = 1000000007
pat = [1,1]
x =  min([a[i]-a[i-1] for i in range(1,m)])
for i in range(2,x+1):
    pat.append(pat[i-2]+pat[i-1])
ans = pat[a[0]-1]
for i in range(1,m):
    ans *= pat[a[i] - a[i-1] -2]
ans *= pat[n- a[-1]-1]
print(ans%div)

Submission status: Runtime Error

Solution code:
import numpy as np


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

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

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

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

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


print(int(ans)%(1000000007))

Submission status: Runtime Error

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

zero_flag = False

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

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

blocks.append(n - last_ana)

b_max = max(blocks)

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

if 0 in blocks:
    ans = 0
else:
    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans *= c[num - 1]
        if ans >= BIGNUM:
            ans %= BIGNUM

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

    if locale + num in hole:
        return

    if res >= 1000000007:
        res=res%1000000007

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

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

print(res)

Submission status: Runtime Error

Solution code:
def fio(x,y):
    return x+y

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

n = [0,1,2]

for i in range(1,100000):
    n.append(fio(n[i],n[i+1]))

last_break = 0
ans = 1
ans = ans * n[a[0]-last_break-1]
ans = ans % 1000000007
last_break = a[0]

if a[0] == 1:
    ans = 1
    
for i in range(1,m):
    ans = ans * n[max(0,a[i]-last_break-2)]
    ans = ans % 1000000007
    last_break = a[i]
    
ans = ans * n[n_a-last_break-1]
ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[]
count=[]
for i in range(m):
  a=int(input())
  if a-1 in A:
    print(0)
    break
  A.append(a)
A=sorted(list(set(A)))
c=1
d=1
for i in range(A[0]-1):
  c=d%(10**9+7)
  d=(c+d)%(10**9+7)
count.append(c)
if m>1:
  for i in range(1,len(A)-1):
    e=1
    f=1
    for j in range(A[i+1]-A[i]-2):
      e=f%(10**9+7)
      f=(e+f)%(10**9+7)
    count.append(e)
a=1
b=1
for i in range(n-A[-1]-1):
  a=b%(10**9+7)
  b=(a+b)%(10**9+7)
count.append(a)
Total=1
for i in range(len(count)):
  Total*=count[i]%(10**9+7)
print(Total%(10**9+7))

Submission status: Runtime Error

Solution code:
#C問題
N, M = map(int, input().split())
lack = []
for _ in range(M):
    lack.append(int(input()))

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

print(fib(N)%1000000007)

Submission status: Runtime Error

Solution code:
mod = 1000000007
n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
b = [0] * n
if a.count(1) == 0:
    b[0] = 1
else:
     b[0] = 0
if a.count(2) == 0:
    b[1] = b[0] + 1
else:
    b[1] = 0

for i in range(2,n):
    if a.count(i+1) == 0:
        b[i] = (b[i-2] + b[i-1])%mod
    else:
        b[i] = 0
print(b[n-1])

Submission status: Runtime Error

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

inf=1000000007

l=[1,1]
for i in range(n+2):
    l.append((l[i]+l[i+1])%inf)

k=[a[0]]
for i in range(m-1):
    k.append(a[i+1]-a[i]-1)
k.append(n-a[m-1])

for i in range(1,len(k)):
   if k[i]==0:
       print(0)
       exit()
ans=1

for j in range(len(k)):
    ans=(ans*l[k[j]-1])%inf
print(ans%inf)

Submission status: Runtime Error

Solution code:
import sympy as sym
def FibRe(n):
    x = sym.symbols('x',nonnegative=True,integer=True)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
    result=Fib.subs(x,n)
    result=result.evalf(int(n*3/14)+1)
    return int(result)

N,M = map(int,input().split())
if M == 0:
  print(FibRe(N+2))
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= FibRe(S[i+1]-S[i]) 

  print(P%1000000007)

Submission status: Runtime Error

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

if n = 1:
  pat = 1
else:
  pt = [1]
  if (1 in a):
    pt.append(0)
  else:
    pt.append(1)

  for i in range(2, n + 1):
    if (i in a):
      pt.append(0)
    else:
      if (i-1 in a):
        pt.append(pt[i-2])
      else:
        pt.append(pt[i-1] + pt[i-2])

pat = (pt[-1] % 1000000007)
print(pat)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for _ in range(M)]
ans = 1
z = False

def fib(n):
    a1 = 2
    a2 = 1 
    if n==2:
        return 2
    elif n==1:
        return 1
    else:
        count = 1
        for i in range(n-2):
            count = a1 + a2
            a2 = a1
            a1 = count
        return count



for i in range(M):
    if i != 0:
        if a[i]-a[i-1] != 1:
            ans *= fib(a[i]-a[i-1]-2)
        else:
            z = True
            break
    else:
        ans *= fib(a[i]-1)

ans *= fib(N-a[-1]-1)

if z:
    print(0)
else:
    print(str(ans%1000000007))

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]
AS = {}
for _ in range(M):
    i = int(input())
    AS[i] = 0
visited = {}

def dfs(i):
    if i == N:
        return 1
    if i > N:
        return 0
    if AS.get(i) == 0:
        return 0
    if i in visited:
        return visited[i]
    total = 0
    total += dfs(i + 1)
    total += dfs(i + 2)
    visited[i] = total
    return total

print(dfs(0))

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input()) - 1] = 0

    # print(n, m)
    # print(a)
    # ans = step(a, 0)

    f = [0] * n
    if a[0] == 0:
        f[0] = 0
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 1
    else:
        a[0] = 1
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 2

    if a[1] == 0:
        f[1] = 0

    # print(f)
    for i in range(2, n):
        # print(i)
        if a[i]:
            f[i] = (f[i-1] + f[i-2])
    # print(f)
    print(f[n-1] % LARGE)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
def nibutan(x,l):
    low=0
    high=len(l)-1
    while low<=high:
      mid=(low+high)//2
      guess=l[mid]
      if guess==x:
         return True
      elif guess>x:
          high=mid-1
      elif guess<x:
          low=mid+1
    return False
if m==0:
  pass
else:
  for i in range(m):
    l.append(int(input()))
l1=[0 for i in range(n)]
if 1 in l:
  l1[0]=0
else:
  l1[0]=1

if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n>=3:
  for i in range(3,n+1): 
    if nibutan(i,l):
      pass
    else:
      l1[i-1]=(l1[i-2]+l1[i-3])%(((10**9)+7))
print(l1[n-1])

Submission status: Runtime Error

Solution code:

import sys


n,m = map(int, input().split())
steps = [True] * (n+1)
for i in range(m):
    steps[int(input())] = False

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

ans = 1

l = 0
r = 0
idx = 0
finished = 2
while l < len(steps):

    if idx >= len(steps):
        if r-l > finished:
            for i in range(finished+1, r-l+1):
                dp[i] = dp[i-2] + dp[i-1]
                finished = i
        ans *= dp[r-l]
        break

    if steps[idx]:
        r = idx
    else:
        # idx段目が壊れてる
        #次も壊れてるなら終わり
        if steps[idx+1] == False:
            print(0)
            exit()
        else: 
            if r-l > finished:
                for i in range(finished+1, r-l+1):
                    dp[i] = dp[i-2] + dp[i-1]
                    finished = i
            ans *= dp[r-l]
            l = idx+1
            r = idx+1
    idx += 1

print(ans%(10**9+7))

Submission status: Runtime Error

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

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n -2)

safe_area = []
a_p = int(input())
safe_area.append(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    safe_area.append(diff-1)
    a_p = a

safe_area.append(N - a_p)

sum = 1
for i in safe_area:
    sum *= fib(i)
print(sum % 1000000007)

Submission status: Runtime Error

Solution code:
cache = {1: 1, 2: 2}


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


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

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

Submission status: Runtime Error

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

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for a_ in a:
    hole = a_ - hole
    pattern *= fibo(hole-1)
    hole = a_
    
pattern *= fibo(N-hole-1)

print(pattern % 1_000_000_007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(input()))
for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    # a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    # a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print(true_ans)

Submission status: Runtime Error

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

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

before = 0
total = 1
flag = False
for a in a_i:
    if a == before:
        flag = True
        break
    x = a - 1 - before
    fib = Fib(x+2)
    total = total*fib
    before = a + 1
if flag:
    print("0")
else:
    x = n - before
    total = total*Fib(x+2)
    print(total%1000000007)

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n == 0:
        return 0 # F0
    elif n == 1:
        return 1 # F1
    return fibonacci_sub2(n-2, 1, 0) #F2以降

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

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
a.append(N+1)
anser = 1
start = 0
for i in range(M+1):
    Bre = a.pop(0)
    if Bre == start:
        anser = 0
        break
    anser = anser * fibonacci(Bre - start + 1)
    start = Bre + 1

print(anser % 1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import sympy as sym
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N,M = map(int, input().split(" "))
	#N = int(input())
	#S = input()
	#S = list(S)
	
	a = []
	for _ in range(M):
		tmp = int(input())
		if len(a) != 0:
			if tmp-1 == a[-1]:
				print(0)
				sys.exit()
		a.append(tmp)

	if M == 0:
		print(fb(N+1))
		sys.exit()

	base = 0
	ans = 1
	for i, vol in enumerate(a):
		if base == 0:
			ans = ans * fb(vol)
			base = vol
		else:
			ans = (ans% 1000000007) * (fb(vol-base)% 1000000007)
			base = vol

	if N != base:
		ans = (ans% 1000000007) * (fb(N-base)% 1000000007)

	print(ans % 1000000007)


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 0
    for _ in range(num):
        a, b = a + b, a
    return b

if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

zero_flag = False

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

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

blocks.append(n - last_ana)

print(max(blocks))
b_max = max(blocks)

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

if 0 in blocks:
    ans = 0
else:
    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans *= c[num - 1]
        if ans >= BIGNUM:
            ans %= BIGNUM

print(ans)

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

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


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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
for i in range(len(hoge)-1):
  sa=hoge[i+1]-hoge[i]-1
  ans=ans*fib[sa]
  ans=ans%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
def countStep(n):
    global S, b
    if n==-1:
        return 0
    elif n==0:
        return 1
    elif str(n) in b:
        count = S[n]
        return count
    else:
        count1 = countStep(n-1)
        count2 = countStep(n-2)
        count = count1 + count2
        b.append(str(n))
        S[n] = count
        return count

N,M = map(int,input().split())
b = []
for _ in range(M):
  b.append(input())
S = [0] * (N+1)

print(countStep(N) % 1000000007)

Submission status: Runtime Error

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

def fibo(x2):
    if (x2 == 1) or (x2 == 2):
        return (1)
    else:
        return((fibo(x2-1) + fibo(x2-2)) // (10**9 + 7))

aa = []
#aa.append(a[0]-)
for k in range(M-1):
    aa.append(a[k+1] - a[k] - 1)
#aa.append(N - a(M))

if 0 in aa:
    ans = 0

else:
    ans_list = []
    for i in range(M-1):
        if aa[i] >= 1:
            ans_list.append(fibo(aa[i]))

	ans_list.append(fibo(a[1])
	ans_list.append(fibo(N - a[M]))

	ans = (sum(ans_list) // (10**9 + 7))

print(ans)

Submission status: Runtime Error

Solution code:
lst = dict({0: 1, 1: 1, 2: 2})
def calc(n):
    if (n in lst):
        return lst[n]
    else:
        lst[n] = calc(n-1) + calc(n-2)
        return lst[n]

N, M = [int(x) for x in input().split()]
a_list = [int(input()) for _ in range(M)]
span_list = [a_list[0]-1]
ans = -1
for i, a in enumerate(a_list[:-1]):
    if (a_list[i+1] - a) == 1:
        ans = 0
    else:
        span_list.append(a_list[i+1] - 2 - a)
if (ans == 0):
    print(ans)
else:
    span_list.append(N - a_list[-1] -1)
    max_span = max(span_list)
    for i in range(max_span+1):
        calc(i)
    ans = 1
    for span in span_list:
        ans = (ans * lst[span]) % (10**9+7)
    print(ans)

Submission status: Runtime Error

Solution code:
# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools
from math import factorial


div_num  = 1000000007

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

dmg = [int(input()) for _ in range(M)]

for i in range(M - 1):
    # 連番なら終了
    if dmg[i] == (dmg[i + 1] - 1):
        print(0)
        exit()

comb_list = []
start = 0
for i in range(len(dmg) + 1):
    if i == len(dmg):
        n = N - start
    else:
        n = (dmg[i] - 1) - start
    j = 0
    comb_sum = 0
    while True:
        if 2 * j > n:
            break
        num = j + (n - (2 * j))
        r = j
        comb_sum += int(factorial(num) / factorial(r) / factorial(num - r))
        j += 1
    if i < len(dmg):
        start = dmg[i] + 1
    comb_list.append(comb_sum)

result = 1

for elem in comb_list:
    result *= elem

print(result % div_num)

Submission status: Runtime Error

Solution code:

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

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

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

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

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


print(counter_arr[-1])

Submission status: Runtime Error

Solution code:
N, M = [int(s) for s in input().split()]
AS = {}
for _ in range(M):
    i = int(input())
    AS[i] = 0
visited = {}

def dfs(i):
    if i == N:
        return 1
    if i > N:
        return 0
    if AS.get(i) == 0:
        return 0
    if i in visited:
        return visited[i]
    total = 0
    total += dfs(i + 1)
    total += dfs(i + 2)
    visited[i] = total
    return total

print(dfs(0), visited, AS)

Submission status: Runtime Error

Solution code:
def fib2(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]

inp = input()
n = int(inp.split()[0])
m = int(inp.split()[1])
a = []
for i in range(m):
  a.append(int(input()))
  
mul_list = []
nochance = False
for j in range(m+1):
  if j == 0:
    ss = a[0]
    if ss <= 0:
      p = 1
    else:
      p = fib2(ss)
    mul_list.append(p)
  elif j == m:
    step = n - a[-1]
    p = fib2(step)
    mul_list.append(p)
  else:
    step = a[j] - a[j-1] - 1
    if step == 0:
      nochance = True
      break
    p = fib2(step)
    mul_list.append(p)
    

if nochance:
  print(0)
else:
  ans = 1
  for b in mul_list:
    ans *= b
  print(ans%1000000007)