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:
from sys import stdin
def main():
  N, M = map(int, stdin.readline().rstrip().split())
  paterList=[]
  Abefore=0

  a1=1
  a2=2
  for i in range(M):
    A = int(input())
    stepNum=A-Abefore
    
    if stepNum == 1:
      print("0")
      return
    elif stepNum <= 3:
      paterList.append(stepNum-1)
    else:
      an2=a1
      an1=a2
      for j in range(stepNum -1-2):
        patern += an2+an1
        an2 = an1
        an1 = patter
      paterList.append(patern//1000000007 )
  print(sum(paterList)//1000000007)
      
input = lambda: stdin.readline()
main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split(" "))
a=[]
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0
if ans == 1:
    t,w,v = 0,0,0
    for j in range(len(a)):
        if j+1 == m:
            if n-a[j] >= 3:
                v += 1
                w += n-a[j]
            break
        elif a[j] - t >= 3:
            v += 1
            w += a[j] - t
            t = a[j] + 1
        else:
            t = a[j] + 1
ans = v * 2
t = ans // 2
for k in range(w):
    temp = ans
    ans += t
    t = temp

print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
a = []
total = 0
n,m = map(int,input().split())
for i in range(m):
    a.append(int(input()))
    if int(a[-1]) - int(a[-2]) == 1:
        print(0)

ans = total % 1000000007
print(ans)

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:
def fb(n):
  if n > 2:
    return fb(n - 1) + fb(n - 2)
  elif n == 2:
    return 2
  elif n == 0:
    return 0
  else:
    return 1

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

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

po =[fb(B[0] - 1)]          

j = 1
for j in range(M - 1):
  po.append(fb(B[j] - B[j - 1] - 2))
  
po.append(fb(N-B[M - 1]- 1))
  
ans = reduce(lambda x,y: x * y,po)
answer = ans % 1000000007
print(answer)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[-1]
d=[]
for i in range(m):
 a.append(int(input()))
a.append(n+1)
for i in range(m+1):
 d.append(a[i+1]-a[i]-1)
ansk=1
for i in range(m+1):
 k=int(((1+5**(1/2)/2)**d[i]-(1-5**(1/2)/2)**d[i])/(5**1/2))
 ansk*=k
print(ansk%1000000007)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def stairs_count(now, goal, memo):
    if now == goal:
        return 1
    if now > goal:
        return 0

    if memo[now] != -1:
        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 = [-1 for _ 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:
import sys

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

if M = 0:
    print(fibo(N))
    sys.exit()

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import math

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

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


# a が連続しているとだめ
for i in range(M-1):
    if A[i] == A[i+1]-1:
        print(0)
        sys.exit()

# 穴同士の間隔を考えて，積を取る
d = np.zeros(M+1)

for i in range(M-1):
    d[i+1] = A[i+1] - A[i] - 2

d[0] = A[0] - 1
d[-1] = N - A[-1] - 1


p = np.zeros(M+1)

for i in range(M+1):

    n = int(d[i] // 2)

    for j in range(1,n+1):
        # 2の数 j個
        # 1の数 n1 = d - 2j
        n1 = d[i] - 2*j
        pp = math.factorial(n1+j)/(math.factorial(j) * math.factorial(n1))
        p[i] += pp

    p[i] += 1

mm = 1000000007
p = p % mm

print(int(np.prod(p) % mm))

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 total[i-1] == 0 and total[i-2] == 0:
        print(0)
        exit()
    if (i+1) not in a:
        one[i] = total[i-1]
        two[i] = total[i-2]
        total[i] = one[i]+two[i]
print(a)
print(total[-1] % 1000000007)

Submission status: Runtime Error

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

pattern=[0]*n
pattern[0]=1
pattern[1]=1
pattern[2]=2

for i in range(3, n):
    pattern[i]=2*pattern[i-2]+pattern[i-3]

judge=False
for i in range(m-1):
    if a[i+1]-a[i]==1:
        judge=True
ans=1
med=0
num=1

if judge:
    print("0")
else:
    for i in range(n):
        if i+1 in a:
            num=0
            ans*=med
    
        else:
            med=pattern[num]
            num+=1


ans*=med

print(ans)

Submission status: Runtime Error

Solution code:
def step_for_two(genzai):
    global kaisu
    for i in range(genzai + 2, N + 1, 2):
        print('step2_i', i)
        if i in break_step:
            print(i, '段目は踏んじゃだめ！')
            step_for_one(i - 1)
        if i == N:
            print('------GOAL------')
            kaisu += 1


def step_for_two_flag(genzai):
    global kaisu
    for i in range(genzai + 2, N + 1, 2):
        print('step2_i', i)
        if i + 2 not in break_step:
            step_for_one(i + 2)
        if i == N:
            print('------GOAL------')
            kaisu += 1


def step_for_one(genzai):
    global kaisu
    for i in range(genzai, N + 1):
        print('step1_i', i)
        if i in break_step:
            print(i, '段目は踏んじゃだめ！')
            step_for_two(i - 1)
        if i == N:
            print('------GOAL------')
            kaisu += 1


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

for soezi, i in enumerate(break_step):
    if break_step[soezi - 1] + 1 == i:
        print(0)
        exit()

kaisu = 0

step_for_one(0)
print('----end_one-----\n')
step_for_two_flag(0)
# step_for_two(0)
print('end_two')

print(kaisu % 1000000007)

Submission status: Runtime Error

Solution code:
def cul_num(key):
    if key == 0:
        return 0
    if key <= 2:
        return 1
    if key == 3:
        return 2
    return cul_num(key-1)+cul_num(key-2)+1

n, m = map(int, input().split())
a = []
res = 1

[a.append(int(input())) for _ in range(m)]
a.append(n+1)

for index,i in enumerate(a):
    if i == a[0]:
        res *= cul_num(i)
    else:
        res *= cul_num(i-a[index-1]-1)
    if res > 1000000007:
        res = res % 1000000007

print(res)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


N, M = map(int, input().split())
# 壊れている床番号
a = []
for _ in range(M):
    a.append(int(input()))
# ルートの総数
root = 0
# 今いる階段の段数
now = 0


def isSafe(now):
    """
    1, 2段先共になければ0
    1段先だけあれば1
    2段先だけあれば2
    1, 2段先共にあれば3
    """
    now_1 = not (now-1) in a
    now_2 = not (now-2) in a
    if now<=1:
        return 0
    elif now==2:
        return int(now_1)
    else:
        return int(now_1 + now_2*2)


@lru_cache(maxsize=1000)
def step(N):
    # N段を登る移動方法数
    if N <= 1:
        if not (1 in a):
            return 1   
        else:
            return 0
    elif N==2:
        if not (2 in a):
            return step(1) + 1
        else:
            return step(1)
    elif isSafe(N)==1:
        return step(N-1)
    elif isSafe(N)==2:
        return step(N-2)
    elif isSafe(N)==3:
        return step(N-1)+step(N-2)
    else:
        return 0

print(step(N)%1000000007)

Submission status: Runtime Error

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

flag = 0
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:
from sys import stdin
import sys
import numpy as np
from math import factorial
# [【Python】組み合わせ\(nCr\) 計算の高速化 \- Qiita](https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E6%97%A2%E5%AD%98%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E6%89%8B%E6%B3%95%EF%BC%93%E8%A9%95%E4%BE%A1-)


def get_pattern(num):
    ret = 0
    if num == 1:
        ret = 1
    else:
        for i in range(int(num / 2) + 1):
            n = num - i
            r = i
            tmp = factorial(n) / factorial(r) / factorial(n - r)
            ret = ret + tmp

    return int(ret)


if __name__ == '__main__':
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    a = [int(input()) for i in range(M)]
    a.insert(0, 0)
    a.append(N)

    ret = 0
    for j in range(M+2):
        if j == 0:
            continue
        elif a[j] - a[j-1] - 1 == 0 and a[j-1] != 0:
            ret = 0
            break
        else:
            ret = ret + get_pattern(a[j]-a[j-1]-1)

    print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
t_list = []
for _ in range(m):
  t = int(input())
  t_list.append(t)
i = 0
s_a = 0
flg = False
ans = 1
for j in range(m):
  if j < len(t_list)-1 and (t_list[j+1] - t_list[j]) == 1:
    ans = 0
    flg = True
    break
  if t_list[j] == 1 and i-2 not in t_list[j-1]:
    s_a += 1
  else:
    s_a += 2
  print(s_a)
if not flg:
  ans = 2 ** (n - s_a - m - 1)
  if ans < 1:
    ans = 1
    
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
cnt = 0
lists = []
kaidan = list(range(N+1))
ans = []
for i in range(M):
    a = int(input())
    lists.append(a)

def dfs(i):
    if i == N:
        return cnt + 1
    
    if i > N:
        return False

    if i in lists:
        return False
    
    if dfs(i+1):
        return dfs(i+1)
    
    if dfs(i+2):
        return dfs(i+2)

    return False

m = dfs(0)
print(m+m)

Submission status: Runtime Error

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

# def fib(n):
#     a, b = 0, 1
#     if n == 1:
#         return a
#     elif n == 2:
#         return b
#     else:
#         for i in range(n-2):
#             a, b = b, a + b
#         return b

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:

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

A = range(M)
B = range(M)

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(10)

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):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    else:
        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(int(roots%1000000007))

Submission status: Runtime Error

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

a = [int(input()) for i in range(M)]
dp = [0] * (N + 1)
dp[0] = 0
if 1 in a:
    dp[1] = 0
    dp[2] = 1
else:
    if 2 in a:
        dp[1] = 1
        dp[2] = 0
    else:
        dp[1] = 1
        dp[2] = 2
for i in range(3,N+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])

Submission status: Runtime Error

Solution code:
# 3
memo=dict()
def combi_memorized(n, k):
    if k * 2 > n:
        k = n - k
    if k == 0:
        return 1
    if k == 1:
        return n
    memo_key = (n, k)
    if (n, k) not in memo:
        memo[memo_key] = combi_memorized(n-1, k) + combi_memorized(n-1, k-1)
    return memo[memo_key]

import sys
sys.setrecursionlimit(10000)
N, M = (int(x) for x in sys.stdin.readline().split(' '))
a_list = [int(x) for x in sys.stdin.readlines()]

tmp_list = []
tmp_list.append(a_list[0]-1 - 0)
for i in range(1, M):
    tmp_list.append(a_list[i] - a_list[i-1]-1)
tmp_list.append(N - a_list[-1]-1)

if 0 in tmp_list[1:]:
    print(0)
    exit()
s = 0
for v in tmp_list:
    for i in range(v):
        s += combi_memorized(v-i, i)
        if s > 1000000007:
            s -= 1000000007
print(s)

Submission status: Runtime Error

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000) 

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

for i in a:
    memo[i] = 0

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

print(stair(n))

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
try:
    for x in range(3,n+1):
        kaidan[x] = kaidan[x-1]+kaidan[x-2]
        if x in a_list:
            kaidan[x]  = 0
except IndexError:
    pass
print(int(kaidan[n])%1000000007)

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%1000000007)
sum %= 1000000007
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:
N, M=map(int, input().split())
a=[int(input()) for _ in range(M)]

def func(x):
    if x==0:
        return 1
    elif x==-1:
        return 0
    else:
        return 2**(x-1)

s=func(a[0]-1)
for i in range(0, M-1):
    s*=func(a[i+1]-a[i]-2)
s*=func(N-a[M-1]-1)
print(s%1000000007)

Submission status: Runtime Error

Solution code:
import math
N,M = map(int,input().split())
a = []
flg = False

for i in range(M):
  a_ = int(input())
  a.append(a_)
  if a_ - a[i-1] == 1:
    flg = True

if flg == True:
  print(0)
else:
  before = 0
  ans = 1
  for i in a:
    step = i-before
    two = (step-1)//2
    p = 0
    if two < 1:
      p = 1
    else:
      for j in range(1,two+1):
        p += math.factorial(step-1-j)/math.factorial(j)/math.factorial(step-1-j-j)
      p += 1
      ans = ans * p
      ans = ans % 1000000007
      before = i
  step = N-before
  two = (step-1)//2
  p = 0
  if two < 1:
    p = 1
  else:
    for j in range(1,two+1):
      p += math.factorial(step-1-j)/math.factorial(j)/math.factorial(step-1-j-j)
    p += 1
  ans = ans * p
  ans = ans % 1000000007
  print(int(ans))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
f=[0]*100001
f[0]=0
f[1]=1
f[2]=2
for i in range(3,100001):
  f[i]=f[i-1]+f[i-2]
ans=max(f[a[0]-1],1)
for j in range(m-1):
  ans*=f[a[j+1]-a[j]-2]
print((ans*max(1,f[n-a[-1]-1]))%1000000007)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from functools import lru_cache


a = {-1}

@lru_cache(maxsize=None)
def near(g):
    d = 99999999
    v = g
    for i in a:
        if abs(g-i) < d:
            d = abs(g-i)
            v = i
    return v


@lru_cache(maxsize=None)
def solv1(n, g):
    if n in a:
        return 0
    if n-g == 0:
        return 1
    if n-g < 0:
        return 0
    count = 0
    if (n-2) not in a:
        count += solv1(n-2, g)
    if (n-1) not in a:
        count += solv1(n-1, g)
    return count


def solv(n, a):
    if n < 100:
        return solv1(n, 0)
    g = near(n // 2)
    if g > 15:
        return solv1(g+1, 0) * solv1(n, g+1)
    else:
        return solv1(g-1, 0) * solv1(n, g-1)


if __name__ == '__main__':

    n, m = map(int, input().split())
    for _ in range(m):
        a.add(int(input()))

    ans = solv(n, a)

    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:

N, M = map(int,input().split())
a = []
dev = 100000007

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

ans = 0
flag = True
a.append(N+1)

for i in range(M-1):
    if a[i+1] == a[i]+1:
        flag = False
        break

def fadd(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 0:
        return 0
    else:
        return fadd(n-1)%dev + fadd(n-2)%dev
    
if flag:
    
    pa = 0 
    for i,na in enumerate(a):
        print(i,na)
        ans += fadd(na - 1 - pa)%dev
        pa = na + 1

print(ans)

Submission status: Runtime Error

Solution code:
def kaidan(n):
    steps = [0] * (n+1)

    steps[1] = 1
    steps[2] = 2
    steps[3] = 3
    for i in range(4, n+1):
        steps[i] = steps[i-1] + steps[i-2] + steps[i-3]

    return steps[n]
  

a = input()
a = a.split(" ")
N = int(a[0])
M = int(a[1])

cns = []

d_list = []
for i in range(M):
    d_list.append(int((input())))
    
# print(d_list)
ddd = kaidan(N)
for i  in(d_list):
    an = kaidan(i)
    bn  = kaidan(N+1-i)
    cn = an* bn -2
    cns.append(cn)
    
print(ddd - sum(cns))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
bre = []
flag = 0
A = []
for i in range(M):
    bre.append(int(input()))
#print(bre)
A.append(bre[0] - 1)
count = 0
if len(bre) >= 2:
    for i in range(len(bre) - 1):
        a = bre[i + 1] - bre[i]
        A.append(a - 2)
        if a == 1:
            #print(0)
            flag = 1
A.append(N - bre[len(bre) - 1] - 1)

if flag == 0:
    suu = [0, 1, 2]
    for i in range(2, max(A)+1):
        suu.append(suu[i] + suu[i-1] )
    #print(suu)
    for i in A:
        if count == 0:
            count = suu[i]
        else :
            count *= suu[i]
            count = count % 1000000007
    print(count)

Submission status: Runtime Error

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

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

if flag >= 1:
    print(0)
    exit()

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

ans = total % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np



def main(N, M, a_list):
    fib_memo = {}
    fib_memo[0] = 1
    fib_memo[1] = 1
    def fib(n):
        if n not in fib_memo:
            fib_memo[n] = fib(n-1) + fib(n-2)
        return fib_memo[n]

    mul = 1
    old_a = 0

    for a in a_list:
        if a != 1 and old_a == a - 1:
            print(0)
            return

        mul *= (fib(a - old_a - 1) % 1000000007)
        old_a = a
        

    mul *= (fib(N - a_list[-1] -1) % 1000000007)
    print(mul % 1000000007)




if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lst = [int(input()) for i in range(m)]
slst = []
cnt = 1

for i in range(m):
  if len(slst) == 0:
    slst.append(list(range(0,lst[i])))
  else:
    slst.append(list(range(lst[i-1]+1,lst[1])))
slst.append(list(range(lst[-1]+1,n+1)))
#print(slst)
for i in slst:
  if len(i) == 1:
    cnt*=1
  elif len(i) == 2:
    cnt*= 2
  elif len(i) == 3:
    cnt*= 3
  elif len(i) == 4:
    cnt*= 4
  elif len(i) == 5:
    cnt*= 7
  elif len(i) == 6:
    cnt*= 12
print(cnt)
"""
  for j in range(len(i)//2+1):
    tmp = [[2]*j+[1]*(len(i)-2*j)]
    plst = list(permutations(tmp))
    print(plst)
"""

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%1000000007)
sum %= 1000000007
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:
n, m = [int(i) for i in input().split()]
a = [-1]

MAX = 100000
MOD = 1000000007
fac = [1 for i in range(MAX)]
finv = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def COM(n , r):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r]* finv[n-r]%MOD)%MOD

for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += COM(k-i, i)
    ans = ans * cnt % 1000000007
    if ans == 0:
        break

print(int(ans))

Submission status: Runtime Error

Solution code:
#coding:utf-8
from math import *
def fib(n):
    return round(( ((1 + sqrt(5))/2)**n - ((1 - sqrt(5))/2)**n ) / sqrt(5))
F = 10001
MD = 1000000007
ls = [0,1]
for f in range(F-2):
    s = sum(ls[-2:])
    ls.append(s)
def fib2(n):
    return ls[n]
old_a = 0
diff = []
N,M = map(int, input().split())
for m in range(M):
    a = int(input())
    if a-old_a==1 and old_a != 0:
        print (0)
        exit()
    diff.append(a-old_a)
    old_a = a
diff.append(N - old_a)
    
#print (diff)
ans = 1
for i,d in enumerate(diff):
    if i!=0 and i!=len(diff)-1:
        d-=1
    ans *= fib2(d)
    #ans %= 1000000007
print (ans % MD)
#print (ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())

a = []

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


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)


for i in range(1, len(a)):
    sa = a[i] - a[i - 1]
    if sa == 1:
        print("0")
        exit()

a2 = []
for i in range(len(a)):
    if i == 0:
        a2.append(fib_memo(a[i]))
    elif i == (len(a) - 1):
        a2.append(fib_memo(a[i] - a[i - 1]))
    else:
        a2.append(fib_memo(a[i] - a[i - 1]) - 1)

print(np.prod(a2) % 1000000007)

Submission status: Runtime Error

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

n, m = map(int, raw_input().split())
a_arr = []
stock_arr = []

for idx in range(0, m):
  a_arr.append(int(raw_input()))
for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print(true_ans)

Submission status: Runtime Error

Solution code:

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

Ans = reduce(lambda a, b: a*b, B)
# Ans = 10
print(Ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

a_s = []
flag = False

for i in range(M):
    a_m = int(input())
    a_s.append(a_m)
    if(i > 0 and a_m == a_s[i-1]+1):
        flag = True
        print(0)
        break


if not flag:
    way = 1
    now = 0
    for a in a_s:
        # print("a = " + str(a))

        step = a - 1 - now
        # print("now = " + str(now))
        # print("step = " + str(step))
        w = 0
        for i in range(step//2+1):
            # print(str(step-i) + " C " + str(i))
            # print (scm.comb(step-i, i))
            w += comb(step-i, i)
        if(w != 0):
            way = w * way
        now = a+1
        # print(w)

    step = N - now
    # print("way = " + str(way))
    w = 0
    for i in range(step//2+1):
        # print(str(step-i) + " C " + str(i))
        # print (scm.comb(step-i, i))

        w += comb(step-i, i)
    # print("w = " +str(w))
    if(w != 0):
        way = w * way

    print(int(way % 1000000007))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
As = []
for i in range(M):
    As.append(int(input()))
As.sort()
Ds = []
if M==0:
    Ds.append[N+1]
else:
    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:
from scipy.special import comb

N,M= map(int, input().split())
aList = [0] * M
for i in range(M):
    aList[i] = int(input())

aList.sort()
aList.append(N+1)

result = 1
MOD = 7+10**9
now = 0
for a in aList:
    if now == a:
        result = 0
        break

    x = (a - now - 1)
    root = 1
    for i in range(x//2, x):
        root += int(comb(x, (x-i+1), exact = False))
    result = result * root
    result = result % MOD
    now = a+1
print(result)