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 acinput():
    return list(map(int,input().split(" ")))


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


Mod=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    if x<0:
        return 0

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%Mod
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%Mod
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%Mod)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
NMAX = 10 ** 5

A = []
for _ in range(M):
    A.append(int(input()))

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if A[0] == 1 else 1
for i in range(2, N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import factorial

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

def fibo(dan):
    if dan == 0 or dan == 1: return 1
    else: return fibo(dan-1) + fibo(dan-2)

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
F = [1,1]

def fibo(n):
    if n <= len(F):
        return F[n-1]
    while len(F) < n:
        F.append(F[-1] + F[-2])
    return F[n-1]

N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
MOD = 1000000007

B = [A[0]]
for i in range(M-1):
    B.append(A[i+1] - A[i] - 1)
B.append(N - A[M-1])
ans = 1
if 0 in B:
    ans = 0
else:
    for n in B:
        ans *= fibo(n)
print(ans % MOD)

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
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = pattern[i - 2] + pattern[i - 1]
    return pattern


def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    stepsList[0] = a[0] - 1
    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] - 1
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]

        else:
            total = total * (pattern[stepsList[k]]) % MOD

    return total


ans = solve()
print(ans)

Submission status: Runtime Error

Solution code:
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			print(0)
			flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

Submission status: Runtime Error

Solution code:
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)

Submission status: Runtime Error

Solution code:
import sys

mod = int(1e9+7)

def dfs(i,dp,bad):
  	if i == 0:
      return 1
    if i in dp:
      return dp[i]
	dp[i] = 0;
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x)
        dp[i] %= mod
	return dp[i]
  
n = int(sys.stdin.next())
m = int(sys.stdin.next())
bad = set()
for _ in range(m):
  a = int(sys.stdin.next())
  bas.add(a)
print(dfs(n,dict(),bad))

Submission status: Runtime Error

Solution code:
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())
o = 1
p = 0
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1)
    p = ft

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import factorial

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

def fibo(dan):
    if dan == 0 or dan == 1: return 1
    else: return fibo(dan-1) + fibo(dan-2)

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan)) % 1000000007
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int,input().split(" ")))


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


Mod=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%Mod
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%Mod
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%Mod)

Submission status: Runtime Error

Solution code:
cache = {1: int(1), 2: int(2)}


def calc(_n):
    if _n in cache:
        return cache[_n]
    else:
        x = int(calc(_n - 1) + calc(_n - 2))
        cache[_n] = x
        return x


N, M = map(int, raw_input().split())
prev_a = int(-1)
ans = int(1)

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

for i in range(0, M):
    a = int(input())
    if a == 1:
        prev_a = 1
    elif prev_a + 1 == a:
        ans = 0
        break
    else:
        ans = ans * calc(a - prev_a - 2)
        prev_a = a

if ans == 0:
    print(ans)
else:
    if prev_a + 1 == N:
        ans = ans
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros(n+2)
dp[0] = 1
for i in range(0, a[0]):
    dp[i+2] += dp[i]
    dp[i+1] += dp[i]
for i in range(m-1):
    for j in range(a[i]+1, a[i+1]):
        dp[j+2] += dp[j]
        dp[j+1] += dp[j]
for i in range(a[m-1]+1, n):
    dp[i+2] += dp[i]
    dp[i+1] += dp[i]
print(int(dp[n])%1000000007)

Submission status: Runtime Error

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

gap=[0]*m
gap[0]=a[0]-1
for i in range(3,n+1):
    lst[i]=lst[i-1]+lst[i-2]
    
    
for i in range(1,m):
    gap[i]=a[i]-a[i-1]-1
gap.append(n-a[-1]-1)
    

ans=1
for i in range(len(gap)):
    ans*=lst[gap[i]]
    ans=ans%(10**9+7)
b=a[0]
for i in range(1,len(a)):
    if b+1==a[i]:
        ans=0
    b=a[i]


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

Submission status: Runtime Error

Solution code:

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())
o = 1
p = 0
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1)
    p = ft

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=list(int(input()) for _ in range(M) )
ans=0
ansn1=0
ansn2=0
mod=1000000007
A=a[0]
for i in range(N):

    if i>=2 and  i+1 < A:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans
        continue

    elif i>=2 and  i+1 > A:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans
        if a.index(A)+1<=M-1:
            A=a[a.index(A)+1]
        else:
            A=mod
        continue

    elif i+1 == A:
        ans = 0
        ansn2 = ansn1
        ansn1 = ans
        if a.index(A) + 1 <= M - 1:
            A = a[a.index(A) + 1]
        else:
            A=mod
        continue


    if i==0:
        if i+1 not in a:
            ans=1
            ansn2 = 0
            ansn1=ans


    elif i==1:
        if i+1 not in a:
            ans=1+ansn1
            ansn2 = ansn1
            ansn1=ans
        else:
            ans=0
            ansn2=ansn1
            ansn1=ans


print(ans)

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int,input().split(" ")))


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


M=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%M
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%M
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%M)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

Submission status: Runtime Error

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b

if M == 0:
    print(fib(N))

flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1

if flag >= 1:
    print(0)


else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int,input().split(" ")))


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


M=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%M
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%M
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%M)

Submission status: Runtime Error

Solution code:
# 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())
o = 1
p = 0
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft-1)
    p = ft

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

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	print(A)
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			print(r)
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

Submission status: Runtime Error

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

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 = [1,0]
def dps(cnt,cantvisit):
    if cnt == n + 1 :
        return 
 
    else :
        if cnt == 1 :
            if cnt in cantvisit :
                dp[1] = 0
                cnt += 1
            else : 
                dp[1] = 1
                cnt += 1
        else :
            if cnt in cantvisit : 
                a  = 0 
                dp[0] = dp[1]
                dp[1] = a
                cnt += 1
            else :
                
                a  = (dp[0] + dp[1]) % mod
                dp[0] = dp[1]
                dp[1] = a 
                cnt += 1
        return dps(cnt,cantvisit)
dps(1,para)
print("{}".format(dp[1]))

Submission status: Runtime Error

Solution code:
import math
N,M = map(int, input().split())
def C(a,b):
    return math.factorial(a+b)/(math.factorial(a)*math.factorial(b))
def pattern(n):
    ans = 0
    i = 0
    while n - 2*i >= 0:
        ans += C(n-i*2,i)
        i += 1
    return ans
ans = 1
mod = 10**9 + 7
l = [0 for i in  range(M)]
for i in range(1,M):
    l[i] = int(input()) - l[i-1] -2
if N-l[M-1]-2 >= 0:
    l.append(N-l[M-1]-2)
l.sort()
for i in range(len(l)):
    if i != 0 and l[i] == l[i-1]:
        ans *= tmp
    else:
        ans *= pattern(l[i])
    ans = ans%mod
    tmp = pattern(l[i])
print(int(ans))

Submission status: Runtime Error

Solution code:
import sympy as sym #sympyのインポート
def Fib(n):
    x = sym.symbols('x',nonnegative=True,integer=True) #変数xの宣言(非負の整数)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1)) #一般項の式
    result=Fib.subs(x,n) #xにnを代入
    result=result.evalf() #式を浮動小数点数として評価
    return int(result)
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        for w in newlist:
            ans = (ans*Fib(w))%1000000007
        print(ans)

Submission status: Runtime Error

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

flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1

if flag >= 1:
    print(0)


else:
    def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b

    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

    print(ans)

Submission status: Runtime Error

Solution code:
def acinput():
    return list(map(int,input().split(" ")))


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


M=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    res=0
    zeroflg=True
    if  a[x-1]==1:
        res+=solve(x-1)%M
        zeroflg=False
    if a[x-2]==1:
        res+=solve(x-2)%M
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%M)

Submission status: Runtime Error

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
l = []
for i in range(n):
    a = input()
    a.split()
    l.append(a)
def f(x,y):
    global l ,n,m
    ans = -3
    if l[x][y] == "#":
        return 0
    else :
        for i in range(x,n):
            if l[i][y] == ".":
                ans += 1
            else :
                break
        for i in range(x+1):
            if l[x-i][y] == ".":
                ans += 1
            else :
                break
        for i in range(y,m):
            if l[x][i] == ".":
                ans += 1
            else :
                break
        for i in range(y+1):
            if l[x][y-i] == ".":
                ans += 1
            else:
                break
        return ans
k = 1
for i in range(n):
    for j in range(m):
        k = max(k,f(i,j))
        if k == n + m - 1:
            break
print(k)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2000)

N,M = map(int,input().split(' '))
l = [int(input()) for i in range(M)]

pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    # print("n",n)
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        # print(n,r)
        tmp += cmb(n, r)
        dif = n-r
        # print("tmp",tmp,n,r)
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

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

list_Stairs = []

for i in range(M):
    list_Am.append(int(input()))
# print(str(list_Am))

## Anにはスタート合わせて何段あるかが入る
for j,An in enumerate(list_Am):
    if j == 0:
        list_Stairs.append(An)
    else:
        list_Stairs.append(An-list_Am[j-1]-1)
list_Stairs.append(N-list_Am[-1])

# print(str(list_Stairs))

## スタートを0としてn段目までか（スタート合わせてn+1段ある）
def endFib(n, a1 = 1, a2 = 1):
    if (n < 2): 
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)% 1000000007

result = 1
if 0 in list_Stairs:
    result = 0
else:
    for Stair in list_Stairs:
        # print("段数："+str(Stair))
        # print(str(endFib(Stair-1)))
        result = result * endFib(Stair-1)
        result = result % 1000000007

print(str(result))

"""
if __name__ == "__main__":
    for i in range(10):
        print(str(endFib(i)))
"""

Submission status: Runtime Error

Solution code:
    import sys
    import numpy as np
     
    X = (1+np.sqrt(5))/2
    Y = (1-np.sqrt(5))/2
    Z = np.sqrt(5)
     
    def InputToInt():
        A = input().split()
        for i in range(len(A)):
            A[i] = int(A[i])
        return A
     
    def cases(N):
        if N == 0:
            print('0')
            sys.exit()
        return int((np.power(X, N)-np.power(Y, N))/Z+0.1)
        
        
    if __name__ == '__main__':
        N, M = InputToInt()
        result = 1
        oldA = -1
        for i in range(M):
            A = int(input())
            result *= cases(A - oldA - 1)
            oldA = A
        result *= cases(N - A)
        print(result % 1000000007)

Submission status: Runtime Error

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



if n == 1:
    print(1)

elif n == 2:
    if m == 0:print(2)
    elif m == 1:
        if a[0] == 2:print(0)
        else:print(1)
        
    
elif n == a[-1]-1:
    print(0)
    
else:
    if m == 0:
        t = -1
    else:
        c = 0
        t = a[c]-1
    x, y = 0, 1
    for i in range(n):
        if x == 0 and y == 0:
            break
        elif i == t:
            x, y = y, 0
            if a[c]-1 == a[-1]-1:
                continue
            else:
                c += 1
                t = a[c]-1
        else:
            x, y = y, x + y
    print(y%1000000007)

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())
o = 1
p = 0
ft = int(input())
if ft < 3:
    p = ft
elif ft == 3:
    o = 2
    p = ft
elif ft > 3:
    o = endFib(ft)
    p = ft
for i in range(m-1):
    t = int(input())
    if t-p == 1:
        print(0)
        exit()
    elif t-p-1 == 1:
        p = t
        pass
    elif t-1-p == 2:
        p = t
        pass
    elif t-1-p > 2:
        o = o*endFib(t-2-p)
        p = t
if n-p > 3:
    o = o * endFib(n-p-1)
elif n-p == 3:
    o = o*2
print(o % 1000000007)

Submission status: Runtime Error

Solution code:
# import syinput = sys.stdin.readline
md = 1000000007
dp=[]
def countways(n,broken,ix):
	global dp,md
	if(dp[ix]!=-1):
		return dp[ix]

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

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(brok	en)
print(countways(n,broken,0)%md)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
b = [-1]
ans = 1

def dfs(top, bot):
    if top == bot:
        return 1
    elif top < bot:
        return 0
    else:
        return dfs(top - 1, bot) + dfs(top - 2, bot)
    
for i in range(m):
    broken = int(input())
    b.append(broken)

b.append(n + 1)
##print (b)

for i in range(len(b) - 1):
    if b[i + 1] == b[i] + 1:
        ans = 0
        break
    else:
##        print (b[i + 1] - 1, b[i] + 1)
        ans *= dfs(b[i + 1] - 1, b[i] + 1)
        ans %= 1000000007

print (ans)

Submission status: Runtime Error

Solution code:
mod = 1000000007


def feb(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    k = (n + 1) / 2 if n % 2 else n / 2
    fib_k = feb(k)%mod
    fib_k_1 = feb(k - 1)%mod
    return (fib_k**2 + fib_k_1**2)%mod if n % 2 else ((2 * fib_k_1 + fib_k) * fib_k)%mod

    # if n==0:
    #     return 0
    # if n==1:
    #     return 1
    # else:
    #     return feb(n-1)+feb(n-2)
    # root = math.sqrt(5)
    # return int((1/root)*(((1+root)/2)**n - ((1-root)/2)**n))

def calculate(n, b):
    diff = [b[i+1] - b[i] - 1 for i in range(len(b)-1)]
    diff.insert(0, b[0])
    diff.append(n - b[-1])
    sum = 1
    for d in diff:
        if d == 0:
            return 0
        sum *= feb(d)%mod
        sum = sum%mod
    return sum


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

print(calculate(n, b))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
n += 1
a = [-1]
for i in range(m):
    a.append(int(input()))
a.append(n)
 
pattern = 0    
for i in range(1, len(a)):
#     print("for up to {}th step".format(a[i] - 1))
    step = [0] * (a[i] - a[i-1] - 1)
#     if a[i] - a[i-1] == 2:
#         step[1] = 1
#         for j in range(2, (a[i] - a[i-1])):
#             step[j] = step[j-1] + step[j-2]
#     else:
    step[1] = 1
    step[2] = 2
    for j in range(3, (a[i] - a[i-1] - 1)):
        step[j] = step[j-1] + step[j-2]
#     print(step)
#     print("there are {} patterns".format(max(step)))
    pattern += max(step)
print(pattern)

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(5000):
  a,b = b,a+b
  ref.append(b)
ans = 1
for num in dif:
  ans *= ref[num]
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split(' '))
l = [int(input()) for i in range(M)]
 
pre = 0
last = -1
ans_l = []
flag = False
l.append(N+1)
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
 
for i in l:
    if i==1:
        last = 1
        continue
    if i-last==1:
        flag =True
        break
    n = i - last - 3
    r = 0
    tmp = 1
    dif = 1
    while dif>0:
        r += 1
        if n<=0 or n<r:
            break
        tmp += cmb(n, r)
        dif = n-r
        n -= 1
    ans_l.append(tmp)
    # print(i,ans_l)
    last = i
if flag:
    print(0)
else:
    ans = 1
    for i in ans_l:
        ans*=i
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
 
a = [int(input()) for i in range(M)]
 
wa = (10**9) + 7
 
def Fib(n):
    if n==0:
        return 0 #F0
    elif n==1:
        return 1 #F1
    elif n==2:
        return 1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 0 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo
 
 
 
 
 
ans = 1
 
 
 
if M!= 1:
    length = a[0]
    ans *= Fib(length+1)
 
    for i in range(0,M-1):
        length = a[i+1]-a[i]-1
        # print(length)
        if length == 0:
            ans *= 0
        else:
            ans *= Fib(length+1)
        # print(ans)
 
 
    
if M==1:
    length = a[0]
    ans *= Fib(length+1)
 
 
 
 
length = N-a[-1]
 
 
ans *= Fib(length+1)
 
print(ans%wa)