Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    maxdif = 0
    a = []
    for _ in range(m):
        a.append(im.inputSingle())
        if len(a) >= 2:
            maxdif = max(maxdif, a[-1] - a[len(a)-2])
    MOD = 1000000007
    # Logic ############################################################################################################
    idx = 0
    total = 1
    fib = fibonacci(maxdif + 1)
    for ai in a:
        if idx - 1 == ai and idx != 0:
            print()
            continue
        if (ai - idx) == 0 and idx != 0:
            print(0)
            return
        total *= fib[ai - idx - 1]
        idx = ai+1
    total *= fib[n - idx]
    # Output ###########################################################################################################
    print(total % MOD)
    # Return ###########################################################################################################
    return

def fibonacci(n):
    fib = [1, 1]
    for _ in range(n - 1):
        fn_1 = fib[len(fib)-1]
        fn_2 = fib[len(fib) - 2]
        fib.append(fn_2 + fn_1)
    return fib

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
cache = {1: 1, 2: 2}


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


N, M = map(int, raw_input().split())
prev_a = long(-1)
ans = long(1)
for i in range(0, M):
    a = long(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 = 0
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 1
checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

for i in range(3, n):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)

Submission status: Runtime Error

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

dp=[0]*(n+1)
dp[0]=1

for i in range(1,n+1):
    if i in a:
        dp[i]=0
        continue
	if dp[i]==d[i-1]==0:break
    dp[i]=dp[i-1]
    if i>1:dp[i]+=dp[i-2]
    dp[i]%=1000000007
print(dp[-1])

Submission status: Runtime Error

Solution code:
from math import factorial
import math
def cmb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for i in range(M)] + [N + 1]

    d = [0] * (len(A) - 1)
    for i in range(len(A) - 1):
        if A[i+1] - A[i] == 1:
            print(0)
            exit(0)
        d[i] = A[i+1] - 1 - (A[i] + 1)

    ans = 1
    for dd in d:
        if dd > 1:
            tmp = 0
            for j in range(math.ceil(dd/2) + 1):
                tmp += cmb(dd - j, j)
            ans *= tmp

    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

N, M = [int(x) for x in input().split()]
a_list = [int(input()) for _ in range(M)]
span_list = [a_list[0]-1]
for i, a in enumerate(a_list[:-1]):
    if (a_list[i+1] - a) == 1:
        print(0)
        exit()
    else:
        span_list.append(a_list[i+1] - 2 - a)
span_list.append(N - a_list[-1] -1)
max_span = max(span_list)
for i in range(max_span+1):
    calc(i)
ans = 1
for span in span_list:
    ans = (ans * lst[span]) % (10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys

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
        tmp2 = 1
        for j in range(i):
            tmp2 *= n - j
        for j in range(i):
            tmp2 /= j + 1
        tmp += tmp2

    return tmp


for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        print(0)
        sys.exit()

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

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

Submission status: Runtime Error

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

if m == 0:
    x = [999999]

a = [1,1]
if x[xi] == 1:
    xi += 1
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)

Submission status: Runtime Error

Solution code:
LARGE = 1000000007


def step(a, i):
    if i == len(a):
        return 1
    elif i > len(a):
        return 0

    elif a[i] == 0:
        return 0

    return step(a, i + 1) + step(a, i + 2)


def solve():
    n, m = [int(x) for x in input().split()]
    a = [1] * n
    for _ in range(m):
        a[int(input()) - 1] = 0

    # print(n, m)
    # print(a)
    ans = 0
    # ans = step(a, 0)

    f = [0] * n
    if a[0] == 0:
        f[0] = 0
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 1
    else:
        a[0] = 1
        if a[1] == 0:
            f[1] = 0
        else:
            f[1] = 2

    if a[1] == 0:
        f[1] = 0

    # print(f)
    for i in range(2, n):
        # print(i)
        if a[i]:
            f[i] = (f[i-1] + f[i-2]) % LARGE
    # print(f)
    print(f[n-1])


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys


n,m = map(int, input().split())
steps = [True] * (n+1)
for i in range(m):
    steps[int(input())] = False

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


ans = 1

l = 0
r = 0
idx = 0
while l < len(steps):

    if idx >= len(steps):
        ans *= dp[r-l]
        break

    if steps[idx]:
        r = idx
    else:
        # idx段目が壊れてる
        #次も壊れてるなら終わり
        if steps[idx+1] == False:
            print(0)
            exit()
        else: 
            ans *= dp[r-l]
            l = idx+1
            r = idx+1
    idx += 1

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

Submission status: Runtime Error

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

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [0] * (total + 1)
dp[0] = 1
dp[1] = 1

for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) % (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7


def Fib(n, memo={}):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n] % mod
    else:
        memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo)
        return memo[n] % mod


A = list(int(input()) for i in range(m))


if m > 0:
    ans = Fib(A[0] + 1) % mod
    for i in range(m - 1):
        ans *= Fib(A[i + 1] - A[i])
        ans %= mod
        if A[i] + 1 == A[i + 1]:
            print(0)
            exit()
    ans *= Fib(n - A[-1] + 1)
    ans %= mod
else:
    ans = Fib(n + 2) % mod
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = []
for _ in range(M):
  S.append(int(input()))
S.append(-1)
S.append(N+1)
S.sort()  
P = 1

def Fib(n):    
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return Fib(n-1)+Fib(n-2)
      
for i in range(M+1):
  P *= Fib(S[i+1]-S[i]) 

print(P%1000000007)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

def culcC(num):
    if num  < 2:
        return 1
    ret = 1
    minus2 = 1
    while(True):
        ret += int(comb(num - minus2,minus2 if minus2 >0 else 1,exact=True))
        minus2 += 1
        if num - 2 * minus2 < 0:
            break
    return ret
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

if n == 1:
    print(1)
else:
    ans = 1
    stand = 0
    for i,a in enumerate(aa):
        
#        連続穴
        if stand == a:
            ans = 0
            break
            
        step_num = a - stand - 1
        ans *= culcC(step_num)
        stand = a + 1
#         print(step_num,ans,stand)
        
    # 最後のaからnまでで計算
    ans *= culcC(n - aa[-1] - 1)
    
    print(ans % 1000000007)

Submission status: Runtime Error

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

def com(x):
    cnt = 0
    for i in range(x+1):
        for j in range(x//2+1):
            if i + j*2 == x:
                cnt += 1
    return cnt

list_diff = []

for i in range(M):
    if i == 0:
        list_diff.append(list[i]-1)
    else:
        list_diff.append(list[i]-list[i-1]-2)

if list[-1] != N:
    list_diff.append(N-list[-1]-1)

ans = 1

for i in list_diff:
    if i == 0:
        pass
    else:
        ans *= com(i)

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 1
checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

if(n >= 3):
    for i in range(3, n):
        checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)

Submission status: Runtime Error

Solution code:
import sys  
import numpy as np
input = sys.stdin.readline

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

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

sq = []
for k in range(M+1):
    if k == 0:
        sq.append(a[k])
    
    elif k == M:
        sq.append(N-a[k-1])

    elif a[k] == a[k-1] -1:
        sq.append(0)
    
    else:
        sq.append(a[k] - a[k-1]-1)

ans = 1
for p in sq:
    if p == 0:
        ans *= 0
    else:
        q = int((1/np.sqrt(5))*  ( ((1+np.sqrt(5))/2)**p -  ((1-np.sqrt(5))/2)**p  ))
        ans *= q
        ans = ans%1000000007


print(int(ans)%(1000000007))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = 0
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
    break
  else:
    x = a[i+1]-a[i]-1
    if x == 0 or x == 1:
      ans = ans%1000000007
    elif x == 2:
      ans = ans*2%1000000007
    else:
      ans = 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 = map(int, input().split())

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


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

dp = [0] * (N + 1)

if N == 1 and M != 1:
    print(1)
elif N == 1 and M == 1:
    print(0)

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 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:
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 = list(map(int, input().split()))
B = [0]*(M-1)
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 = [int(input()) for _ in range(M)]

sumList = [0] * (N+1)
sumList[0] = 0
sumList[1] = 1
sumList[2] = 2
for i in range(3, N+1) :
    sumList[i] = sumList[i-1] + sumList[i-2]

ans = 0
if a[0] == 1 :
    ans = 1
else :
    ans = sumList[a[0] - 1]
for i in range(1, M) :
    if a[i] - a[i-1] == 1 :
        ans = 0
    else :
        ans *= sumList[a[i] - 2 - a[i-1]]
if N - a[M-1] != 1 :
    ans *= sumList[N - 1 - a[M-1]]
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
cache = {1: 1, 2: 2}


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


N, M = map(int, raw_input().split())
prev_a = long(-1)
ans = long(1)
for i in range(0, M):
    a = long(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 = 0
    elif prev_a != N:
        ans = ans * calc(N - prev_a - 1)
    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
import math

def fb(num):
    a, b = 1, 0
    for _ in range(num-1):
        a, b = a + b, a
    return a


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

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

ans = 1
for j in range(len(a)-1):      
    if a[j+1] - a[j] - 1 == 0:
        print("0")
        sys.exit()
        
    ans *= fb(a[j+1] - a[j] - 1)
    if ans > 1000000007:
        ans = ans % 1000000007

if a[0] > 1:
    ans *= fb(a[0])

if n - a[m-1] - 1 == 0:
    print("0")
    sys.exit()
        
ans *= fb(n - a[m-1])
print(ans % 1000000007)

Submission status: Runtime Error

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

fib_l = [-1] * (n+2)

def fib(step):
    if step < 0:
        return 0
    if fib_l[step] != -1:
        return fib_l[step]
    if 0 <= step <= 1:
        return 1
    else:
        t = fib(step-1) + fib(step-2)
        fib_l[step] = t
        return t

ret = 1
for i in range(m+1):
    ret *= fib(a[i+1] - a[i] - 2)
print(ret % 1000000007)

Submission status: Runtime Error

Solution code:
def step(n, memo={}):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    elif n in memo:
        return memo[n]
    else:
        memo[n] = (step(n-1,memo)+step(n-2,memo))%1000000007
        return memo[n]

N, M = map(int, input().split())
a = [-1]

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

else:
    for m in range(M):
        a.append(int(input()))
        if a[m+1] - a[m] == 1:
            print(0)
            break
    else:
        a.append(N+1)
        ans = 1
        for m in range(M+1):
            ans = (ans*(step(a[m+1]-a[m]-2)))%1000000007
        print(ans)

Submission status: Runtime Error

Solution code:
import math

#n = int(input())
n, m = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for n in range(n)]
#list = [int(i) for i in input().split()]
#s = input()
#list = list(s)

s = [int(input()) for i in range(m)] #m行1列入力

MOD = 1000000007

fib_memo = {}
def fib(n):
    if n == 0: return 0
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2) % MOD
    return fib_memo[n]

kotae = 1

if (m == 0) :
    kotae = (kotae * fib(n)) % MOD
else :
    for i in range(m + 1) :
        if (i == 0) :
            kotae = kotae * fib(s[i]) % MOD
        elif (i == m) :
            kotae = kotae * fib(n - s[i-1]) % MOD
        else :
            kotae = kotae * fib(s[i] - s[i-1] - 1) % MOD


print(kotae)

Submission status: Runtime Error

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

a = [1,1]
if x[xi] == 1:
    xi += 1
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)

Submission status: Runtime Error

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result




N,M = input().split()

N = int(N)
M = int(M)

a = []
ans = 1

for i in range(M):
    newa = int(input())
    a.append(newa)


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

    if (i == 0):
        dan = a[i] - 1
    elif (i == M):
        dan = N - a[i - 1] - 1
    else:
        dan = a[i] - a[i - 1] - 2

    abletwo = (dan - (dan % 2)) // 2
    now = 0

    for j in range(abletwo + 1):

        now += cmb (dan - j , j )
        #print (dan,"dan j",j,cmb (dan - j , j ))

    ans *= now
    #print (now)

ans = ans % 1000000007
print (ans)

Submission status: Runtime Error

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

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

memo = [0] * (n+1)

in_memo = [False] * (n+1)

memo[0] = 1
in_memo[0] = True

if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
in_memo[1] = True

def dp(num):
    if not in_memo[num]:
        if num in a:
            memo[num] = 0
        else:
            memo[num] = dp(num-1) + dp(num-2)
        in_memo[num] = True
    return memo[num]

print(dp(n)%1000000007)

Submission status: Runtime Error

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

ans = 0
def up(now):
    global ans
    if now == n:
        ans += 1
        return
    elif now > n:
        return
    
    if now+1 in a and now+2 in a:
        return
    elif now+1 in a:
        up(now+2)
    elif now+2 in a:
        up(now+1)
    else:
        up(now+1)
        up(now+2)
        
if __name__ == '__main__':
    up(0)
    print(ans % 1000000007)

Submission status: Runtime Error

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

sumList = [0] * (N+1)
sumList[0] = 0
sumList[1] = 1
sumList[2] = 2
for i in range(3, N+1) :
    sumList[i] = sumList[i-1] + sumList[i-2]

ans = 0
if a[0] == 1 :
    ans = 1
else :
    ans = sumList[a[0] - 1]
for i in range(1, M) :
    if a[i] - a[i-1] == 1 :
        ans = 0
    else :
        ans *= sumList[a[i] - 2 - a[i-1]]
if N - a[M-1] != 1
    ans *= sumList[N - 1 - a[M-1]]
print(ans % 1000000007)

Submission status: Runtime Error

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

B = [-1] + A + [N + 1]
B = [B[i + 1] - B[i] - 2 for i in range(M + 1)]

total = max(B)
dp = [0] * (total + 1)
dp[0] = 1
dp[1] = 1

for i in range(total - 1):
    dp[i + 2] = (dp[i + 1] + dp[i]) #% (10 ** 9 + 7)
        
ans = 1
for i in range(M + 1):
    ans *= dp[B[i]]
    ans %= 10 ** 9 + 7
print(ans if -1 not in B[1:] else 0)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	N, M = map(int,inputs().split())
	for i in range(M):
		a = int(inputs())
		ans = ans*count(a - b -1)
		b = a+1
	if a == N - 1:
		print(ans%1000000007)
	else:
		print(ans*count(N - a-1)%1000000007)


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

main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
a = list(range(m+2))
a[0] = 0
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
    break
  else:
    x = a[i+1]-a[i]-1
    if x == 0 or x == 1:
      ans = ans%1000000007
    else:
      ans = 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 = map(int,input().split())
As = []
for i in range(M):
	As.append(int(input()))

count = 0
def search(current):
	global count
	if current in As:
		return
	if current > N:
		return
	if current == N:
		count += 1
		return
	search(current + 1)
	search(current + 2)

search(0)
print(count % 1000000007)

Submission status: Runtime Error

Solution code:
from math import factorial

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

def comb(n,r):
  return factorial(n) / factorial(r) / factorial(n - r)

def func(a_p,a_c):
  if a_p == a_c: return 1
  num_steps = a_c - a_p
  r = 0
  result = 0
  for n in range(num_steps,0,-1):
    result += int(comb(n,r))
    r += 1
    if n <= r: break
  return result

a_p = 0
result = 1
for i in range(M):
  a_c = int(input()) - 1
  
  if a_c + 1 == a_p: 
    result *= 0
  result = ((func(a_p,a_c)%1000000007) * (result%1000000007))%1000000007
  a_p = a_c + 2
  
result = ((func(a_p,N)%1000000007) * (result%1000000007))%1000000007
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
pat = [0] * (N+1)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = [max(A[i+1] - A[i] - 2, 0) for i in range(M-1)]
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

Submission status: Runtime Error

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

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:
import sys

sys.setrecursionlimit(10000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo.get(x):
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = {}
count = dfs(0)
print(count%1000000007)

Submission status: Runtime Error

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 in a:
        hoge[i] = 0
    elif i in a and (i-1) in a:
        hoge[i] = 0
    elif i in a:
        hoge[i] = hoge[i - 2]
    elif (i-1) in a:
        hoge[i] = hoge[i - 1]
    else:
        hoge[i] = hoge[i-1] + hoge[i-2]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))

Submission status: Runtime Error

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

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


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

dp = [0] * (N + 1)
if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 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:
#!/usr/bin/env python3

from functools import lru_cache

a = {-1}


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


def solv(n):
    m = 10000
    while m < n:
        solv1(m)
        m += 10000
    return solv1(n)


if __name__ == '__main__':

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

    ans = solv(n)

    print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

n,m = map(int,input().split())
a = [-1]
for i in range(m):
  a.append(int(input()))
a.append(n+1)
  
@lru_cache(maxsize=1000)
def comb(i,k):
	factorial(k)/(factorial(i)*factorial(k-i))
'''
def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m
'''

pat = 1
for i in range(m+1):
  step = a[i+1]-a[i]-2
  patj = 0
  if(step<0):
    pat = 0
    break
  for j in range(step//2+1):
    patj += comb(step-j,j)
  patj = patj%1000000007
  pat = pat*patj%1000000007
  
print(int(pat))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

n, m = map(int, input().split())
dp = [-1] * (n + 1)
a = []
for i in range(m):
    aa = int(input())
    a.append(aa)
    dp[aa - 1] = 0
mod = 10 ** 9 + 7

dp[0] = 1
if a[0] != 1:
    dp[1] = 1
for i in range(1, n):
    if dp[i + 1] == -1:
        dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])

Submission status: Runtime Error

Solution code:
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    print(fibonacci(N-1)%1000000007)
    exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,i-preidx-1])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,N-preidx-1])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= fibonacci(val[1])
    fibsum %= 1000000007 
print(fibsum)