Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = []
import sys
flg = 0
for i in range(M):
    a = int(input())
    if a == 1 or a == 2:
        flg = a
    if i != 0:
        if a == A[-1] + 1:
            print(0)
            sys.exit()
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    if flg == 0:
        steps[1] = 1
        steps[2] = 2
    elif flg == 1:
        steps[2] = 1
    else:
        steps[1] = 1
    for i in range(3, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if i in A:
            steps[i] = 0
    return steps[n] % 1000000007
print(step(N))

Submission status: Runtime Error

Solution code:
inp = input().split(" ")
n,m = int(inp[0]),int(inp[1])
brokens = []
for i in range (m):
    brokens.append(int(input()))

dp = []
for i in range(n+1):
    dp.append(0)

for i in brokens:
    dp[i]= -1

if dp[1] == -1 and dp[2] == -1:
    dp[1] = 0
    dp[2] = 0
elif dp[1] == -1:
    dp[1] = 0
    dp[2] = 1
elif dp[2] == -1 :
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2


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

print(dp[n] % 1000000007)

Submission status: Runtime Error

Solution code:
import math

def c(n, r):
    u = math.factorial(n)
    d = math.factorial(n-r) * math.factorial(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:
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n, m = lmi()

l = [0] * (n+1)
l[0] = 1

a = int(input())
k = 1
for i in range(n+1):

    if i != a:
        if i == 1:
            l[i] = 1
        elif i >= 2:
            l[i] = l[i-1] + l[i-2]
            l[i] %= 1000000007
    else:
        k += 1
        if k <= m:
            a = int(input())



#print(l)
print(l[n] % 1000000007)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
memo = {}
def steps(n):
  if not(n in memo):
    if n == 0:
      memo[n] = 1
    elif n == 1:
      memo[n] = 1
    else:
      memo[n] = (steps(n-1)+steps(n-2))%MOD
  return memo[n]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
nowstep = 0
ans = 1
for a in A:
  if nowstep == a:
    ans = 0
    break
  ans = (ans * steps(a-1-nowstep))%MOD
  nowstep = a+1
ans = (ans * steps(N-nowstep))%MOD
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=4096)
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:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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)
        if d[i] == 0:
            d[i] = 1

    ans = 1
    for dd in d:
        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:
import sys
n,m= map(int, input().split())
array = list(map(int, input().split()))
if m !=1:
  for j in range(m-1):
    if array[j+1]-array[j] ==1 :
        print(0)
        sys.exit()

count = n -1 - m*3
for i in range(m):
    if array[i]==1:
        count +=1
    elif array[i]==n-1:
        count +=1

print(2**count)

Submission status: Runtime Error

Solution code:
def count_a(number,a_list):
	if number in a_list:
		return 0
	elif number ==1:
		return 1
	elif number ==2:
		return 2
	else:
		return count_a(number-1,a_list)+count_a(number-2,a_list)
		
n,m=map(int,input().split())
a_list=[]
for i in range(m):
	a_list.append(int(input()))
print(count_a(n,a_list)%1000000007)

Submission status: Runtime Error

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

N, M = (int(x) for x in input().split())
a = [-1]
for i in range(M):
    a.append(int(input()))

a.append(N+1)
ans = 1
for i in range(M+1):
    length = a[i+1] - a[i] - 1
    if length == 0:
        print(0)
        exit()
    else:
        ans *= function(length-1)

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

Submission status: Runtime Error

Solution code:
def  solve(n, total):
    cnt = 0

    if total == n:
        return 1
    else:
        if total > n:
            return 0
        else:
            cnt += solve(n, total+1)
            cnt += solve(n,total+2)

    return cnt



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

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

ans = 1

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

    if idx >= len(steps):
        ans *= solve(r-l,0)
        break


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

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
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
if N == 1:
    print(1)
    quit()

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:
n,m=map(int,input().split())
a=[]

for i in range(m):
  b=int(input())
  a.append(b)
    
def count(x):
    if x==-1:
        return 0
    elif x==0:
        return 1
    elif x in a:
        return 0
    else:
        return (count(x-2)+count(x-1))%1000000007
    
print(count(n))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    a = im.input2D(h=m)
    MOD = 1000000007
    # Logic ############################################################################################################
    idx = 0
    total = 1
    for ai in a:
        ai = ai[0]
        if (ai - idx) == 1 and idx != 0:
            print(0)
            return
        total *= fibonacci(ai - idx)
        idx = ai+1
    total *= fibonacci(n + 1 - idx)
    # Output ###########################################################################################################
    print(total % MOD)
    # Return ###########################################################################################################
    return

def fibonacci(n):
    fib = (pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n)) / sqrt(5)
    return int(fib)

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split(' ')]
brokens = []
for _ in range(M):
  brokens.append(int(input()))
  
memo = {}
def count_climbable(a, end, count):
  if a in memo:
    return memo[a]
  elif a is end:
    return 1
  elif a > end:
    return 0
  elif a in brokens:
    return 0
  else:
    memo[a] = count_climbable(a+1, end, count)+count_climbable(a+2, end, count)
    return memo[a]
  
print(count_climbable(0, N, 0) % 1000000007)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = sorted(list(set(a)))
dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
n,m,*a=map(int,open(0).read().split())
s=0
c=[0]*(1+len(a))
p=1
for j,e in enumerate(a+[n+1]):
  d=e-1-s
  m=d//2
  for i in range(m+1):
    l=d-i*2
    c[j]+=int(factorial(l+i)/factorial(l)/factorial(i))
  s=e+1
  p*=c[j]
print(p%1000000007)

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
mod = 1000000007
n,m = map(int,input().split(' '))
a0 = -1
b = []
for q in range(m):
    a1 = int(input())
    if a1 == a0:
        continue
    else:
        b.append(a1-a0-2)
        a0 = a1
b.append(n-a1-1)
ans = 1
for b0 in b:
    if b0 == -1:
        ans = 0
        break
    i = 0
    ans0 = 0
    while i <= b0//2:
        ans0 += cmb(b0-i,i)
        i += 1
    ans *= ans0
    ans = ans%mod
print(ans%mod)

Submission status: Runtime Error

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

li = [0]*10**5
lia = [-1]
ans = 1
mod = 1000000007

for i in range(n):
    if i == 0:
        li[i] = 1
    elif i == 1:
        li[i] = 1
    else:
        li[i] = li[i-1] + li[i-2]

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        if lia[i] == 0 or lia[i+1] == n:
            pass
        else:
            ans = 0
    ans %= mod

print(ans%mod)

Submission status: Runtime Error

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

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:
# 1 <= N <= 10 ** 5
# 0 <= M <= N − 1
# 1 <= a <= N - 1
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)

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 if not 1 in A else 0

def steps(n):
    if ans[n] is not None:
        return ans[n]
    if n in A:
        ans[n] = 0
        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:
import sys
N, M = map(int, input().split())

dp_f = [None] * 10**5
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]

if M == 0:
    print(f(N))
    sys.exit(0)

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

S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])

m = 1
for s in S:
    m *= f(s)
    m %= 1000000007

print(m)

Submission status: Runtime Error

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

a=[1,1]
for i in range(2,10001):
    a.append((a[i-1]+a[i-2])%1000000007)

bad=[]
for i in range(m):
    bad.append(int(input()))
num=[]
before=0
bad_flag=0

if m!=0:
    for i in range(len(bad)):
        nxt=bad[i]-before-1
        if nxt==-1:
            bad_flag=1
            break
        num.append(nxt)
        before=bad[i]+1
    num.append(n-bad[len(bad)-1]-1)
else:
    num.append(n)
if bad_flag:
    print(0)
else:
    ans=0
    last=1
    for i in num:
        ans=a[i]*last
        last=ans%1000000007
    print(last)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, raw_input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(raw_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

print(calc_ans(0) % 1000000007)

Submission status: Runtime Error

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

dan=[]

for i in range(m):
    b=list(map(int, input().split()))
    dan.append(b[0])

fib=[0 for i in range(n+2)]
fib[1]=1
fib[2]=2

for ii in range(n-1):
    i=ii+3
    fib[i]=(fib[i-1]+fib[i-2])%1000000007
    
#print(fib,dan)

eachans=[]

if(m==0):
    print(fib[n])

if(m>=1):
    if(dan[0]!=1):
        eachans.append(fib[dan[0]-1])

for i in range(m-1):
    if(dan[i+1]-dan[i]-2 == 0):
        eachans.append(1)
    elif(dan[i+1]-dan[i]-2 == -1):
        eachans.append(0)
    else:
        eachans.append(fib[dan[i+1]-dan[i]-2])
    #print(dan[i+1]-dan[i]-1)

if(m>=1):
    if(dan[-1]!=n-1):
        eachans.append(fib[n-dan[-1]-1])
    
if(m>=1):
    #print(eachans)
    ans=1
    for i in range(len(eachans)):
        ans = ans*eachans[i]%1000000007

print(ans)

Submission status: Runtime Error

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

def factorial(x):
  if x == 0:
    return 1
  else:
    return x * factorial(x-1)

def C(x,y):
    return factorial(x)//(factorial(x-y)*factorial(y))

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

b = []
for i in range(m+1):
    b.append(a[i+1]-a[i]-2)

ans = 1
if -1 in b:
    print(0)
else:
    for i in b:
        ans *= f(i)
        ans %= 1000000007
    print(ans%1000000007)

Submission status: Runtime Error

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

@lru_cache(maxsize=4096)
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:
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = list(set(a))
dif = [a[0]-1]
dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
dif.extend([N-a[-1]-1])
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
c[2] = 2
ans = 1
a = []
for i in range(3,N+1):
    c[i] = c[i-1]+c[i-2]
for i in range(M):
    ai = int(input())
    a.append(ai)
for i in range(1,M-1):
    if a[i+1]-a[i] == 1:
        print(0)
        exit()
for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        ans *= c[a[i+1]-a[i]-2]
        ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def stairs_count(now, goal, memo):
    if memo[now] is not None:
        return memo[now]

    step1 = 0
    step2 = 0

    # step1
    if now + 1 == goal:
        step1 = 1
    else:
        step1 = stairs_count(now+1, goal, memo)

    # step2
    if now + 2 > goal:
        step2 = 0
    elif now + 2 == goal:
        step2 = 1
    else:
        step2 = stairs_count(now+2, goal, memo)

    memo[now] = step1 + step2
    return memo[now]


n, m  = map(int, input().split())
memo = [None for i in range(n)]
for _ in range(m):
    a = int(input())
    memo[a] = 0

root = stairs_count(0, n, memo)
print(root % 1000000007)

Submission status: Runtime Error

Solution code:
def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()

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 = []
now_step = -1
for i in range(len(list_a)):
    steps.append(list_a[i]-now_step-2)
    now_step = list_a[i]
steps.append(n-now_step-1)

if steps[0] == 0:
    steps[0] = 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)**v
    
if steps.count(0) == 0:
    print(ans% 1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    x=int(input())
    if a:
        if x!=a[-1]:
            a.append(x)
    else:
        a.append(x)
count=[0]*(n+2)
count[1]=2
count[0]=1
i=0
s=a.pop(0)
if s==1:
    count[1]=1
    count[0]=0
    if a:
        s=a.pop(0)
if s==2:
    count[1]=0
    if a:
        s=a.pop(0)

while i<n:        
    if (i+2==s-1):
        i=i+1
        if a:
            s=a.pop(0)
    else:
        count[i+2]=(count[i]+count[i+1])%1000000007
        i=i+1
#print(count)
print(count[n-1])

Submission status: Runtime Error

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def fib_memo(n):
    memo = [0] * (n+1)
    memo[0] = 1
    memo[1] = 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo

def main():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    D = [0] * (M+1)
    if M == 0:
        D[0] = N
    else:
        D[0] = A[0] - 1
        for i in range(1, M):
            t = A[i] - A[i-1] - 2
            if t <= 1:
                print(0)
                return
            D[i] = t
        D[M] = N - A[M-1] - 1
    n = 1
    memo = fib_memo(max(D))
    for d in D:
        n = (n * memo[d]) % MOD
    print(n)

main()

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
DIV = 10**9+7

def main():
    B = [0]*(M+1)
    for i in range(M+1):
        if i==0:
            B[i] = A[i]-1
        elif i==M:
            B[i] = N-A[i-1]-1
        else:
            B[i] = A[i] - A[i-1] - 2
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i in range(max_B+1):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        if ans > DIV:
            ans %= DIV
    return ans

print(main())

Submission status: Runtime Error

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

s = [0] * (n + 1)
s[-1] = 1
for _ in range(m):
    a = int(input())
    s[a] = None

if s[0] is None and s[1] is None:
    print(0)
    exit()

for i in range(n - 1, -1, -1):
    if s[i] is None:
        continue
    if i + 1 < len(s) and s[i + 1] is not None:
        s[i] += s[i + 1]
    if i + 2 < len(s) and s[i + 2] is not None:
        s[i] += s[i + 2]

print(s[0] % 1_000_000_007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
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 i in 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:
from collections import deque
N, M = map(int, input().split())
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:
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]))%INF
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[m+1] = n

a[1] = int(input())
x *= howmany(a[1]-1)

for i in range(2,m+1):
    a[i] = int(input())
    x *= howmany(a[i] - a[i-1] -2)

x *= howmany(a[m+1]-a[m] -1)

if  all(a[i+1]-a[i] != 1 for i in range(1,m+1)):
    print(x % 1000000007)
else: print(0)

Submission status: Runtime Error

Solution code:
from sys import stdin
data = stdin.readline().split()
N, M = int(data[0]), int(data[1])
a = [None] * M
for i in range(M):
    a[i] = int(stdin.readline().rstrip())
    if i > 0 and a[i] - a[i-1] == 1:
        print(0)
        exit()
fib = [None] * N
if not 1 in a:
    fib[0] = 1
    if not 2 in a:
        fib[1] = 2
    else:
        fib[1] = 0
else:
    fib[0] = 0
    fib[1] = 1
for i in range(2,N):
    if not i + 1 in a:
        fib[i] = fib[i-1] + fib[i-2]
    else:
        fib[i] = 0
# print(fib)
print(fib[N-1] % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
  a, b = 1, 1
  if n == 0:
  	return a
  elif n == 1:
    return b
  else:
    for i in range(n-2):
      a, b = b, a + b
    return b

mod = 1000000007
def mul(a, b):
  return ((a % mod) * (b % mod)) % mod

def power(x, y):
  if   y == 0     : return 1
  elif y == 1     : return x % mod
  elif y % 2 == 0 : return power(x, y/2)**2 % mod
  else            : return power(x, y/2)**2 * x % mod

def div(a, b):
  return mul(a, power(b, mod-2))
  
N, M = map(int, input().split())
a = int(input())
ret = mul(1, Fib(a))
pre_a = a

for i in range(M-1):
  a = int(input())
  if a - pre_a <= 1:
    ret = 0
    break
  else:
    num_step = a - pre_a - 1
    ret = mul(ret, Fib(num_step))
  pre_a = a
    
num_step = N - a
ret = mul(ret, Fib(num_step))
print(ret)

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 if not 1 in A else 0

def steps(n):
    if ans[n] is not None:
        return ans[n]
    if n in A:
        return 0
    #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:
n, m = map(int, input().split())
S = []
tmp = int(input())
s = tmp + 1
for _ in range(m-1):
  a = int(input())
  S.append(a-tmp)
  tmp = a
g = n-tmp+1

fib = [1 for _ in range(n+1)]
for i in range(2, n-1):
  fib[i+2] = fib[i] + fib[i+1]
total = fib[s]*fib[g]

fib[1] = 0

for x in S:
  total *= fib[x]
  
print(s, S, g)
print(total%1000000007)