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:
def fib_memo(n):
    """メモ化フィボナッチ"""
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, array)
print(Ans % 1000000007)

Submission status: Runtime Error

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

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



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:
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 / 5**0.5 + 0.5) % MOD
    return int(f)


kotae = 1

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

N,M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)]

m = 10**9+7

memo = [1]*(N+1)
for i in range(3,N+1):
    memo[i] = memo[i-1] + memo[i-2]

A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    print(ans)
    if p+1 == A[i]:
        print(0)
        exit()
    else:
        ans *= memo[A[i]-p-1]
        ans %= m
    p = A[i]

print(ans)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(100000)

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

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
fib = [None] * N
for i in range(M):
    a[i] = int(stdin.readline().rstrip())
    fib[a[i] - 1] = 0
    if i > 0 and a[i] - a[i-1] == 1:
        print(0)
        exit()
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 fib[i] == 0:
        continue
    else:
        fib[i] = fib[i-1] + fib[i-2]
# print(fib)
print(fib[N-1] % 1000000007)

Submission status: Runtime Error

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
af=0
for i in range(m):
    a.append(int(input()))
if len(a)>0:
    a.sort()
    af=1
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if af==1 and i==a[0]:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

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 < 2:
            continue
        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]%q+dp[i-2]%q)%q
      """print("dp[i]",i,dp[i])"""
  if ans==0:
    dp[n]=ans
print(dp[n])

Submission status: Runtime Error

Solution code:
import sys
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:
mod = 1000000007
dp=[]
def countways(n,broken,index):
	global dp,mod
	if(dp[index]!=-1):
		return dp[index]

	ways = 0
	if(index+1<=n and broken[index+1]==0):
		ways+=countways(n,broken,index+1)
	if(index+2<=n and broken[index+2]==0):
		ways+=countways(n,broken,index+2)
	dp[index]=(ways%mod)
	return dp[index]

n,m = list(map(int,input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(input())]=1
print(countways(n,broken,0)%mod)

Submission status: Runtime Error

Solution code:
import math

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
b = []
for i in range(m):
    if i == 0:
        b.append(a[i] - 1)
    else:
        b.append(a[i] - a[i - 1] - 2)
b.append(n - a[-1] - 1)
if -1 in b:
    print(0)
    exit()
c = set(b)
d = {}
for i in c:
    k = 0
    s = 1
    while i - k > k:
        s += nCr(i - k, k)
        k += 1
    d[i] = s
ans = 1
for i in b:
    ans *= d[i] % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

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

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:
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
for i in range(1000):
  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:
fib=[0,1]
for i in range(9999):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[0]
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()
    
  ans=ans*max(1,fib[hoge[i+1]-hoge[i]-1])
  ans=ans%1000000007
  
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
if N == 1:
    print(1)
    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:
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):
    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:
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 / 5**0.5 + 0.5
    return int(f)


kotae = 1

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

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
dp[3] = 2
for i in range(3,N+5):
    dp[i+1] = dp[i] + dp[i-1]
    dp[i+1] %= mod
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= mod
print(ans)

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 = list(map(int, sys.stdin.readlines()))

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:
def get_num_path(index):
    if index < 0:
        return 0
    if num_path[index] != -1:
        return num_path[index]
    ans = 0
    if can_step[index - 1]:
        ans += get_num_path(index - 1)
    if can_step[index - 2]:
        ans += get_num_path(index - 2)
    num_path[index] = ans
    return ans


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

am = [int(a) for a in am]
num_path = [-1] * (n + 1)
num_path[0] = 1
num_path[1] = 1
can_step = [False if i in am else True for i in range(n+1)]

ans = get_num_path(n)
ans %= 1000000007
print(ans)

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))
if len(a)>0:
    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])
else:
    dif = [N]
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 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())
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 = [int(i) for i in input().split()]


def countPattern(s, cnt):
    if s > 1:
        cnt = countPattern(s-2, cnt)
        cnt = countPattern(s-1, cnt)
        return cnt
    else:
        return cnt + 1


ans = 1
a_pre = -1
for mi in range(m):
    a = int(input())
    if a == a_pre:
        break
    elif a == a_pre + 1:
        ans = 0
    ans = ans * countPattern(a-a_pre-2, 0) % 1000000007
    a_pre = a

a = n + 1
ans = ans * countPattern(a - a_pre - 2, 0) % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.sort()
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if i==a[0]:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

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 math

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())
li = [int(input()) for i in range(m)]
p = 1000000007
ans = 0

steps = [0]*(n+1)
steps[1] = 1
steps[2] = 2
for i in range(3,n+1):
  steps[i] = (steps[i-1] + steps[i-2])%p

if li[0] == 1:
  ans += 1
else:
  ans += steps[li[0]-1]%p

for i in range(m-1):
  ans *= steps[li[i+1]-li[i]-2]
  ans %= p

if li[m-1] == n-1: 
  print(ans)
else:
  print((ans*steps[n-li[m-1]-1])%p)

Submission status: Runtime Error

Solution code:
def up_stairs(N, a, now):
  
  if now == N or (now + 1) == N:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  if (now + 1) in a:
    return up_stairs(N, a, now + 2)
  elif (now + 2) in a:
    return up_stairs(N, a, now + 1)
  else:
    return up_stairs(N, a, now + 1) + up_stairs(N, a, now + 2)


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

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

print(int(up_stairs(N, a, 0) % 1000000007))

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)
        return memo[n]%1000000007

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:
# 1 <= N <= 10 ** 5
# 0 <= M <= N − 1
# 1 <= a <= N - 1
import sys
sys.setrecursionlimit(10000)
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:
import sys

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

sys.setrecursionlimit(N * 2)

Z = 1000000007

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


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


def d(n):
    if B[n] != -1:
        return B[n]

    if n in A or n < 0:
        return 0
    if n <= 2:
        return n

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


print(d(N))

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb
N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N)
if not 1 in A:
    A.append(0)
    A.sort()
count=1
for m in range(len(A)-1):

    count*=sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])])
    #print(sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])]),count)
print(count%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = [int(input())-1 for i in range(m)]
dp = [0]*n
if 0 in a:
    if 1 in a:
        print(0)
        exit()
    else:
        dp[0]=0
        dp[1]=1
else:
    if 1 in a:
        dp[0]=1
        dp[1]=0
    else:
        dp[0]=1
        dp[1]=2
for i in range(2,n):
    if i-1 in a and i-2 in a:
        print(0)
        exit()
    elif i-1 in a:
        dp[i]=dp[i-2]
    elif i-2 in a:
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+dp[i-2]
        if dp[i]>10**9+7:
            dp[i]=dp[i]%(10**9+7)
print(dp[n-1])

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())

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

print(stair(n))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [-1] * (n + 1)
a = []
for i in range(m):
    aa = int(input())
    if a:
        if a[-1] == aa - 1:
            print(0)
            exit()
    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 = [0]*M
for i in range(M):
    a[i] = int(input())

ans = int(1)

A = [0]*(M+1)
A[0] = a[0]-1
A[M] = N - a[M-1]-1
for i in range(M-1):
    A[i+1] = a[i+1] - a[i]- 2
    if A[i+1]==-1:
        ans = 0
        print(ans)
        exit()

SA =[0]*N
SA[0] = int(1)
SA[1] = int(1)
for i in range(N-2):
    SA[i+2] = SA[i+1] + SA[i]

for i in range(M+1):
    ans *= SA[A[i]]
    ans = ans%1000000007


print(int(ans))

Submission status: Runtime Error

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

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



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] % 1000000007)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections


def fib(n):
    return int((1 / math.sqrt(5)) * (math.pow((1 + math.sqrt(5)) / 2, n) - math.pow((1 - math.sqrt(5)) / 2, n)))


# for i in range(10):
#     print(fib(i))

N, M = map(int, sys.stdin.readline().rstrip().split(" "))
As = []
for i in range(M):
    a, = map(int, sys.stdin.readline().rstrip().split(" "))
    As.append(a)
As.append(N+1)
result = 1
current = 0
for a in As:
    diff = a - current - 1
    if diff == -1:
        print(0)
        exit(0)
    # 1: 1
    # 2: 2
    # 3: 3C0 + 2C1 = 3
    # 4: (1,1,1,1) (1,1,2) (1, 2, 1) (2, 1, 1), (2, 2): 4C4 + 3C1 + 2C2 = 1+ 3 + 1 = 5
    # 5: 5C0 + 4C1 + 3C2 = 1 + 4 + 3 = 8
    # 6: 6C0 + 5C1 + 4C2 + 3C3 = 1+5+6+1 = 13
    # 7: 7C0 + 6C1 + 5C2 + 4C3 = 1+6+10+4 = 21
    # print(current, a, fib(diff+1))
    result *= fib(diff+1)
    result %= 1000000007
    # print("res", result)
    current = a + 1
print(result)
exit(0)

Submission status: Runtime Error

Solution code:
mod = 1000000007
dp=[]
def countways(n,broken,index):
	global dp
	if(dp[index]!=-1):
		return dp[index]

	ways = 0
	if(index+1<=n and broken[index+1]==0):
		ways+=countways(n,broken,index+1)
	if(index+2<=n and broken[index+2]==0):
		ways+=countways(n,broken,index+2)
	dp[index]=(ways%mod)
	return dp[index]

n,m = list(map(int,input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(input())]=1
print(countways(n,broken,0)%mod)

Submission status: Runtime Error

Solution code:
from scipy.special import perm, comb
N,M=list(map(int,input().split()))
A=[int(input()) for i in range(M)]
A.append(N)
if not 1 in A:
    A.append(0)
    A.sort()
count=1
for m in range(len(A)-1):

    count*=sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])])
    print(sum([comb((A[m+1]-1)-A[m]-i,i,exact=True) for i in range((A[m+1]-1)-A[m])]),count)
print(count%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
l,a,b,m = map(int,input().split())
x = []
for i in range(l):
    x.append(a+b*i)
a = "".join(map(str,x))
print(np.mod(int(a), m))

Submission status: Runtime Error

Solution code:
def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    mems = [False] * (N+1)

    def rec(target):
        if target in As:
            return 0
        
        if target == 1:
            return 1
        
        if target == 2:
            return 2 if 1 not in As else 1

        if not mems[target]:
            one = rec(target-1)
            two = rec(target-2)
            mems[target] = one + two
        
        return mems[target]
    
    print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

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

import sys
imput =sys.stdin.readline

p = 10**9 + 7

N,M =map(int,input().split())
lis = [0]*N

for _ in range(M):
    i = int(input())-1
    lis[i] = -1


if lis[0]!=-1:
    lis[0] =1
if lis[1]!=-1:
    lis[1] =1 + max(0,lis[0])

for i in range(N-2):
    i += 2
    if lis[i]!=-1:
        lis[i]= (max(0,lis[i-1])+max(0,lis[i-2]))%p

print(lis[-1])

Submission status: Runtime Error

Solution code:
def up_stairs(N, a, now):
  
  if now == N or (now + 1) == N:
    return 1
  if (now + 2) == N and (now + 1) not in a:
    return 1
  if now > N:
    return 0
  if (now in a):
    return 0
  
  if (now + 1) in a:
    return up_stairs(N, a, now + 2)
  elif (now + 2) in a:
    return up_stairs(N, a, now + 1)
  else:
    return up_stairs(N, a, now + 1) + up_stairs(N, a, now + 2)


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

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

print(int(up_stairs(N, a, 0) % 1000000007))

Submission status: Runtime Error

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

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

import sys
sys.setrecursionlimit(100000)

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

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]
for i in range(0,m):
  a = a+[int(input())]
  if a[i+1] - a[i] == 0:
    print(0)
    exit
a = a + [n+1]
ans = 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:
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])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append(fib[-1] + fib[-2])
  
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1]
  
  print(ans % MOD)

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [0] * (n + 1)
m = int(input())

dp[0] = 1
dp[1] = 1

for i in range(m):
    a = int(input())
    dp[a] = -1

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

print(dp[len(dp)-1] % 1000000007)

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 a[0] == 0:
  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 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:
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(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)