Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
import functools
import operator

dic = {-1: 0, 0: 1, 1:1}

def pat(n):
  if n not in dic:
    dic[n] = pat(n-1) + pat(n-2)
  return dic[n]


import sys
n, m = map(int, input().split())
a = sorted(list(set(map(int, sys.stdin.readlines()))))
m = len(a)

s = 0
e = n
xs = [0] * (m + 1)
for i, j in enumerate(a):
  xs[i] = pat(j - s - 1)
  s = j + 1
xs[m] = pat(n - s)
if 0 in xs:
  print(0)
else:
  result = functools.reduce(operator.mul, xs)
  print(result % 1000000007)

Submission status: Runtime Error

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

def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
      
for i in range(M):
  if i == 0:
    P = Fib(S[i]+1)
  else:
    P *= Fib(S[i] - S[i-1])
  if i == M-1:
    P *= Fib(N - S[i] + 1)

print(P%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 0
checked_steps = {-1:0, 0:1, 1:1, 2:2}
divide_num = 1000000007 

for i in range(3, n):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count % divide_num)

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)

if 0 in blocks:
    ans = 0
else:
    ans = 1
    for num in blocks:
        if num == 1:
            continue
        k = num // 2
        m = num % 2
        cases = 3 * k - 2 + m
        ans *= cases
        # if ans >= BIGNUM:
        #     ans %= BIGNUM

print(ans)

Submission status: Runtime Error

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

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


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

dp = [0] * (N + 1)

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

Submission status: Runtime Error

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

mod = 10 ** 9 + 7


def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n] % mod
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n] % mod


A = list(int(input()) for i in range(m))

ans = Fib(A[0] + 1)
for i in range(m - 1):
    ans *= Fib(A[i + 1] - A[i])
    ans %= mod
    if A[i] + 1 == A[i + 1]:
        print(0)
        exit()
ans *= Fib(n - A[-1] + 1)
ans %= mod
print(ans % mod)

Submission status: Runtime Error

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

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):
    if s == 0:
        print(0)
    else:
        dict_steps[s] = steps.count(s)

ans = 1
for k,v in dict_steps.items():
    ans *= countWays_memo(k-1)**v
    
if steps.count(0) == 0:
    print(ans% 1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")
i_pattern = [-inf for i in range(n+1)]

#i段目までの行き方を数える
def solve(i):
    if i == 1:
        if 1 in a:
            i_pattern[1] = 0
            return 0
        else:
            i_pattern[1] = 1
            return 1
    if i == 0:
        i_pattern[0]=1
        return 1
    if i_pattern[i] >= 0:
        ret = i_pattern[i]
    else :
        if i in a:
            i_pattern[i]=0
            return 0
        ret = solve(i-1)+solve(i-2)
        i_pattern[i]=ret
    return ret

print(solve(n)%1000000007)

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
for i in range(m):
  l.append(int(input()))
l1=[0 for i in range(n)]
if 1 in l:
  l1[0]=0
if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n==1:
  print(1)
elif n==2:
  if 1 in l:
    print(1)
  else:
    print(2)
else:
  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]%(10**9+7))

Submission status: Runtime Error

Solution code:
import math

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for n in range(n)]
#list = [int(i) for i in input().split()]
#s = input()
#list = list(s)

s = [int(input()) for i in range(m)] #m行1列入力

MOD = 1000000007

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

kotae = 1

if (m == 0) :
    kotae = kotae * fib(n) % MOD
else :
    for i in range(m + 1) :
        if (i == 0) :
            kotae = kotae * fib(s[i]) % MOD
        elif (i == m) :
            kotae = kotae * fib(n - s[i-1]) % MOD
        else :
            kotae = kotae * fib(s[i] - s[i-1] - 1) % MOD


print(kotae)

Submission status: Runtime Error

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

memo = [-1] * (N+1)
def countWays(n):
    if n < 0 or (n in broken_data):
        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]

print(countWays(N) % 1000000007)

Submission status: Runtime Error

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

combination = [1,1,2]
for i in range(3,N):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []

next_a = int(input())
lst.append(combination[next_a-a-1])
a = next_a

for i in range(M-1):
    next_a = int(input())
    if next_a-a == 1:
        ans = 0
        break
    lst.append(combination[next_a-a-2])
    a = next_a
    
next_a = N
lst.append(combination[next_a-a-1])

for tmp in lst:
    ans *= tmp
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys  
import numpy as np
input = sys.stdin.readline

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


print(int(ans%1000000007))

Submission status: Runtime Error

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

dp = [0]*(N+3)
dp[0] = 1

for i in range(N+1):
    if A:
        a = A[0]
    if len(A) >= 2:
        b = A[1]

    dp[i] = dp[i] % (10**9 + 7)
    if not i+1 == a:
        dp[i+1] += dp[i]
    else:
        A.popleft()
    if not i+2 == b and not i+2 == a:
        dp[i+2] += dp[i]
print(dp[N])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
 
MOD = 1000000007  # type: int
 
def solve(N: int, M: int, a: "List[int]"):
    i = 2
    arr = [1, 1]
    seek = 0
    while a[seek]==1:
        arr[1] = 0
        seek+=1
    while i<=N:
        if seek < len(a) and i == a[seek]:
            arr[0], arr[1] = arr[1], 0
            seek+=1
        else:
            arr[0], arr[1] = arr[1], (arr[0]+arr[1])%MOD
        i+=1
    print(arr[1])
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = 10**9+7
nots = [int(input()) for i in range(m)]
leng = len(nots)
cnt = 0
dp = [0]*(n+1)
dp[0] = 1
if leng > 0 and nots[0] == 1:
  dp[1] = 0
else:
  dp[1] = 1
if n < 2:
  print(1)
  exit()

for i in range(2,n+1):
  if leng > 0 and nots[cnt] == i:
    dp[i] = 0
  else:
    dp[i] = dp[i-1] + dp[i-2]
  if nots[cnt] < i and cnt < leng - 1:
    cnt += 1
print(dp[n] % num)

Submission status: Runtime Error

Solution code:
def calc(_n):
    if _n == 1:
        return 1
    elif _n == 2:
        return 2
    else:
        return calc(_n - 1) + calc(_n -2)


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 prev_a + 1 == N:
    ans = 0
else:
    ans = ans * calc(N - prev_a - 1)

print( ans % 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]
for i in range(2,n+1):
    pat.append(pat[i-2]+pat[i-1])
ans = pat[a[0]-1]
sa = 0
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:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
 
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b


ans = 1
for i in range(M+1):
	if i == 0:
		ans = (ans*Fib(a[0]-(-1)))%dekai
	elif i == M:
		ans = (ans*Fib(N+1-a[M-1]))%dekai
	else:
		ans = (ans*Fib(a[i]-a[i-1]))%dekai
print(ans)

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])
    max_dis = max(max_dis, dis[-1])
  max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis - 2):
    fib.append(fib[-1] + fib[-2])
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1]
  
  print(ans % MOD)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
A = deque(A)
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    a = A.popleft()
    if 1 == a:
        dp[1] = 0
        a = A.popleft()

for i in range(2, N+1):
    if i != a:
        dp[i] = (dp[i-1] + dp[i-2]) % P
    else:
        dp[i] = 0
        if len(A):
            a = A.popleft()
print(dp[N])

Submission status: Runtime Error

Solution code:
def fact(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
    return ret

def c(n, r):
    u = fact(n)
    d = fact(n-r) * fact(r)
    return u//d

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



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

mod = 1000000007
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)

Submission status: Runtime Error

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

now = 0
ans = 1
j = 0
for i in range(M):
    if now == a[i] - 1:
       now = a[i] + 1 
    elif now == a[i]:
        ans = 0
        break
    else:
        j = (a[i] - 1) - now
        k1 = 0
        k2 = 1
        k3 = 1
        for n in range(j):
            k3 = k2
            k2 += k1
            k1 = k3
        ans *= k2
        now = a[i] + 1

j = N - now
k1 = 0
k2 = 1
k3 = 1
for n in range(j):
    k3 = k2
    k2 += k1
    k1 = k3
ans *= k2
now = a[i] + 1
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def solve(n):
  if n <= 1:
    ans = 1
  elif n == 2:
    ans = 2
  else:
    ans = solve(n-1) + solve(n-2)
  return ans

n,m=map(int, input().split())
a=[0]
ans = 1
for i in range(0,m):
  a = a+[int(input())]
  if a[i+1] - a[i] == 1:
    ans = 0
a = a + [n+1]
for i in range(0,m+1):
  ans = (ans * solve(a[i+1] - a[i] - 2)) % 1000000007
print(ans)

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

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

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(round(dd/2) + 1):
                tmp += cmb(dd - j, j)
            ans *= tmp

    print(ans%1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


q=1000000007
a=[]
if n>=3:
  for i in range(m):
    b=int(input())
    a.append(b)
    if b==1:
      dp[1]=0
      dp[2]=1
    if b==2:
      dp[2]=0

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

  for i in range(3,n+1):
    if i in a:
      continue
    else:
      dp[i]=(dp[i-1]+dp[i-2])%q
      """print("dp[i]",i,dp[i])"""
  if ans==0:
    dp[n]=ans
print(dp[n])

Submission status: Runtime Error

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

def root(i): #0からiにいく組み合わせ
    if i==0:
        return 1
    elif i==1:
        return 1
    elif i==2:
        return 2
    elif i<0:
        print(0)
        exit()
    else:
        return root(i-1)+root(i-2)

if M==0:
    print(root(N))
    exit()
#print(root(5))
#print(A)
ans=0
for i in range(M):
    if i==0:
        ans=root(A[0]-1)
    else:
        ans*=root(A[i]-A[i-1]-2)
    #print(ans)
    #print(i)
ans*=root(N-A[M-1]-1)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
dif = []
cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
if m <= 10000:
  nnn = 1000
else:
  nnn = 20000
for i in range(nnn):
  a,b = b,a+b
  ref.append(b)
ans = 1
for num in dif:
  ans *= ref[num]
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())

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
cnt[2] = 2 
for i in range(3,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
for i in range(M): 
    if i == 0:
        if A[i] != 1:
            ans*= cnt[A[i]-1]
    elif i > 0 and i < M:
        ans*=cnt[A[i] - A[i-1] - 1]

    if i == M-1:
        if A[i] != N -1:
            ans*= cnt[N - A[i]]
    
    if ans == 0:
        break
  
    ans %= amari

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
from functools import reduce
from operator import add, mul

from functools import lru_cache
@lru_cache(maxsize=None)  # メモ化したい関数の前につける
def fib(n):  # n 番目のフィボナッチ数を求める関数
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 2) + fib(n - 1)


nm = [int(i) for i in stdin.readline().rstrip().split(" ")]
a = []
for i in range(nm[1]):
    a.append(int(stdin.readline().rstrip()))
result =[]
result.append(fib(a[0]))
for i in range(nm[1]-1):
    result.append(fib(a[i+1] - a[i] - 1))
result.append(fib(nm[0] - a[nm[1]-1]))
print(reduce(mul, result) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

def dfs(n:int, heights: int, a_index:int):
    if n < heights:
        return

    if a_index <= len(a) -1 and a[a_index] == heights:
        memo[heights] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[heights] = memo[heights-1] + memo[heights -2]
        #print("13",heights)
    dfs(n,heights+1,a_index)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(n+1)
a = []
a_index = 0
for i in range(m):
    tmp = int(input())
    if i >= 1 and tmp -1 == a[len(a)-1]:
        print(0)
        sys.exit()
    else:
        a.append(tmp)
        #print(i,a)

if a[0] == 1:
    memo[1] = 0
    a_index += 1

dfs(n,2,a_index)
#print(memo)
print(memo[n] % (10**9+7))

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
a = [int(input()) for i in range(M)]
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,i-preidx-2])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    ans.append([idx,N-preidx-1])

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

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
 
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b


ans = 1
for i in range(M+1):
	if i == 0:
		ans = ans*(Fib(a[0]-(-1))%dekai)
	elif i == M:
		ans = ans*(Fib(N+1-a[M-1])%dekai)
	else:
		ans = ans*(Fib(a[i]-a[i-1])%dekai)
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(30000)

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

MOD = pow(10, 9) + 7

isOk = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        isOk = False
    
@lru_cache(maxsize = None)
def func(n):
    if n <= 0:
        return 1
    cnt = 0
    if n >= 2:
        cnt += func(n-2) % MOD
    if n >= 1:
        cnt += func(n-1) % MOD
    return cnt

if not isOk:
    print(0)
else:
    ans = 1
    s = 0
    for i in range(M+1):
        if i >= M:
            e = N
        else:
            e = a[i] - 1

        ans = ans * func(e-s) % MOD

        if i >= M:
            break

        s = a[i] + 1

    print(ans)

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, input().split())
kaidan = [1] * (n+1)
for _ in range(m):
    a = int(input())
    kaidan[a] = -1

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

ans = 1
renzoku = 0
koshou = 0
for i in range(n+2):
    if i == n+1:
        temp = fiblist[renzoku]
        ans = (ans * temp) % 1000000007
    elif kaidan[i] == 1:
        renzoku += 1
        koshou = 0
    else:
        koshou += 1
        if koshou == 2:
            print(0)
            sys.exit()
        else:
            temp = fiblist[renzoku]
            ans = (ans * temp) % 1000000007
        renzoku = 0

print(ans)

Submission status: Runtime Error

Solution code:
def howmany(z):
    if z == -1 or z == 0 or z == 1:
        return(1)
    elif z == 2:
        return(2)
    else:
        return howmany(z-1) + howmany(z-2)

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

x = 1
a = [0]*(m+2)
a[0] = -1
a[m+1] = n

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

if m == 0:
    print(howmany(n))

elif all(a[i+1]-a[i] != 1 for i in range(1,m+1)):
    for i in range(1,m+1):
        x *= howmany(a[i] - a[i-1] -2)
    x *= howmany(a[m+1]-a[m]-1)
    print(x % 1000000007)

else: print(0)

Submission status: Runtime Error

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

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

if M==0:
  print(step(N))
else:
  b = [0]*(M+1)
  b[0] = step(a[0]-1)
  if M>=2:
    for i in range(M-1):
      if a[i+1]-a[i] == 1:
        b[i+1] = 0
      else:
        b[i+1] = step(a[i+1]-a[i]-2)
  b[M] = step(N-a[M-1]-1)

answer = 1
for i in range(M+1):
  answer = answer*b[i]%1000000007
print(answer)

Submission status: Runtime Error

Solution code:
def step(n, memo={}):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    elif n in memo:
        return memo[n]%1000000007
    else:
        memo[n] = (step(n-1,memo)+step(n-2,memo))%1000000007
        return memo[n]

N, M = map(int, input().split())
a = [-1]

for m in range(M):
    a.append(int(input()))
    if a[m+1] - a[m] == 1:
        print(0)
        break
else:
    a.append(N+1)
    ans = 1
    for m in range(M+1):
        ans = (ans*(step(a[m+1]-a[m]-2)))%1000000007
    print(ans)

Submission status: Runtime Error

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

a = [int(x) for x in input()]



def solve(n,now,ls,cnt):
    if n == now:
        return cnt
    elif n-1 == now:
        return cnt
    else:
        pass

    if now+1 in ls and now+2 in ls:
        return 0
    elif   now+1 in ls:
        return solve(n,now+2,ls,cnt)
    elif   now+2 in ls:
        return solve(n,now+1,ls,cnt)
    else:
        return solve(n,now+2,ls,cnt*2)

ans = solve(n,0,a,1)

print(ans%(1000000007))

Submission status: Runtime Error

Solution code:
from math import factorial

n, m = map(int, input().split())
A = [0] * m
for i in range(m):
    A[i] = int(input())
B = []
if m > 1:
    for i in range(m - 1):
        if A[i + 1] - A[i] == 1:
            print(0)
            exit()
if m:
    B.append(A[0])
    A.append(n + 1)
    for i in range(len(A) - 2, -1, -1):
        B.append(A[i + 1] - A[i] - 1)
else:
    B.append(n + 1)
div = 1_000_000_007
ans = 1
for b in B:
    if b < 3:
        continue
    c = b - 1
    two_max = c // 2
    a = 0
    for two in range(two_max + 1):
        one = c - (2 * two)
        a += factorial(one + two) // (factorial(one) * factorial(two))
    ans *= a
    ans %= div
print(ans)

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]

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:
from math import factorial

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

def comb(n,r):
  return factorial(n) / factorial(r) / factorial(n - r)

def func(a_p,a_c):
  if a_p == a_c: return 1
  num_steps = a_c - a_p
  r = 0
  result = 0
  for n in range(num_steps,0,-1):
    result += int(comb(n,r))
    r += 1
    if n <= r: break
  return result

a_p = 0
result = 1
for i in range(M):
  a_c = int(input()) - 1
  
  if a_c + 1 == a_p: 
    result *= 0
  result *= func(a_p,a_c)
  a_p = a_c + 2
  
result *= func(a_p,N)
print(result%1000000007)

Submission status: Runtime Error

Solution code:
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
		# print(i)
		return True
	if i>N:return False
	if i in L:return False
	dfs(i+1)
	dfs(i+2)

dfs(0)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
INF = 1000000007
n,m= map(int,input().split())
a = [0]*m
for i in range(m):
    a[i] = int(input())

def step(x):
    if x < 0:
        return 0
    if x == 0:
        return 1
    if x == 1:
        return 1
    if x == 2:
        return 2
    if x >= 3:
        return step(x-1)+step(x-2)

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

ans = 1

for i in range(m+1):
    ans = ans*step(l[i])
    if ans >= INF:
        ans = ans % INF

print(ans)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
 
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b


ans = 1
for i in range(M+1):
	if i == 0:
		ans = ans*(Fib(a[0]-(-1))%dekai)
	elif i == M:
		ans = ans*(Fib(N+1-a[M-1])%dekai)
	else:
		ans = ans*(Fib(a[i]-a[i-1])%dekai
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [-1] * (n + 1)
a = []
for i in range(m):
    aa = int(input())
    a.append(aa)
    dp[aa] = 0
mod = 10 ** 9 + 7

dp[0] = 1
if a[0] != 1:
    dp[1] = 1
for i in range(1, n):
    if dp[i + 1] == -1:
        dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])

Submission status: Runtime Error

Solution code:
n , m = map(int, input().split())
a = []
p = 0
max_wid = 0
for i in range(m):
    b = int(input())
    a.append(b)
    if i > 0:
        max_wid = max(max_wid, b)
max_wid = max(max_wid, n - a[m-1])
fib = [1, 1]
for i in range(max_wid+3):
    l = len(fib)
    fib.append(fib[l-2] + fib[l-1])

ans = 1
if a[0] == 0:
    ans *= 0
else:
    ans *= fib[a[0]-1]

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

ans *= fib[n-a[m-1]-1]
ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
#print(N)
#print(M)
def root(i): #0からiにいく組み合わせ
    if i==0:
        return 1
    elif i==1:
        return 1
    elif i==2:
        return 2
    elif i<0:
        print(0)
        exit()
    else:
        return root(i-1)+root(i-2)
#print(root(5))
#print(A)
ans=0
for i in range(M):
    if i==0:
        ans=root(A[0]-1)
    else:
        ans*=root(A[i]-A[i-1]-2)
    #print(ans)
    #print(i)
ans*=root(N-A[M-1]-1)
print(ans%1000000007)

Submission status: Runtime Error

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

from functools import lru_cache

a = {-1}


@lru_cache(maxsize=None)
def solv(n):
    if n == 0:
        return 1
    count = 0
    if (n-2) not in a:
        count += solv(n-2)
    if (n-1) not in a:
        count += solv(n-1)
    return count


if __name__ == '__main__':

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

    ans = solv(n)

    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1002)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[-1]*(n+1)
print(func(n)%1000000007)

Submission status: Runtime Error

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys

WARU = 1000000007

N, M = [ int(x) for x in input().split() ]
A = {}
for i in range(M):
    A[int(input())] = 1

ans = [None for i in range(N + 1)]
ans[0] = 1
ans[1] = 1
for a in A:
    ans[a] = 0

def steps(n):
    if ans[n] is not None:
        return ans[n]
    #print ("{} : {}".format(n, steps(n - 1) + steps(n - 2)))
    ans[n] = (steps(n - 1) + steps(n - 2)) % WARU
    return ans[n]

#print(ans)
print(steps(N))

Submission status: Runtime Error

Solution code:
# 1 <= N <= 10 ** 5
# 0 <= M <= N − 1
# 1 <= a <= N - 1
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())

memo = {1: 1, 0: 1}
def fibo(n):
  if n in memo:
    return memo[n]
  else:
    num = fibo(n - 1) + fibo(n - 2)
    memo[n] = num
    return num


stairs = [False for _ in range(N + 1)]
pattern = 1
prev = 0
for _ in range(M):
  a = int(input())
  sub = a - prev - 1
  if sub == -1:
    print(0)
    break
  pattern *= fibo(sub)
  prev = a + 1
else:
  sub = N - prev
  pattern *= fibo(sub)

  print(pattern % 1000000007)