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:
import sys
n, m = map(int, input().split())
a_list = []
for i in range(m):
    a_i = int(input())
    a_list.append(a_i)
#print(n, m, a_list)
#print(a_list)
flag = 0

'''
def stepup(x):
    #x段
    ans = 0
    for i in range(x):
        if i==0:
            two_before=1
            ans=1
        elif i==1:
            one_before=2
            ans=2
        else:
            #print(two_before, one_before)
            ans = one_before+two_before
            two_before = one_before
            one_before = ans
    return(ans)
'''
def stepup(x):
    x += 1
    ans = ((1 + 5**0.5) / 2)**x / 5**0.5 + 0.5
    return(int(ans))

#print(stepup(1))
#print(a_list)
for i in range(m):
    if i==0:
        if a_list[i]==1:
            count = 1
            continue
        else:
            count = stepup(a_list[0]-1)
    else:
        if a_list[i]-a_list[i-1]==1:
            #print(a_list[i], a_list[i-1])
            flag = 1
            break
        elif a_list[i]-a_list[i-1]==2:
            pass
        else:
            #print(stepup(23))
            #print(i, stepup(a_list[i]-a_list[i-1]))
            count *= stepup(a_list[i]-a_list[i-1]-2)
    #print(count)
#print(len(a_list), m)
if n-a_list[m-1]==1:
    pass
else:
    count *= stepup(n-a_list[i]-1)
#print(count)

if flag==1:
    print(0)
else:
    print(count%1000000007)
#print((stepup(20)**4 * stepup(10))%1000000007)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
s =[0]*(b+1)
flag = 0
p = [0]*b
goukei = 0
for i in range(b):
  if i == 0:
    p[i] = int(input())
  else:
    p[i] = int(input())
    if (p[i] -p[i-1]) ==1:
      flag = 1
      break
for l in range(b+1):
  if l == 0:
    s[l] = p[l] -1
  elif l == b:
    s[l] = a - p[l-1]
  else:
    s[l] = p[l] - p[l-1]-1
counter = 0
def fib(n):
    memo = [0] * n
    memo[0:2] = [0, 1]
    for i in range(2, n):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n-1]
if flag == 0:
  for f in range(len(s)):
    if not s[f] == 0:
      goukei += fib(s[f]+2)
  print(goukei%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
class Solution(object):
	def __init__(self):
		self.ans = 0
	def search(self, pos, dest):
		if(pos > dest):
			return
		if(pos == dest):
			self.ans += 1
			return
		if(pos - dest % 3 == 0):
			self.ans += (pos // 3) * 2
			return
		self.search(pos+1, dest)
		self.search(pos+2, dest)

N, M = map(int, input().split())
A = []

prev = 0

for i in range(M):
	curr = int(input())
	A.append(curr)
	#prev = curr

A.append(N+1)

#print(A)

ans = 1

prev = 0
for i in range(len(A)):
	s = Solution()
	if(i == 0):
		prev = 0
	else:
		prev = A[i-1] + 1
	#print(prev)
	s.search(prev,A[i]-1)
	con = s.ans
	#print(con)
	ans *= con % 1000000007

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [0]
for i in range(m):
    a.append(int(input()))
a.append(n)
    
def ways(n):
    if n == 1:
        return 1
    elif n == 0:
        return 0
    elif n == 2:
        return 2
    else:
        return ways(n-1) + ways(n-2)

times = 1
flag = 0
for i in range(len(a)-1):
    t = a[i+1]-a[i]
    if a[i+1] == 1 or a[i] == n-1 or t == 0:
        continue
    elif t == 1:
        flag = 1
        break
    else:
        times *= ways(t-1)

if flag:
    print(0)
else:
    print(times % (10**9 +7))

Submission status: Runtime Error

Solution code:
import math

N,M=map(int,input().split())
a=[-1]+[int(input()) for i in range(M)]+[N+1]
ans=1

for i in range(M+1):
    dist=a[i+1]-a[i]-2
    if dist<0 and a[i]!=-1 and a[i+1]!=N+1:
        ans=0
        break
    
    val=0
    cnt1=dist%2
    cnt2=dist//2
    while cnt2 >= 0:
        val+=math.factorial(cnt1+cnt2)/math.factorial(cnt1)/math.factorial(cnt2)
        cnt2-=1
        cnt1+=2
    ans*=val
    print(dist,val)

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M - 1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = -1
a[m+1] = n+1
ans = 1
for i in range(m):
  a[i+1] = int(input())
for i in range(m+1):
  if a[i]+1 == a[i+1] and i != 0:
    ans = 0
  else:
    x = a[i+1]-a[i]-1
    ans = ans * int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

if m == 0:
    x = a[m+1]-a[i]-1
    ans = int(1/(5**0.5) * (((1+(5**0.5))/2)**x - ((1-(5**0.5))/2)**x)) %1000000007

print(ans)

Submission status: Runtime Error

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

total = [0 for _ in range(n)]
one = [0 for _ in range(n)]
two = [0 for _ in range(n)]

if 1 not in a:
    one[0] = 1
if 2 not in a:
    one[1] = 1
    two[1] = 1
total[1] = one[1]+two[1]

for i in range(2,n):

    if (i+1) not in a:
        one[i] = total[i-1]
        two[i] = total[i-2]
        total[i] = one[i]+two[i]

print(total[-1] % 1000000007)

Submission status: Runtime Error

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

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

time_f=[]

for i,v in enumerate(a):
    if i == 0:
        # print (fib(a[i]))
        time_f = fib(a[i])
    else:
        # print((a[i]-a[i-1]-1))
        # print (fib(a[i]-a[i-1]-1))
        time_f *=fib(a[i]-a[i-1]-1)


print(time_f%1000000007)

Submission status: Runtime Error

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

a_list = [0] * M

for m in range(M):
    a_list[m] = int(input())

for m in range(M - 1):
    if a_list[m] + 1 == a_list[m + 1]:
        print(0)
        sys.exit()

range_list = [i for i in range(1, N + 1)]
new_list = [0] * (M + 1)

a = 0
if a_list[0] == 1:
    new_list[0] = []
else:
    new_list[0] = [0] + range_list[0: a_list[0] - 1]
new_list[M] = range_list[a_list[M - 1]:]

if M - 1 >= 1:
    for m in range(1, M):
        new_list[m] = range_list[a_list[m - 1]: a_list[m] - 1]

MOD = 1000000007
#print(new_list)
value = 1
for item in new_list:
    if len(item) == 0:
        continue
    else:
        if (len(item) - 1) % 2 == 0:
            value *= (2 ** ((len(item) - 1) // 2)) % MOD
        else:
            value *= ((2 ** ((len(item) - 1) // 2)) + 2 ** (((len(item) - 1) // 2) - 1)) % MOD
print(value)

Submission status: Runtime Error

Solution code:
import math
n,m = map(int,input().split())
before = -1
alls = 1
a = -1
if m != 0:
        for i in range(m):
                a = int(input())
                b = (a - before - 2) // 2
                c = a - before - 2
                ptr = 0
                for j in range(b + 1):
                        ptr += math.factorial(c - j) / (math.factorial(j) * math.factorial(c - 2 * j))
                alls = alls * ptr
                before = a
ptr = 0
b = (n - a - 1) // 2
c = n - a - 1
for j in range(b + 1):
        ptr += math.factorial(c - j) / (math.factorial(j) * math.factorial(c - 2 * j))
alls = alls * ptr
print(int(alls % 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)]

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:
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[count]:
        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:
        if count < m-1:
            count += 1
            
print(dp[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = list(map(lambda x: int(x), inputs[1:]))

    prev = broke_steps[0]
    for broke_step in broke_steps[1:]:
        if broke_step - prev == 1:
            return 0

    SSSS = 1000000007

    patterns = [0]
    for i, step in enumerate(reversed(range(1, N))):
        if step in broke_steps:
            ap = 0
        elif step == N - 1:
            ap = 1
        elif step == N - 2:
            ap = 2
        else:
            ap = (patterns[i] + patterns[i - 1]) % SSSS
        patterns.append(ap)

    return patterns[-1] + patterns[-2]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

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

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*(n+1)
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        #dp[i]=dp[i]%d

    if m == 0:
        print(dp[n]%d)

    else:
        ans = []
        pre = 0
        for i in range(len(a)):
            if i == 0:
                ans.append(a[i]-pre)
            else:
                ans.append(a[i]-pre-1)
            pre = a[i]

        #print(ans)
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**20)

if m == 0:
    print(countWays_memo(n))
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    def countWays_memo(n):
        memo = [-1]*(n+1)
        def _countWays(n):
            if n < 0:
                return 0
            elif n == 0:
                return 1
            else:
                if memo[n] > -1:
                    return memo[n]
                else:
                    memo[n] = _countWays(n-1) + _countWays(n-2) 
                    return memo[n]
        return _countWays(n)

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
full = 1000000007
a = []
for _ in range(m):
    a += [int(input())]

b = []
start = 0
for x in a:
    b += [-start+x]
    start = x+1
b  += [-start+n+1]

print(b)

def steps(N, cnt):
    if N == 2:
        cnt += 1
        return cnt
    if N ==1:
        cnt += 1
        return cnt
    if N > 2:
        cnt = steps(N-1,cnt)
        cnt = steps(N-2,cnt)
        return cnt

# l = []
# for x in a:
if 0 in b:
    print(0)

else:
    ans = 0
    for z in b:
        ans += steps(z, 0)

    print(ans%full)
# n = int(input())
# cnt = steps(n,0)
# print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000)
N, M = map(int, input().split())
a = [int(input())for _ in range(M)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
dp[1] = 1
def loop(n):
    if n <= 0:
        return 1
    if dp[n] >= 0:
        return dp[n]
    ans = 0
    for i in range(1, 3):
        if n - i in a:
            continue
        ans += loop(n - i)
        ans %= 1000000007

    dp[n] = ans
    return dp[n]

loop(N)
print(dp[N])

Submission status: Runtime Error

Solution code:
from scipy.special import comb
def c(n):
    c = 0
    if n != 0:
        for i in range(n):
            c += comb(n-i, i, exact=True)
    return c
N, M = map(int,input().split())
ans = 1
pre_a = 0
for j in range(M+1):
    if j != M:
        a = int(input())

    else:
        a = N
    n = a - pre_a - 1
    if a == 1:
        ans *= 1
    else:
        ans *= c(n)
    pre_a = a
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a_list = [int(input()) for x in range(m) ]
import numpy as np
kaidan = np.zeros(n+1)

kaidan[1] = 1 
kaidan[2] = 2 
if 1 in a_list:
    kaidan[1] = 0
    kaidan[2] = 1
if 2 in a_list: 
    kaidan[2] = 0

for x in range(3,n+1):
    kaidan[x] = kaidan[x-1]+kaidan[x-2]
    if x in a_list:
        kaidan[x]  = 0
print(int(kaidan[n]))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = []
for i in range(M):
    As.append(int(input()))
    
Ds = []
for i in range(M):
    if i==0:
        Ds.append(As[0]-1)
    else:
        Ds.append(As[i]-1-As[i-1])
Ds.append(N-As[-1])

def fibo(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    S = [1, 1]
    for i in range(2, n):
        S.append(S[-2]+S[-1])
    return S[-1]

if min(Ds)==0:
    print(0)
else:
    Fs = [fibo(n) for n in Ds]
    pattern = 1
    for f in Fs:
        pattern *= f
    print(pattern % 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)

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

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

Submission status: Runtime Error

Solution code:
import operator
from functools import reduce


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(operator.mul, range(n, n-r, -1), 1)
    denom = reduce(operator.mul, range(1, r+1), 1)
    return numer // denom


def calc_step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = calc_step2patterns(num_step)
        step_dict[num_step] = ret
        return ret


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

last_wet = -1
num_pattern = 1
d = {}

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)

# 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:
from functools import lru_cache
N, M = map(int, input().split(' '))

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

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib((diff-1)%1000000007)
    sum %= 1000000007
    a_p = a

if (N - a_p == 1):
    print('0')
    exit()

sum *= fib(N - a_p)
sum %= 1000000007
print(sum)

Submission status: Runtime Error

Solution code:
import math
phi = (1 + math.sqrt(5)) / 2

def counter(n):
    if n == 0:
        return 0
    else:
        f = round(phi**(n) / math.sqrt(5)) % (10**9+7)
        return f
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
ans = counter(a[0])
for i in range(1,M+1):
    ans = (ans * counter(a[i]-a[i-1]-1)) % (10**9+7)
#ans = ans * round(phi**(N-a[-1]) / math.sqrt(5)) % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import math
def f(k):
    aaa = 1/math.sqrt(5)*(((1+math.sqrt(5))/2)**k-((1-math.sqrt(5))/2)**k)%1000000007
    return aaa
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input())
if start == []:
    print(f(n-1))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(n-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        for w in newlist:
            ans = 1
            ans = ans*f(w-1)%1000000007      
        print(ans)

Submission status: Runtime Error

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

def stair(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return stair(x - 1) + stair(x - 2)

s = stair(A[0]) * stair(n - A[m - 1])

for i in range(m - 1):
    a = A[i + 1] - A[i] - 1
    s = s * stair(a)



print(int(s%1000000007))

Submission status: Runtime Error

Solution code:
def step(N,M):
    if N == 0:
        return 1
    if N < 0:
        return 0
    if N - 1 in M and N - 2 in M:
        return 0
    if N - 1 in M:
        return step(N-2, M) % 1000000007
    if N - 2 in M:
        return step(N-1,M) % 1000000007
    return (step(N - 1, M) + step(N - 2, M)) % 1000000007


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

print(step(N, a))

Submission status: Runtime Error

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

total = [0 for _ in range(n)]
one = [0 for _ in range(n)]
two = [0 for _ in range(n)]

if 1 not in a:
    one[0] = 1
if 2 not in a:
    one[1] = 1
    two[1] = 1
total[1] = one[1]+two[1]

for i in range(2,n):

    if (i+1) not in a:
        one[i] = total[i-1]
        two[i] = total[i-2]
        total[i] = one[i]+two[i]
        print(one[i],two[i],total[i])

print(total[-1] % 1000000007)

Submission status: Runtime Error

Solution code:
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = list(map(lambda x: int(x), inputs[1:]))

    prev = broke_steps[0]
    for broke_step in broke_steps[1:]:
        if broke_step - prev == 1:
            return 0

    SSSS = 1000000007

    patterns = [0]
    for i, step in enumerate(reversed(range(1, N))):
        if step in broke_steps:
            ap = 0
        elif step == N - 1:
            ap = 1
        elif step == N - 2:
            ap = 2
        else:
            ap = patterns[i] + patterns[i - 1]
        patterns.append(ap)

    return (patterns[-1] + patterns[-2]) % SSSS


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
for i in range(M):
  dp[a] = -1
k = 10**9+7
d = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if dp[i] == -1:
      continue
    elif i==1:
      dp[i] = 1
    elif i==2:
      dp1 = dp[i-1] if dp[i-1] != -1 else 0
      d += dp[1]
      dp[i] = d
    else:
      dp1 = dp[i-1] if dp[i-1] != -1 else 0
      dp3 = dp[i-3] if dp[i-3] != -1 else 0
      d = d-dp3+dp1
      dp[i] = d
  print(dp[N]%k)

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb

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

pre_a = None
for _ in range(M):
    a = int(input())
    if pre_a is not None and a - pre_a < 2:
        print(0)
        sys.exit()
    pre_a = a
    a_list.append(a)

a_list.append(N + 1)
start_step = 0
end_step = 0
answer = 1
for a in a_list:
    p = 0
    end_step = a - 1
    diff = end_step - start_step
    for x in range(diff // 2 + 1):
      p += comb(diff - x, x, exact=True)

    answer *= p
    start_step = a + 1

answer %= 1000000007
print(answer)

Submission status: Runtime Error

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

def get_num_of_ways(floor_number, broken_floors):
  memo = [-1 for _ in range(floor_number + 1)]
  
  def _fibo(n, skip):
    if n in skip:
      # Be careful n can be 1
      return 0
    elif n <= 1:
      return 1
    elif memo[n] > 0:
      return memo[n]
    ways = _fibo(n - 1, skip) + _fibo(n - 2, skip)
    ways %= 1000000007
    memo[n] = ways
    return ways
    
  return _fibo(floor_number, broken_floors)

print(get_num_of_ways(N, broken_floors))

Submission status: Runtime Error

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

    step1 = 0
    step2 = 0

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

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

    memo[now] = (step1 + step2) % 1000000007
    return memo[now]


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

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

a = deque()
for _ in range(M):
    a.append(int(input()))

before1 = 1
before2 = 0
if len(a)>0:
    ai = a.popleft()

for i in range(N):
    if i == (ai-1):
        before2 = before1
        before1 = 0
        if len(a)>0:
            ai = a.popleft()
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current


print(before1)

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
    # print("n",n)
    while dif>0:
        r += 1
        tmp += cmb(n, r)
        dif = n-r
        n -= 1
        # print("tmp",tmp,n,r)
    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:
NM= list(map(int, input().split()))
A = [int(input()) for i in range(NM[1])]

roots = 1
OUT = False

def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)


for j in range(len(A)):
    #keynum 1 ブロックに1つ，飛ぶしかないのでスルー keynum 0 ブロックに0，問答無用で全体0通り
    keynum = 1

    if j == 0:
        keynum = A[j]
    else:
        keynum = A[j] - (A[j-1]+1)


    if keynum == 0:
        roots = 0
        OUT = True
        break
    elif keynum == 1 or keynum == 2:
        continue
    else:
        roots *= fib(keynum)


lastkeynum = NM[0]+1 - (A[-1]+1)
# print(lastkeynum)
if lastkeynum == 0:
    roots = 0
elif lastkeynum == 1 or lastkeynum == 2:
    roots = roots
else:
    roots *= fib(lastkeynum)


if OUT:
    roots = 0

print(roots%1000000007)

Submission status: Runtime Error

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

def serach(locale, num):
    global res
    if locale + num > N:
        return

    if locale + num == N:
        res+=1
        if res >= 1000000007:
            res=res%1000000007
        return

    if locale + num in hole:
        return

    serach(locale+num, 1)
    serach(locale+num, 2)

serach(0,1)
serach(0,2)

print(res)

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 calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp += factorial(n) / factorial(i) / factorial(n - i)
        # tmp += len(list(itr.combinations(range(n), i)))

    return tmp

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

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
a.append(n+1)
q=1000000007
def fi(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    elif n==2:
        return 2
    else:
        return fi(n-1)+fi(n-2)
A=[a[0]-1]
temp=0
ans=1
for i in range(1,m+1):
    A.append(a[i]-a[i-1]-2)
    if a[i]-a[i-1]-1==0:
        ans=0
    """if temp<a[i]-a[i-1]-2:
        temp=a[i]-a[i-1]-2
Fi=[0]
for i in range(temp+1):
    Fi.append(fi(n))"""

if ans!=0:
    for i in range(m+1):
        ans*=fi(A[i])
Ans=ans%q
print(Ans)

Submission status: Runtime Error

Solution code:
import sys
from pprint import pprint

def solve(n, m, a):
    sum = 1
    a_pre = 0
    for a_i in a:
        if a_pre != 0 and a_pre == a_i:
            return 0
        if a_i == 1:
            a_pre = a_i + 1
            continue
        pattern = (a_i - 1 - a_pre - 1)
        #print pattern
        sum *= 2**pattern
        a_pre = a_i + 1
    pattern = (n - a_pre - 1)
    #print pattern
    sum *= 2**pattern

    return sum % 1000000007


if __name__ == '__main__':

    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = []
    for i in range(m):
        a.append(int(sys.stdin.readline().strip()))
    print solve(n, m, a)

Submission status: Runtime Error

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

def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n in lack:
            return 0
        if n == 0:
            return 1
        elif n == 1:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)

print(fib_memo(N)%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

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

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

elif m == 0:
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 1
    for i in range(3, len(dp)):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n]%d)


else:
    dp = [0]*(n+1)
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        #dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

Submission status: Runtime Error

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

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

a_p = int(input())
sum = fib(a_p)
for i in range(M-1):
    a = int(input())
    diff = a - a_p
    if diff == 1:
        print('0')
        exit()
    sum *= fib((diff-1)%1000000007)
    sum %= 1000000007
    a_p = a

if (N - a_p == 1):
    print('0')
    exit()

sum *= fib(N - a_p)
sum %= 1000000007
print(sum)

Submission status: Runtime Error

Solution code:
from math import factorial
N,M=list(map(int,input().split()))
dansa=[int(input()) for _ in range(M)]
ans=1
flag=True
if dansa[0]==0:
    print("0")
else:
    if len(dansa)>1:
        for i in range(M-1):
            if dansa[i]+1==dansa[i+1]:
                print("0")
                flag=False
                break
if flag:
    dansa.insert(0,0)
    dansa.append(N)
    for i in range(M+1):
        tmp=dansa[i+1]-dansa[i]-1
        arr=[i for i in range(int(tmp/2)+1)]
        #print("tmp:{}".format(tmp))
        hoge=0
        """
        if tmp%2==0:
            arr=[j*2 for j in range(0,int(tmp/2+1))]
            
        else:
            arr=[j*2+1 for j in range(0,int((tmp+1)/2))]
        """
        #print(arr)
        #if tmp%2==0:
        for k in arr:
            n=tmp-k
            hoge+=factorial(n) / factorial(k) / factorial(n-k)
            
        #print(hoge)
        ans=ans*hoge
        #print(ans)
    print(int(ans%1000000007))
    #print(ans)