Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * (num + 2)
    pattern[0] = 0
    for i in range(1, num + 2):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern

def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    stepsList[0] = a[0]
    for j in range(1, M):
        stepsList[j] = a[j] - a[j - 1] - 1
        if stepsList[j] == 0:
            return 0
    stepsList[M] = N - a[M - 1]
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    # print("#", pattern)
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]
        else:
            total = (total * pattern[stepsList[k]]) % MOD
        # print("##", k, stepsList[k], pattern[stepsList[k]], total)

    return total


ans = solve()
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
out=[]
for i in range(m):
  out.append(int(input())
from functools import lru_cache

@lru_cache(maxsize=10**5)
def fib_memoized(n):
    if n < 2:
        return n
    elif n in out:
        return 0
    else:
        return fib(n - 1) + fib(n - 2)
print(fib_memorized(n))

Submission status: Runtime Error

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

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


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if N == 0 :
    flag = False

fib = [1] * (N) # フィボナッチ数列
for i in range(2,N) :
    fib[i] = fib[i-1] + fib[i-2]

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

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

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

Submission status: Runtime Error

Solution code:
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

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

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * N # フィボナッチ数列
for i in range(2,N) :
    fib[i] = fib[i-1] + fib[i-2]

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

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[-1]*(n+1)
for i in range(m):
    idx=int(input())
    l[idx]=0
mod=10**9+7
if l[1]==-1:
    if l[2]==-1:
        l[1]=1;l[2]=2
    else:
        l[1]==1
else:
    if l[2]==-1:
        l[2]=1

for i in range(3,n+1):
    if l[i]==-1:
        l[i]=(l[i-1]+l[i-2])%mod
    else:
        continue
print(l[-1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(maxsize=1000)
def fib(n):
	if n < 2:
		return n
	else:
		return fib(n - 1) + fib(n - 2)



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

a.append(n)

b = []
for i in range(n+1):
	b.append(fib(i))
	
c = []
#if a[1] == 0:
	#c.append(1)
#else:
	#c.append(b[a[1] - a[0] ])
	
	
i = 0
while i <= m + 1:
	if a[i + 1] - a[i] - 2 >= 0:
		c.append(b[a[i + 1] - a[i]  - 2])
		i += 1
	#elif a[i + 1] - a[i] - 2 == 0:
		#c.append(1)
	else:
		c.append(0)
		break
#print(c)
d = c[0] 
i = 1
#print(d)
while i < len(c):
	d = d * c[i]
	i += 1

e = 1000000007
print(d % e)
#print(b[0])

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
a = [-1]
 
MAX = 100000
MOD = 1000000007
fac = [1 for i in range(MAX)]
finv = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
 
def COM(n , r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r]* finv[n-r]%MOD)%MOD
 
for mi in range(m):
    a.append(int(input()))
a.append(n+1)
 
ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += COM(k-i, i)
    ans = ans * cnt % 1000000007
    if ans == 0:
        break
 
print(int(ans))

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:
from functools import lru_cache
2.@lru_cache(maxsize=1000)
3.def fib(n):
4.    if n < 2:
5.        return n
6.    else:
7.        return fib(n - 1) + fib(n - 2)
8. 
9.n,m = map(int,input().split())
10.a = []
11.a.append(0)
12.for i in range(m):
13.    b = int(input())
14.    b -= 1
15.    a.append(b)
16.a.append(n)
17.b = []
18. 
19.for i in range(n):
20.    b.append(fib(i))
21. 
22.c = []
23.#if a[1] == 0:
24.    #c.append(1)
25.#else:
26.    #c.append(b[a[1] - a[0] ])
27.i = 0
28.while i <= m:
29.    #if a[i + 1] - a[i] - 2 >= 0:
30.    c.append(b[a[i + 1] - a[i]  - 2])
31.    i += 1
32.    #elif a[i + 1] - a[i] - 2 == 0:
33.        #c.append(1)
34.    #else:
35.        #c.append(0)
36.        #break
37.#print(c)
38.d = c[0] 
39.i = 1
40.#print(d)
41.while i < len(c):
42.    d = d * c[i]
43.    i += 1
44.e = 1000000007
45.print(d % e)
46.#print(b[0])

Submission status: Runtime Error

Solution code:
nm=list(map(int,input().split()))
n=nm[0]
m=nm[1]

inp=[]
for inpset in range(m):
    inp.append(int(input()))
    

dis=[max(inp[0],1)]
p=0
for i in inp[:-1]:
    dis.append(inp[p+1]-inp[p]-1)
    p+=1
dis.append(max(n-inp[-1],1))
#print (dis)

import math

def kaijo(x):
    ans=(math(100000)%1000000007)
    return ans

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%1000000007

def counting(x):
    if x==1:
        return 1
    else:
        
        res=0
        for a in range(x-1):
            if x-1-a>=a:
                res+=combinations_count(x-1-a,a)
                # print(x-1-a,a)
                res=res%1000000007
            else:
                break
        return res

if 0 in dis:
    print(0)
else:
    ans=1
    dis.sort()
    for d in dis:
        ans*=counting(d)
        ans=ans%1000000007
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
S = [True]*(N+1)
for _ in range(M):
  a = input()
  S[a] = False
T = [0]*(N+1)
T[0] = 1
T[1] = 1 if S[1] else 0
for i in range(2, N+1):
  if S[i]:
    T[i] = (T[i-1]+T[i-2])%1000000007
print(T[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
#a = [0 for _ in range(N + 1)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
def fib(n) :
    if n==1 :
        return 1
    elif n==0 :
        return 1
    else :
        return fib(n-1) + fib(n-2)
a=[]
b=1

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

def rest(num) :
    return num % 1000000007
c=0
if b==0 :
    print(c)
else :
    for i in range(M+1):
        if i == 0 == M :
            c += rest(fib(N))
        elif i == 0:
            c += rest(fib(a[i]-1))
        elif i == M:
            c = rest(c * fib(N-a[i-1]-1))
        else :
            c = rest(c * fib(a[i]-a[i-1]-2))
    print(c)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [0 for _ in range(N)]

# 初期化する
if 0 not in broken_stairs:
    dp[0] = 1
if 1 not in broken_stairs:
    dp[1] = 1
if 2 not in broken_stairs:
    dp[2] = 1

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if i not in broken_stairs:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(int(dp[-1] % MOD))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in M:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[0]*(N+1)
    memo[0]=1
    ban=[False]*(N+1)
    for a in M:
        ban[a]=True
    mod=1000000007
    print(ban)
    for a in range(1,N+1):
        if ban[a]:
            print("ban")
            memo[a]=0
        else:
            if a>1:
                memo[a]=(memo[a-1]+memo[a-2])%mod
            else:
                memo[a]=1



    print(memo[-1]%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#


main()

Submission status: Runtime Error

Solution code:
nm = [int(s) for s in input().split()]


def fib(n) :
    if n==1 :
        return 1
    elif n==0 :
        return 1
    else :
        return fib(n-1) + fib(n-2)
a=[]
b=1
for i in range(nm[1]):
    a.append(int(input()))
    if a[i]-a[i-1] == 1 :
        b=0

def rest(num) :
    return num % 1000000007
c=0
if b==0 :
    print(c)
else :
    for i in range(nm[1]+1):
        if i == 0:
            c += rest(fib(a[i]-1))
        elif i == nm[1]:
            c = rest(c * fib(nm[0]-a[i-1]-1))
        else :
            c = rest(c * fib(a[i]-a[i-1]-2))
    print(c)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  if n in a:
    return 0
  elif n in (0, 1):
    return 1
  else:
    return (comb(n-1) + comb(n-2))%(10**9 + 7)

print(comb(n)%(10**9 + 7))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
bre = []
A = [1] * 10000
A[0] = 0
for i in range(M):
    a = int(input())
    A[a+1] = 0
#print(bre)
for i in range(2, N+2):
    if A[i] == 0:
        continue
    A[i] = A[i-1]+ A[i-2]
    A[i] = A[i] % 1000000007
    #print(A)
print(A[N+1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  if n in a:
    return 0
  elif n in (0, 1):
    return 1
  else:
    return (comb(n-1) + comb(n-2))

print(comb(n)%(10**9 + 7))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  if n in a:
    return 0
  if 1 not in a and n == 1:
    return 0
  elif n in (0, 1):
    return 1
  else:
    return (comb(n-1) + comb(n-2))

print(comb(n)%(10**9 + 7))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0)%mod)
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=dp(index+1)+dp(index+2)
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)%mod+dp(index+2)%mod)%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=1000000007
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    print(mod)
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
lis=list(map(int,input().split()))
alist=[]
for i in range(lis[1]):
    alist.append(int(input()))
flag=0
ans=0
steps=[0]*(lis[0]+1)
if 1 in alist:
    steps[1]=0
    steps[2]=1
elif 2 in alist:
    steps[1]=1
    steps[2]=0
else:
    steps[1]=1
    steps[2]=2
for i in range(3,lis[0]+1):
    if i not in alist:
        steps[i]=(steps[i-1]+steps[i-2])%((10**9)+7)
ans=steps[-1]

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=10**9+7+1
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    global N,M,A,mod,memo
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=10**9+7
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    global N,M,A,mod,memo
    if(index>N):return 0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=10**9+7
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    global N,M,A,mod,memo
    if(index>N):memo[index]=0
    if(index==N):memo[index]=1
    if(A.count(index)>0):memo[index]=0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
 
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
 
def SI(): return input()
 
 
MOD = 1000000007
 
 
def comb(a, b):
    ans = 1
    for i in range(1, min(a-b, b)+1):
        ans *= a - i + 1
        ans //= i
        ans = ans % MOD
    return ans
 
 
def calc(N):
    r = 1
    for b in range(N//2):
        a = N - b*2
        r += comb(a+b, b)
        r %= MOD
    return r
 
 
def main():
    N, M = LI()
    now = 0
    ans = 1
    for _ in range(M):
        a = int(input())
        if a == now-1:
            continue
        if a == now:
            print(0)
            return
        ans = (ans*calc(a-now-1)) % MOD
        now = a+1
    ans = (ans*calc(N-now)) % MOD
    print(ans)
 
 
main()
import sys
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


MOD = 1000000007


def comb(a, b):
    ans = 1
    for i in range(1, min(a-b, b)+1):
        ans *= a - i + 1
        ans //= i
        ans = ans % MOD
    return ans


def calc(N):
    r = 1
    for b in range(N//2):
        a = N - b*2
        r += comb(a+b, b)
        r %= MOD
    return r


def main():
    N, M = LI()
    now = 0
    ans = 1
    for _ in range(M):
        a = int(input())
        if a == now-1:
            continue
        if a == now:
            print(0)
            return
        ans = (ans*calc(a-now-1)) % MOD
        now = a+1
    ans = (ans*calc(N-now)) % MOD
    print(ans)


main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import os
import time
import re
import math


def main():
    global N,M,A,mod,memo
    N,M=map(int,input().split())
    A=[int(input()) for  a in range(M)] #a (1段~N-1段)
    start=time.time();#
    memo=[-1]*(N+1)
    
    mod=10**9+7
    print(dp(0))
    #print("{}ms".format(math.floor(time.time()*1000-start*1000)))#

def dp(index):
    global N,M,A,mod,memo
    if(index>N):return 0
    if(index==N):return 1
    if(A.count(index)>0):return 0
    if memo[index]==-1:
        memo[index]=(dp(index+1)+dp(index+2))%mod
    return memo[index]

main()

Submission status: Runtime Error

Solution code:
def fib(n):
    if n == 0: 
        return 0

    if n == 1: 
        return 1

    def matmul(M1, M2):
        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        return [[a11, a12], [a21, a22]]

    def matPower(mat, p):
        if p == 1: 
            return mat

        m2 = matPower(mat, p//2)
        if p % 2 == 0:
            return matmul(m2, m2)
        else: 
            return matmul(matmul(m2, m2),mat)

    Q = [[1,1],[1,0]]

    q_final = matPower(Q, n-1)
    return q_final[0][0]

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

result = 1

for i in range(1, M):
    if(V[i]-V[i-1]==1):
        result = 0

result *= fib(V[0])

for x in range(1, M):
    result *= fib(V[x]-V[x-1]-1)

if(V[M-1]!=N):
    result *= fib(N-V[M-1])

print(result%1000000007)

Submission status: Runtime Error

Solution code:
lis=list(map(int,input().split()))
alist=[-1]
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)
flag=0
ans=0
for i in range(lis[1]):
    if alist[i+1]-alist[i]==1:
        flag=1
        break
if flag==0:
    steps=[0]*(lis[0]+1)
    if 1 in alist:
        steps[1]=0
        steps[2]=1
    elif 2 in alist:
        steps[1]=1
        steps[2]=1
    else:
        steps[1]=1
        steps[2]=2
    for i in range(3,lis[0]+1):
        if i in alist:
            steps[i]=steps[i-1]
            flag=2
        elif flag==2:
            steps[i]=steps[i-1]
            flag=3
        elif flag==3:
            steps[i]=steps[i-1]
            flag=0
        else:
            steps[i]=(steps[i-1]+steps[i-2])%((10**9)+7)
    ans=steps[-1]

print(ans)

Submission status: Runtime Error

Solution code:
mod=10**9+7

de={}
def stairs(N,M,a):
    for i in range(M):
        if N==a[i]:
            return 0
    if N==0:
        return 1
    if N==1:
        return 1
    if N in de: return de[N]
    de[N]=(stairs(N-1,M,a)+stairs(N-2,M,a))%mod
    return de[N]

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

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

print(stairs(N,M,a))

Submission status: Runtime Error

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

dev = 100000007
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1

fall = [1 for _ in range(N+1)]

for i in range(M):
    fall[a[i]] = 0

for i in range(1,N):
    dp[i+1] = dp[i]*fall[i] + dp[i-1]*fall[i-1]
    dp[i+1] %= dev

print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * N
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

for i in range(N-2, -1, -1):
    if (i in A) == False:
        dp[i] = dp[i + 1] + dp[i + 2] 

print(dp[0] % mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
  
@lru_cache(maxsize=100000)
def comb(n):
  for i in a:
    if n == i:
      return 0
  if a.count(1) == 0 and n == 1:
    return 1
  elif a.count(1) != 0 and n == 1:
    return 0
  elif n == 0:
    return 1
  else:
    return (comb(n-1) + comb(n-2))

print(comb(n)%(10**9 + 7))

Submission status: Runtime Error

Solution code:
def combination(n, r):
    r = min(r, n-r)
    nume = 1
    denomi = 1
    for i in range(1, r+1):
        denomi *= i
    for i in range(n-r+1, n+1):
        nume *= i
    return nume // denomi

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

sl = []
cnt = -1
ng = 0
for i in range(M):
    a = int(input())
    b = (a - 1) - (cnt + 1)
    if b == -1:
        ng = 1
    sl.append(max(b, 1))
    cnt = a

if ng:
    print(0)
else:
    sl.append(max(N - (a + 1), 1))
    ans = 1
    for s in sl:
        p = 0
        for i in range(s):
            j = s - i
            if (i <= j):
                p += combination(j, i)
            else:
                break
        ans *= p
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
def main(A, dp, n, mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1, mod)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5 + 2)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)

Submission status: Runtime Error

Solution code:
def combination(n, r):
    r = min(r, n-r)
    nume = 1
    denomi = 1
    for i in range(1, r+1):
        denomi *= i
    for i in range(n-r+1, n+1):
        nume *= i
    return nume // denomi

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

sl = []
cnt = -1
for i in range(M):
    a = int(input())
    b = (a - 1) - (cnt + 1)
    if b == -1:
        print(0)
        break
    sl.append(max(b, 1))
    cnt = a
else:
    sl.append(max(N - (a + 1), 1))
    ans = 1
    for s in sl:
        p = 0
        for i in range(s):
            j = s - i
            if (i <= j):
                p += combination(j, i)
            else:
                break
        ans *= p
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(2, n+1):
    if D[i] == 0:
        continue
    D[i] = (D[i-1] + D[i-2]) % MOD
print(D[i])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(100000) 

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

@lru_cache(maxsize=100000)
def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(maxsize=100000)

import sys
sys.setrecursionlimit(100000) 

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

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

print(stair(n))

Submission status: Runtime Error

Solution code:
mod = 1000000007
 
N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)] + [N + 1]
 
for i in range(len(A) - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        quit()
 
memo = {0: 1, 1: 1, 2: 2, 3: 3}
 
def fib(n):
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
 
ans = 1
pre = -1
lo = 0
for a in A:
    f = fib(a - 1 - lo)
    ans = (ans * f) % mod
 
    lo = a + 1
    pre = a
 
print(ans)

Submission status: Runtime Error

Solution code:
def main(A, dp, n, mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1, mod)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)

Submission status: Runtime Error

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

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

t = []
j = 1
for i in range(1,n+1):
    if i in s:
        t.append(j)
        j = 0
    else:
        j += 1
if j != 0:
    t.append(j)

memo = {}
ans = 1
fibo(max(t),memo)
for i in t:
    ans *= memo[i]
ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
def main(A, dp, n, mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)

Submission status: Runtime Error

Solution code:
def main(A, dp, n mod):
    if n == -1:
        return dp[0]

    if (n in A) == False: 
        dp[n] = (dp[n + 1] + dp[n + 2]) % mod
    return main(A, dp, n-1)
 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1
ans = main(A, dp, N-2, mod)
print(ans)

Submission status: Runtime Error

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

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for j in range(i+1, min(N, i+2)+1):
    if j not in A:
      dp[j] += dp[i]
      dp[j] %= mod
print(dp[N])

Submission status: Runtime Error

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

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

t = []
j = 1
for i in range(1,n+1):
    if i in s:
        t.append(j)
        j = 0
    else:
        j += 1
if j != 0:
    t.append(j)

ans = 1
for i in t:
    ans *= fibo(i)
ans %= 1000000007
print(ans)