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(n):
    s, t = 0, 1
    if n == 1:
        return s
    elif n == 2:
        return t
    else:
        for i in range(n-2):
            s, t = t, s + t
        return t
def FIB(q):
    return Fib(q+1)

n,m = map(int,input().split())
A =[]
add = 1
ex = 0
y = 0
for _ in range(m):
    a = int(input())
    A.append(a)
for i in range(1,n+1):
    if A.count(i) == 1 and A.count(i+1) == 1 :
        ex += 1
    else:
        ex += 0
if ex >= 1:
    print(0)
else:
    if A[0] == 1:
        if m ==1:
            add *= FIB(n - 1)
        else:
            for j in range(0,m-1):
                y = A[j+1]-A[j] -1
                add *= FIB(y)
            add *= FIB(n-A[m-1])
    else:
        if m == 1:
            z =0
            for l in range(1,A[0]):
                z += FIB(l)
            add *= z*(FIB(n - A[0]))
        else:
            c = 0
            for u in range(1,A[0]):
                c += FIB(u)
                add *=c
            for k in range(0,m-1):
                y = A[k+1]-A[k] -1
                add *= FIB(y)
            add *= FIB(n - A[m-1])

    print(add % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
    s, t = 0, 1
    if n == 1:
        return s
    elif n == 2:
        return t
    else:
        for i in range(n-2):
            s, t = t, s + t
        return t
def FIB(q):
    return Fib(q+1)

n,m = map(int,input().split())
A =[]
add = 1
ex = 0
y = 0
for _ in range(m):
    a = int(input())
    A.append(a)
for i in range(1,n+1):
    if A.count(i) == 1 and A.count(i+1) == 1 :
        ex += 1
    else:
        ex += 0
if ex >= 1:
    print(0)
else:
    if A[0] == 1:
        if m ==1:
            add *= FIB(n - 1)
        else:
            for j in range(0,m-1):
                y = A[j+1]-A[j] -1
                add *= FIB(y)
            add *= FIB(n-A[m-1])
    else:
        if m == 1:
            z =0
            for l in range(1,A[0]):
                z += FIB(l)
            add *= z*(FIB(n - A[0]))
        else:
            c = 0
            for u in range(1,A[0]):
                c += FIB(u)
                add *=c
            for k in range(0,m-1):
                y = A[k+1]-A[k] -1
                add *= FIB(y)
            add *= FIB(n - A[m-1])

print(add % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
    s, t = 0, 1
    if n == 1:
        return s
    elif n == 2:
        return t
    else:
        for i in range(n-2):
            s, t = t, s + t
        return t
def FIB(q):
    return Fib(q+1)

n,m = map(int,input().split())
A =[]
add = 1
ex = 0
y = 0
for _ in range(m):
    a = int(input())
    A.append(a)
for i in range(1,n+1):
    if A.count(i) == 1 and A.count(i+1) == 1 :
        ex += 1
    else:
        ex += 0
if ex >= 1:
    print(0)
else:
    if A[0] == 1:
        if m ==1:
            add *= FIB(n - 1)
        else:
            for j in range(0,m-1):
                y = A[j+1]-A[j] -1
                add *= FIB(y)
            add *= FIB(n-A[m-1])
    else:
        if m == 1:
            z =0
            for l in range(1,A[0]):
                z += FIB(l)
            add *= z*(FIB(n - A[0]))
        else:
            for u in range(1,A[0]):
                z += FIB(u)
            add *= z*(FIB(n - A[0]))
            for k in range(0,m-1):
                p = A[k+1]-A[k] -1
                add *= FIB(p)
            add *= FIB(n - A[m-1])

print(add % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
    s, t = 0, 1
    if n == 1:
        return s
    elif n == 2:
        return t
    else:
        for i in range(n-2):
            s, t = t, s + t
        return t
def FIB(q):
    return Fib(q+1)

n,m = map(int,input().split())
A =[]
add = 1
ex = 0
y = 0
for _ in range(m):
    a = int(input())
    A.append(a)
for i in range(1,n+1):
    if A.count(i) == 1 and A.count(i+1) == 1 :
        ex += 1
    else:
        ex += 0
if ex >= 1:
    print(0)
else:
    if A[0] == 1:
        if m ==1:
            add *= FIB(n - 1)
        else:
            for j in range(0,m-1):
                y = A[j+1]-A[j] -1
                add *= FIB(y)
            add *= FIB(n-A[m-1])
    else:
        if m == 1:
            z =0
            for l in range(1,A[0]):
                z += FIB(l)
            add *= z*(FIB(n - A[0]))
        else:
            for l in range(1,A[0]):
                z += FIB(l)
            add *= z*(FIB(n - A[0]))
            for k in range(0,m-1):
                y = A[k+1]-A[k] -1
                add *= FIB(y)
            add *= FIB(n - A[m-1])

print(add % 1000000007)

Submission status: Runtime Error

Solution code:
import queue

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

B = []

pre_a = -1
for _ in range(M):
    a = int(input())

    B.append(a - pre_a - 1)
    pre_a = a

B.append(N - pre_a)

fib_list = [0, 1] + [None] * N

def fib(n):
    if fib_list[n] is not None:
        return fib_list[n]
    else:
        if fib_list[n-1] is None:
            fib(n-1)

        fib_list[n] = fib_list[n-1] + fib_list[n-2]
        return fib_list[n]

ans = 1
for b in B:
    ans *= fib(b)

ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
booleans = [True for _ in range(N+1)]
counts = [0 for _ in range(N+1)]
for _ in range(M):
    booleans[int(input())] = False

for n in range(N-1):
    if not booleans[n] and not booleans[n+1]:
        print(0)
        exit()

if booleans[1]:
    counts[1] = 1
if booleans[2]:
    counts[2] = 1 + counts[1]

for n in range(2, N):
    if not booleans[n-1] and booleans[n]:
        counts[n+1] = counts[n]
    elif not booleans[n] and booleans[n-1]:
        counts[n+1] = counts[n-1]
    else:
        counts[n+1] = (counts[n] + counts[n-1]) % 1000000007

print(counts[N])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * M
memo = [-1] * (N + 1)

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

def step(n):
	if memo[n] >= 0:
		return memo[n]
	elif n < 2:
		memo[n] = 1
		return 1
	else:
		memo[n] = (step(n - 1) + step(n - 2)) % mod
		return memo[n]
			
for i in a:
	memo[i] = 0
	
print(step(N))

Submission status: Runtime Error

Solution code:
import sys
#sys.setrecursionlimit(2000)

input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
mod = 10 ** 9 + 7
a = [0] * M
memo = [-1] * (N + 1)

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

def step(n):
	if memo[n] >= 0:
		return memo[n]
	elif n < 2:
		memo[n] = 1
		return 1
	else:
		memo[n] = (step(n - 1) + step(n - 2)) % mod
		return memo[n]
			
for i in a:
	memo[i] = 0
	
print(step(N))

Submission status: Runtime Error

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

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
l = [int(input()) for i in range(M)]
sub = [0 for i in range(M+1)]
for i in range(1,M):
    sub[i] = l[i] - l[i-1] -1
sub[0] = l[0]
sub[M] = N-l[M-1]
max = max(sub)
list = [1 for i in range(max+1)]
for i in range(3,max+1):
        list[i] = list[i-1]+list[i-2]
list[0] = 0
ans = 1
for i in sub:
    ans *= list[i]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
l = [int(input()) for i in range(M)]
sub = [0 for i in range(M+1)]
for i in range(1,M):
    sub[i] = l[i] - l[i-1] -1
sub[0] = l[0]
sub[M] = N-l[M-1]
print(sub)
max = max(sub)
list = [1 for i in range(max+1)]
for i in range(3,max+1):
        list[i] = list[i-1]+list[i-2]
list[0] = 0
ans = 1
for i in sub:
    ans *= list[i]
    ans = ans % 1000000007

print(ans)

Submission status: Runtime Error

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

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
            continue
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Submission status: Runtime Error

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

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Submission status: Runtime Error

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

j = 0
sum = []

for i in range(M+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Submission status: Runtime Error

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

j = 0
sum = []

for i in range(N+1):
    if i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%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())

L = A[0]+1
if L < N - A[M-1]:
    L = N - A[M-1]
for i in range(M-1):
    L1 = A[i+1]-A[i]
    if L1 > L:
        L = L1
        
x = [0]*L
x.insert(0,0)
x.insert(1,1)
if L >2:
    for i in range(L-2):
        x[i+2] = x[i+1] + x[i]
    
S = x[A[0]] * x[N - A[M-1]]
for i in range(M-1):
    S *= x[A[i+1]-A[i]-1]
    
print(S%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())

L = A[0]+2
if L < N - A[M-1]:
    L = N - A[M-1]
for i in range(M-1):
    L1 = A[i+1]-A[i]
    if L1 > L:
        L = L1
        
x = [0]*L
x.insert(0,0)
x.insert(1,1)
for i in range(L-2):
    x[i+2] = x[i+1] + x[i]
    
S = x[A[0]] * x[N - A[M-1]]
for i in range(M-1):
    S *= x[A[i+1]-A[i]-1]
    
print(S%1000000007)

Submission status: Runtime Error

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

if 1 not in A:
    ans[0] += 1
if 2 not in A:
    ans[1] += 1

for i in range(N):
    if i+1 in A:
        continue
    else:
        if i+2 <= N-1:
            if i+2 not in A:
                if i+3 not in A:
                    ans[i+1] += ans[i]
                    ans[i+2] += ans[i]
                else:
                    ans[i+1] += ans[i]
            else:
                if i+3 not in A:
                    ans[i+2] += ans[i]
                else:
                    continue
        elif i+1 <= N-1:
            if i+2 not in A:
                ans[i+1] += ans[i]
            else:
                continue
        else:
            continue
print(ans[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
#集合の中にiが含まれていない場合
    if i not in z:
#i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[i])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
  #集合の中にiが含まれていない場合
    if i not in z:
      #i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[i])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(M)]

#MODに1000000007を入れる
MOD = 10**9 + 7
#Zに集合を作成する
Z = set(a)
 
#i段目までにたどりつく方法を順に求める
dp = [0 for _ in range(N + 1)]
#0段目の場合1とする
dp[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
dp[1] = int(1 not in Z)
#2段目以降の場合
for i in range(2, N + 1):
  #集合の中にiが含まれていない場合
    if i not in Z:
      #i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
#ansに答えを入れる
ans = dp[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(M)]

#MODに1000000007を入れる
MOD = 10**9 + 7
#Zに集合を作成する
Z = set(a)
 
#i段目までにたどりつく方法を順に求める
dp = [0 for _ in range(N + 1)]
#0段目の場合1とする
dp[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
dp[1] = int(1 not in Z)
#2段目以降の場合
for i in range(2, N + 1):
  #集合の中にiが含まれていない場合
    if i not in Z:
      #i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
#ansに答えを入れる
ans = dp[i]
print(dp[i])

Submission status: Runtime Error

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

falls = []
for j in range(m):
    falls.append(int(input()))

steps = [0]

steps.extend(falls)
steps.append(n)

steps.reverse()

result = 1

def roots_mod(number):
    if number ==1:
        return 1 
    elif number == 2:
        return 2
    else:
        return (roots_mod(number-2) + roots_mod(number -1)) % 1000000007

for i in range(m+1):
    stair = steps[i] - steps[i+1]-1

    if stair > 0:
        root =roots_mod(stair)
        result = (result * root) % 1000000007
    else:
        result = 0
        break

print(result)

Submission status: Runtime Error

Solution code:
dp = [0 for i in range(10000)]
dp[0] = 0
dp[1] = 1
for i in range(2,10000):
    dp[i] = dp[i-1]+dp[i-2]

#input    
n,m = map(int,input().split())
tmp1 = 0
tmp2 = 0

cnt = 1
flg = 0

for i in range(m):
    tmp2 = int(input())
    if tmp1 == tmp2:
        flg = 1
    cnt *= dp[tmp2-tmp1]
    tmp1 = tmp2+1
    
cnt *= dp[n-tmp2]
    
if flg == 0:
    print(cnt%1000000007)
else:
    print(0)

Submission status: Runtime Error

Solution code:
dp = [0 for i in range(100)]
dp[0] = 0
dp[1] = 1
for i in range(2,100):
    dp[i] = dp[i-1]+dp[i-2]

#input    
n,m = map(int,input().split())
tmp1 = 0
tmp2 = 0

cnt = 1
flg = 0

for i in range(m):
    tmp2 = int(input())
    if tmp1 == tmp2:
        flg = 1
    cnt *= dp[tmp2-tmp1]
    tmp1 = tmp2+1
    
cnt *= dp[n-tmp2]
    
if flg == 0:
    print(cnt%1000000007)
else:
    print(0)

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 = 1000)
def code(c):
    if c in a:
        return 0
    if c <= 1:
        return 1
    return code(c - 1) + code(c - 2)

count = code(n) % 1000000007
print(count)

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 = 1000)
def code(c):
    if c in a:
        return 0
    if c == 2:
        return 2
    if c <= 1:
        return 1
    return code(c - 1) + code(c - 2)

count = code(n) % 1000000007
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
all_steps = np.ones(N+1)
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
del all_steps

for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]

ok_steps[0] = int(ok_steps[0])
print(ok_steps[0]%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
NM = input()
N, M = NM.split(" ")
del NM
N, M = int(N), int(M)
broken_steps = [int(input()) for num in range(M)]
#all_steps = [num for num in range(N+1)]
all_steps = np.ones(N+1)  ##np.int32だと足りない  ##64もあかんかも
all_steps[broken_steps] = 0
ok_steps = list(all_steps)
#ok_steps = [0 if num in broken_steps else 1 for num in range(len(all_steps))]
#for num in range(len(all_steps)):
#  if num in broken_steps:
#    ok_steps.append(0)
#  else:
#  	ok_steps.append(1)
#del all_steps, broken_steps
#print(ok_steps)
for num in range(0, len(ok_steps)):
  i = - (num + 1)
  
  if (i==-1 or i==-2):
    pass
  else:
    if ok_steps[i]==0:
      pass
    else:
      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
      

#for num in range(0, len(ok_steps)):
#  i = - (num + 1)
#  
#  if (i==-1 or i==-2):
#    pass
#  else:
#    if ok_steps[i]==0:
#      pass
#    else:
#      print(i)
#      ok_steps[i] = ok_steps[i+1] + ok_steps[i+2]
#print(ok_steps[-3])        
print(int(ok_steps[0])%1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(2*10**5)

# 入力
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

MOD = 10**9 + 7
A = set(a)


@lru_cache(maxsize=None)
def f(i):
    return (
        0 if i in A else
        1 if i == 0 or i == 1 else
        (f(i - 1) + f(i - 2)) % MOD
    )


ans = f(N)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
mod = 10**9+7
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n) % mod
elif m > 0:
    ft = int(input())
    if ft < 3:
        p = ft
    elif ft == 3:
        o = 2
        p = ft
    elif ft > 3:
        o = endFib(ft-1) % mod
        p = ft
    else:
        pass

    for i in range(m-1):
        t = int(input())
        if t-1-p == 0:
            print(0)
            exit()
        elif t-1-p == 1:
            p = t
        elif t-1-p == 2:
            p = t
        elif t-1-p == 3:
            o = (o * 2) % mod
            p = t
        elif t-1-p > 3:
            o = (o * endFib(t-2-p)) % mod
            p = t
        else:
            pass
    if n-p > 3:
        o = (o * endFib(n-p-1)) % mod
    elif n-p == 3:
        o = (o * 2) % mod
    else:
        pass

print(int(o))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# c ABC129
# input


def endFib(n, a1=1, a2=0):
    if (n < 1):
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)


n, m = map(int, input().split())
mod = 10**9+7
o = 1
p = 0
if m == 0:
    if n < 3:
        o = n
    else:
        o = endFib(n) % mod
elif m > 0:
    ft = int(input())
    if ft < 3:
        p = ft
    elif ft == 3:
        o = 2
        p = ft
    elif ft > 3:
        o = endFib(ft-1) % mod
        p = ft
    else:
        pass

    for i in range(m-1):
        t = int(input())
        if t-1-p == 0:
            print(0)
            exit()
        elif t-1-p == 1:
            p = t
        elif t-1-p == 2:
            p = t
        elif t-1-p == 3:
            o = (o * 2) % mod
            p = t
        elif t-1-p > 3:
            o = (o * endFib(t-2-p)) % mod
            p = t
        else:
            pass
    if n-p > 3:
        o = (o * endFib(n-p-1)) % mod
    elif n-p == 3:
        o = (o * 2) % mod
    else:
        pass

print(o)

Submission status: Runtime Error

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = a1 + a2 1000000007
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

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

else:
    print(fib(n))

Submission status: Runtime Error

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = a1 + a2
            a1 = a2
            a2 = a3

        return a3

ans = fib(li[0])

for i in range(m-1):
    ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(N, dtype=np.int64)
dp[0] = 0 if 0 in holes else 1
dp[1] = 0 if 1 in holes else dp[0] + 1

for i in range(2, N):
    if i in holes:
        dp[i] = 0
    else:
        if (dp[i-2] == 0) & (dp[i-1] == 0):
            break
        else:
            dp[i] = dp[i-1] + dp[i-2]

mod = 1e9 + 7
print(int(dp[-1] % mod))

Submission status: Runtime Error

Solution code:
brokenStairs = {}
memo = {}
modnum = 1000000007


def fibonacci(n):
    if n in memo:
        return memo.get(n)

    if n == 0 or n == 1:
        if n in brokenStairs:
            memo[n] = 0
        else:
            memo[n] = 1
    else:
        if n in brokenStairs:
            memo[n] = 0
            fibonacci(n - 1)
        else:
            memo[n] = (fibonacci(n - 1) + fibonacci(n - 2)) % modnum
    return memo[n]


N, M = raw_input().split(" ")
for i in range(0, int(M)):
    a = int(raw_input())
    brokenStairs[a] = True
print fibonacci(int(N)) % modnum

Submission status: Runtime Error

Solution code:
brokenStairs = {}
memo = {}
modnum = 1000000007


def fibonacci(n):
    if n in memo:
        return memo.get(n)

    if n == 0:
        memo[n] = 1
    else:
        if n in brokenStairs:
            memo[n] = 0
            fibonacci(n - 1)
        else:
            memo[n] = (fibonacci(n - 1) + fibonacci(n - 2)) % modnum
    return memo[n]


N, M = raw_input().split(" ")
for i in range(0, int(M)):
    a = int(raw_input())
    brokenStairs[a] = True
print fibonacci(int(N)) % modnum

Submission status: Runtime Error

Solution code:
def touri(k1):
    if k1==-1:return 0
    an0=0
    k2=0
    while k1>=0:
        an1=1
        for i in range(k2):
            an1=an1*(k1+k2-i)/(i+1)
        an0+=an1
        k1-=2
        k2+=1
    return an0
n,m=map(int,input().split())
l=[int(input()) for _ in range(m)]
l2=[l[0]-1,n-l[-1]-1]
ans=1
for i in range(m-1):
    l2.append(l[i+1]-l[i]-2)
for j in l2:
    ans*=touri(j)
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
def touri(k1):
    if k1==-1:return 0
    an0=0
    k2=0
    while k1>=0:
        an1=1
        for i in range(k2):
            an1=an1*(k1+k2-i)/(i+1)
        an0+=an1
        k1-=2
        k2+=1
    return an0
n,m=map(int,input().split())
l=[int(input()) for _ in range(m)]
l2=[l[0]-1,n-l[-1]-1]
ans=1
for i in range(m-1):
    l2.append(l[i+1]-l[i]-2)
for j in l2:
    print(j)
    print(touri(j))
    ans*=touri(j)
print(int(ans%1000000007))

Submission status: Runtime Error

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

N, M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
result = 1
for i in range(M):
    if i == 0:
        result = Fib(a[i]+1) * result
    else:
        result = Fib(a[i]-a[i-1]) * result


result = result * Fib(N-a[M-1]+1)

print(result%1000000007)

Submission status: Runtime Error

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

N, M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
result = 1
for i in range(M):
    if i == 0:
        result = Fib(a[i]+1) * result
    else:
        result = Fib(a[i]-a[i-1]) * result


result = result * Fib(N-a[M-1]+1)

print(result%1000000007)

Submission status: Runtime Error

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

N, M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))
result = 1
for i in range(M):
    if i == 0:
        result = Fib(a[i]+1) * result
    else:
        result = Fib(a[i]-a[i-1]) * result


result = result * Fib(N-a[M-1]+1)

print(result%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,M = na()
MOD=1000000007
#壊れいている段の数
a=[]
if M>0:
    p=ni()
    a.append(p)
tmp=0
for i in range(M-1):
    tmp=ni()
    if(tmp-1==p):
        #a.append(tmp)
        print(0)
        exit()
    else:
        a.append(tmp)
dp = [0]*(N+1)
dp[0]=1
dp[1]=1
j=0
if(a[0]==0):
    j+=1
    dp[0]=0
if(a[0]==1):
    j+=1
    dp[1]=0
if(N==1):
    t= 1 if M>0 else 0
    print(t)
    exit()
if(N==2):
    for i in a:
        dp[i]=0
    print(dp[0]+dp[1])
    exit()


flag=True
for i in range(2,N+1):
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=MOD
    if a[-1]<i or j>=len(a):
        flag=False
    if(flag and a[j]==i):
        dp[i]=0
        j+=1
    
#print(dp,a)
#print(dp)
print(dp[N])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
interval_max = 0
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
    interval_max = max(interval_max, a[i+1] - a[i])
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

step = [0]*(interval_max+1)
step[0] = step[1] = step[2] = 1
for i in range(3,interval_max+1):
    step[i] = (step[i-2] + step[i-1]) % 1000000007
sum_step = 1
# print(a)
for i in range(len(a)-1):
    if i == 0 or i == len(a)-2:
        sum_step *= step[a[i+1] - a[i]]
        # print(step[a[i+1] - a[i]])
    else:
        sum_step *= step[a[i+1] - a[i] - 1]
        # print(step[a[i+1] - a[i]] - 1)
    sum_step = sum_step % 1000000007
print(sum_step)
# print(step)

Submission status: Runtime Error

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,M = na()
MOD=1000000007
#壊れいている段の数
a=[]
if M>0:
    p=ni()
    a.append(p)
tmp=0
for i in range(M-1):
    tmp=ni()
    if(tmp-1==p):
        #a.append(tmp)
        print(0)
        exit()
    else:
        a.append(tmp)
dp = [0]*(N+1)
dp[0]=1
dp[1]=1
j=0
if(a[0]==0):
    j+=1
    dp[0]=0
if(a[0]==1):
    j+=1
    dp[1]=0


flag=True
for i in range(2,N+1):
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=MOD
    if(flag and a[j]==i):
        dp[i]=0
        j+=1
    if a[-1]<i or j==len(a):
        flag=False
#print(dp,a)
#print(dp)
print(dp[N])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
interval_max = 0
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
    interval_max = max(interval_max, a[i+1] - a[i])
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

step = [0]*interval_max
step[0] = step[1] = 1
for i in range(2,interval_max):
    step[i] = (step[i-2] + step[i-1])
sum_step = 1
for i in range(len(a)-1):
    sum_step *= step[a[i+1] - a[i] - 1]
sum_step = sum_step % 1000000007
print(sum_step)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
interval_max = 0
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        exit()
    interval_max = max(interval_max, a[i+1] - a[i])
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

step = [0]*interval_max
step[0] = step[1] = 1
for i in range(2,interval_max):
    step[i] = (step[i-2] + step[i-1])
print(a, interval_max)
sum_step = 1
for i in range(len(a)-1):
    sum_step *= step[a[i+1] - a[i] - 1]
sum_step = sum_step % 1000000007
print(sum_step)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(a)):
  steps=a[i]-a[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
    res*=patern_nmu
    res%=1000000007
print(res)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

 
if d[0]==1:
    s[0]=0
else:
    s[0]=1
 
if d[1]==1:
    s[1]=0
else:
    s[1]= s[0]+1
 
 
for i in range(2,n):
    if d[i]==1:
        s[i]=0
    else:
        s[i]=(s[i-1]+s[i-2])%1000000007
 
print( s[n-1] % 1000000007)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
d=[0]*n
s=[0]*n
for i in range(k):
    p=int(input())
    d[p-1]=1

 
if d[0]==1:
    s[0]=0
else:
    s[0]=1
 
if d[1]==1:
    s[1]=0
else:
    s[1]= s[0]+1
 
 
for i in range(2,n):
    if d[i]==1:
        s[i]=0
    else:
        s[i]=(s[i-1]+s[i-2])%1000000007
 
print( s[n-1] % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math

n,m = map(int,input().split())
a_list = list(int(input()) for i in range(m))

if a_list[0] != 1:
    x_list = [1,1] 
else:
    x_list = [1,0]

for i in range(n-1):
    if len(x_list) not in a_list:
        x_list.append(x_list[-2] + x_list[-1])
    else:
        x_list.append(0)

print(x_list[-1]%1000000007)