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: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
a = hi(m)
aset = set(a)
dp = [0] * (n + 1)
dp[0] = 1
if 1 not in aset:
    dp[1] = 1

for i in range(2, n + 1):
    if i - 1 not in aset:
        if i - 2 not in aset:
            dp[i] = dp[i - 1] + dp[i - 2]
        else:
            dp[i] = dp[i - 1]
    else:
        if i - 2 not in aset:
            dp[i] = dp[i - 2]
        else:
            pass
    dp[i] %= mod
print(dp[n] % mod)

Submission status: Accepted

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


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

        if i != n-1 and dp[i+2] != -1:
            dp[i+2] += dp[i] % mod

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
n,m = [int(_) for _ in input().split()]
a = {int(input()) for _ in range(m)}
dp = [0 for _ in range(n+1)]
dp[0] = 1
mod = int(1e9+7)
for i in range(1,n+1):
    if i-1 not in a:
        dp[i] += dp[i-1];dp[i] %= mod
    if i >= 2 and i-2 not in a:
        dp[i] += dp[i-2];dp[i] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[0]*(N+2)
b=[0]*(M+2)
c=[0]*(M+2)
a[0]=0
a[1]=1
a[2]=1
for i in range(3,N+2):
    a[i]=a[i-1]+a[i-2]
if M==0:
    print(a[N+1]%1000000007)
else:
    b[0]=-1
    b[M+1]=N+1
    way=1
    for i in range(1,M+1):
        b[i]=int(input())
        c[i]=b[i]-b[i-1]-1
        way=(way*a[c[i]])%1000000007
    c[M+1]=b[M+1]-b[M]-1
    way=(way*a[c[M+1]])%1000000007
    print(way)

Submission status: Accepted

Solution code:
def cmb(n, r):
    return fct[n] * inv[r] * inv[n - r] % md

md = 10 ** 9 + 7
n, m = map(int, input().split())
ans = 1
pa = -1
ds = []
for _ in range(m):
    a = int(input())
    if a == 1:
        pa = 1
        continue
    d = a - pa-2
    if d == -1:
        print(0)
        exit()
    ds.append(d)
    pa = a
ds.append(n - pa-1)
#print(ds)
mxd = max(ds)
fct = [1, 1]
inv = [1] * (mxd + 1)
s = 1
for i in range(2, mxd + 1):
    s = (s * i) % md
    fct.append(s)
inv[-1] = s = pow(fct[-1], md - 2, md)
for i in range(mxd, 1, -1):
    s = s * i % md
    inv[i - 1] = s
for d in ds:
    tmp = 0
    for i in range(d // 2 + 1):
        tmp = (tmp + cmb(d - i, i)) % md
    ans = (ans * tmp) % md
print(ans)

Submission status: Accepted

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

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    a_list.pop(0)
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            a_list.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now
        if i+1 in a_list:
            a_list.pop(0)
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM
    if step_now ==  step_1 == step_2 == 0:
        break

print(step_now)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for i in range(N+1)]
b = [0 for i in range(N+1)]
dp[0] = 1
for i in range(M):
    b[a[i]] += 1
for i in range(1,N+1):
    if b[i] == 1:
        dp[i] = 0
        continue
    elif i == 1:
        dp[i] = 1
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])

Submission status: Accepted

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

#連続する壊れていない階段の数を求める
li_new = [-1]*(m+1)
li_new[0] = li[0]
for i in range(1,m):
    li_new[i] = li[i] - (li[i-1]+1)
li_new[m] = n - li[m-1]
#print(li_new)

#必用な部分までのフィボナッチ数をリストに保存
fib = [0] * (max(max(li_new)+2,3))
fib[0] = 0
fib[1] = 1
fib[2] = 1
for i in range(3,max(li_new)+2):
    fib[i] = fib[i-2] + fib[i-1]
#print(fib)

#連続する壊れていない階段の数ごとのフィボナッチ数の積
ans = 1
if m > 0:
    for i in li_new:
        ans *= fib[i]
else:
    ans = fib[n+1]
print(ans%1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

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

tmp = [1, 2]
for i in range(10 ** 5):
    tmp.append(tmp[-1] + tmp[-2])

ans = 1
before = -1
if m != 0:
    for i in range(m):
        step = a[i] - before - 2
        if step == -1:
            ans = 0
            break
        elif step > 0:
            ans = ans * tmp[step-1]
            ans = ans % 1000000007

        before = a[i]

# final steps
step = n - before - 1
if step > 0:
    ans *= tmp[step-1]
    ans = ans % 1000000007

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())
a = []
buf = -111
for q in range(m):
  a.append(int( raw_input() ))
  buf = a[q]
  if buf - a[q] == 1:
    print 0
    exit(0)

if n==1:
  print 1
  exit(0)
if n==2:
  if m==1:
    print 1
    exit(0)
  if m==0:
    print 2
    exit(0)

now = [-1]*100001

if m == 0:
  now[0] = 1
  now[1] = 1
  for q in range(2,n+1):
    now[q] = (now[q-1] + now[q-2]) % 1000000007
  print now[q] % 1000000007
  exit(0)
    
now[0] = 1
if a[0] == 1: now[1] = 0
else: now[1] = 1

for q in a:
  now[q] = 0

for q in range(2,n+1):
  if now[q] != -1: continue
  now[q] = (now[q-1] + now[q-2]) % 1000000007
  
print now[q] % 1000000007

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  # 整数列に変換



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)

Submission status: Accepted

Solution code:
mod = 1000000007
N, M = map(int, input().split())
A = list(set([int(input()) for _ in range(M)]))
M = len(A)
for i in range(M-1):
    if A[i] + 1 == A[i+1]:
        print(0)
        exit()

check = [0]*(N+2)
for i in range(M):
    check[A[i]] = 1
    check[A[i]+1] = 1
    check[A[i]+2] = 1

dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
i = 2
while i <= N:
    if check[i]:
        dp[i] = dp[i-1]    
        i += 1
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
        i += 1
print(dp[N])

Submission status: Accepted

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        if i == 0 and len(broken_lst) != 0:
            if broken_lst[0] == 2 and next_broken == 1:
                continue
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**7)
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()]
if (M != 0):
    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)
else:
    span_list = [N]
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: Accepted

Solution code:
N, M = map(int, input().split())
broken = [int(input()) for i in range(M)]
broken.append(N+1)
safe = []
i = 0
j = 0
temp = 0

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

while i != N+2:
    if i < broken[j]:
        temp += 1
        i += 1
    else:
        safe.append(temp)
        temp = 0
        i += 1
        if j < len(broken)-1:
            j += 1
        else:
            break
     

ans = 1
i = 0
for i in range(len(safe)):
    ans = ans * fb(safe[i])

safe2 = [str(i) for i in safe]

if safe2.count('0') != 0:
    print(0)
else:
    print(ans%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
al=[int(input()) for i in range(m)]+[n+1]
mod=1000000007
ms=[0]*(n+1)

def dd(n):
    if ms[n]>0:
        return ms[n]
    if n==1:
        ms[n]=1
        return 1
    if n==2:
        ms[n]=2
        return 2
    m=dd(n-1)+dd(n-2)
    ms[n]=m
    return m

ans=1
now=0
b=-1
for a in al:
    if a-1==b:
        print(0)
        exit()
    b=a
    if a-1!=now:
        ans=(ans%mod)*(dd(a-now-1)%mod)%mod
    now=a+1

print(ans)

Submission status: Accepted

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]*110000
    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)

    if m == 0:
        print(dp[n+1])
    else:
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def fib_memo(n):
    if n <= 1:
        return 1
    memo = [0] * n
    memo[0] = 1
    memo[1] = 2
    for i in range(2, n):
        memo[i] = (memo[i - 1] + memo[i - 2]) % PRIME
    return memo[n-1]

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib_memo(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib_memo(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)  # RecursionError対策

def fibonacci(n):
    if n == 0:
        return 0 # F0
    elif n == 1:
        return 1 # F1
    return fibonacci_sub2(n-2, 1, 0) #F2以降

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())
a = [int(input()) for i in range(M)]
a.append(N+1)
anser = 1
start = 0
for i in range(M+1):
    Bre = a.pop(0)
    if Bre == start:
        anser = 0
        break
    anser = anser * fibonacci(Bre - start + 1)
    start = Bre + 1

print(anser % 1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

def memoize(f):
  table = {}
  def func(*args):
    if not args in table:
      table[args] = f(*args)
    return table[args]
  return func

@memoize

def step(n):
  if n==0:
    return(1)
  elif n==1:
    return(1)
  else:
    return((step(n-1)+step(n-2))%1000000007)

if M==0:
  print(step(N))
else:
  b = [0]*(M+1)
  b[0] = step(a[0]-1)
  if M>=2:
    for i in range(M-1):
      if a[i+1]-a[i] == 1:
        b[i+1] = 0
      else:
        b[i+1] = step(a[i+1]-a[i]-2)
  b[M] = step(N-a[M-1]-1)

  answer = 1
  for i in range(M+1):
    answer = answer*b[i]%1000000007
  print(answer)

Submission status: Accepted

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

Submission status: Accepted

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


def count_steps(NN):

    steps = [0] * (NN + 3)
    steps[1] = 1
    steps[2] = 2
    for i in range(3, NN + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
    return steps[NN]

if m == 0:
    ans = count_steps(n)
else:
    if a[0] == 1:
        ans = 1
    else:
        ans = count_steps(a[0] - 1)

    for i in range(1, len(a)):
        temp = a[i] - a[i - 1] - 2
        if temp < 0:
            ans = 0
        elif temp == 0:
            ans *= 1
        else:
            ans *= count_steps(temp)

    temp = n - a[-1] - 1
    if temp > 0:
        ans *= count_steps(temp)
print(ans%1000000007)

Submission status: Accepted

Solution code:
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
    
a = []
N, M = map(int, input().split())
for i in range(M):
    a.append(int(input()))

results = []

flag = True

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

flag_end = True
if M == 0:
    flag_end = False

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

if flag and flag_end:
    for m in range(M):
        if m == 0:
            results.append(Fib(a[m] + 1))
        else:
            results.append(Fib(a[m] - a[m - 1]))
    results.append(Fib(N - a[m] + 1))
    result = 1
    for i in range(len(results)):
        result = mul(result, results[i])
    print(result % mod)
elif not flag:
    print(0)
else:
    print(Fib(N + 2) % mod)

Submission status: Accepted

Solution code:
import re
import math

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())
step = ['0']*(n+1)
for i in range(m):
    a = int(input())
    step[a] = '1'
steps = ''.join(step)

a = re.findall('000*', steps)
b = len(re.findall('11', steps))
# print(steps)
count = 1
for i in a:
    count *= fib(len(i)+1) % 1000000007

if b != 0:
    print(0)
else:
    print(count % 1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")

fib_memo = [-inf for i in range(n+1)]
fib_memo[0] = 1
if 1 in a:
    fib_memo[1]=0
else:
    fib_memo[1]=1
for i in a:
    fib_memo[i]=0

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if fib_memo[cur_fib_i]==0:
            pass
        else:
            fib_memo[cur_fib_i] = fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2]
        cur_fib_i += 1
print(fib_memo[n]%1000000007)
#print(fib_memo)

Submission status: Accepted

Solution code:
import sys

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

sys.setrecursionlimit(N * 10)

Z = 1000000007

for _ in range(M):
    a = int(input())
    A.add(a)


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


def d(n):
    if n < 1:
        return 0
    if n in A:
        B[n] = 0
        return 0

    if B[n] != -1:
        return B[n]
    if n == 1:
        return 1
    if n == 2:
        if 1 in A:
            return 1
        return 2

    if n - 1 in A and n - 2 in A:
        return 0

    if n - 1 in A:
        B[n] = d(n-2)
        return B[n]

    if n - 2 in A:
        B[n] = d(n-1)
        return B[n]

    B[n] = (d(n-2) + d(n-1)) % Z
    return B[n]


print(d(N))

Submission status: Accepted

Solution code:
def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**9)

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)
    
if m == 0:
    print(countWays_memo(n)% 1000000007)
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    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: Accepted

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

mod = 10 ** 9 + 7

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


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

Submission status: Accepted

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

MOD = 10 ** 9 + 7
a = []
flag = True
for i in range(M):
  tmp = int(input())
  if i != 0 and tmp == a[-1] + 1:
    print(0)
    flag = False
    break
  a.append(tmp)

if flag:
  max_dis = 0
  dis = []
  for i in range(len(a)):
    if i == 0:
      dis.append(a[i])
    else:
      dis.append(a[i] - a[i - 1] - 1)
    max_dis = max(max_dis, dis[-1])
  if M == 0:
    max_dis = N
    a.append(-1)
  else:
    max_dis = max(max_dis, N - a[-1])
  
  fib = [1, 1]
  for _ in range(max_dis):
    fib.append((fib[-1] + fib[-2]) % MOD)
  ans = 1
  for d in dis:
    ans = (ans * fib[d - 1]) % MOD
  ans *= fib[N - a[-1] - 1] % MOD
  
  print(ans % MOD)

Submission status: Accepted

Solution code:

stair, bre_num = list(map(int,input().split()))
bre_stairs = []
mae = -1
dekiru = True
for _ in range(bre_num):
	b = int(input())
	if b-mae==1:
		dekiru = False
	bre_stairs.append(b)
	mae = b

bre_stairs.insert(0,-1)
bre_stairs.append(stair+1)

sosu = 1

def Fib(n):
    a, b = 1, 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

if dekiru:
	for saki,ato in zip(bre_stairs[1:],bre_stairs[:-1]):
		pat = saki-ato-1
		sosu = sosu * Fib(pat)
	print(sosu % 1000000007)

else:
	print(0)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
aa = [False]*(N+1)
for _ in range(M):
    a = int(input())
    aa[a] = True

dp = [1]*(N+1)
if aa[1]:
    dp[1] = 0

for i in range(2,N+1):
    if aa[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2]) %mod

print(dp[-1]%mod)

Submission status: Accepted

Solution code:
import sys

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

steps = [0, 1, 2]
for i in range(3, N+1):
    steps.append(steps[i-1] + steps[i-2])
  
if M == 0:
    print(steps[N] % 1000000007)
    sys.exit()
    
As = []
for i in range(M):
    As.append(int(input()))
    
deffs = []

if As[0] != 1:
    deffs.append(As[0] - 1)
else:
    deffs.append(1)

for i in range(1, M):
    d = As[i] - As[i-1] -2
    if d == 0:
        deffs.append(1)
    elif d == -1:
        deffs.append(0)
    else:
        deffs.append(d)

if N - As[M-1] - 1 != 0:
    deffs.append(N - As[M-1] - 1)
else:
    deffs.append(1)

ans = 1

for i in range(len(deffs)):
    ans *= steps[deffs[i]]
    
print(ans % 1000000007)

Submission status: Accepted

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

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

if M == 0:
    B = []
    B.append(N+1)
elif M == 1:
    B = []
    B.append(A[0])
    B.append(N - A[0])

else:
    B = [A[0]]
    for i in range(M-1):
        B.append(A[i+1] - A[i] - 1)
    B.append(N - A[M-1])


ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)

Submission status: Accepted

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

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

def is_enabled():
    _a = -1
    for a in A:
        if _a + 1 == a:
            return False
        _a = a
        
    return True


X =[1, 2]
BAD = [-1] + A + [N+1]

def pattern(a, b):
    a_b = b-a
    if a_b == 0:
        return 1
    if len(X) >= a_b:
        return X[a_b-1]
    else:
        while len(X) <= a_b:
            X.append(X[-1]+X[-2])
        return X[a_b-1]


if is_enabled() == False:
    print(0)
else:
    ans = 1
    for a, b in zip(BAD[:-1], BAD[1:]):
        ans *= pattern(a+1, b-1)
        
    ans = ans %  1000000007
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

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

for k in a:
	tmp.append(fib(k - start) % INF)
	start = k + 1

for j in tmp:
	ans *= j
	ans %= INF

ans *= fib(N - start + 1)
print(ans % INF)

Submission status: Accepted

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

amari = 1000000007
cnt = [0]*(N+2)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+2):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
def calc(ans):
    if M == 0:
        return cnt[N+1]

    for i in range(M): 
        if i == 0:
            ans*= cnt[A[i]]
        elif i > 0 and i < M:
            ans*=cnt[A[i] - A[i-1]-1]

        if i == M-1:
            ans*= cnt[N - A[i]]
        
        if ans == 0:
            break
    
        ans %= amari
        
    return ans

print(calc(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)%1000000007

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


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%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,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

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

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

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

l = [-1] * (n + 1)
l[n] = 1
l[n-1] = a[n-1]

num = n - 2
while num >= 0:
    if a[num] == 1:
        l[num] = (l[num+1] + l[num+2]) % mod
    else:
        l[num] = 0
    num -= 1

print(l[0])

Submission status: Accepted

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


def func(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)%1000000007 + _fib(n-2)%1000000007
        return memo[n]

    return _fib(n)

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

Submission status: Accepted

Solution code:
def calcPatt(steps):
    if steps <= 1:
        return 1
    elif steps == 2:
        return 2
    ll = {}
    # ここからは3以上
    for i in range(steps)[::-1]:
        if i + 1 == steps:
           ll[i] = 1
        elif i + 2 ==steps:
            ll[i] = 2
        else:
            ll[i] = ll[i+1] + ll[i+2]
    
    return ll[0]

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

before = 0
f = True
ll = []
ax = {}
for i in range(M):
    # 上っていい段数を取得
    a = int(input())
    ax[i] = a
    limit = a - 1
    stepRenge = limit  - before
    #print("before:{}/limit:{}/break:{}/step:{}".format(before,limit,a,stepRenge))
    if not f and stepRenge == -1:
        ll.append(0)
        break
    ll.append(calcPatt(stepRenge))
    before = limit + 2
    f = False
    

# 最後の一回分が残ってるのでやる
stepRenge = N  - before
ll.append(calcPatt(stepRenge))

pro = 1
for i in ll:
    pro = (pro * i) % 1000000007
 
print(pro)

Submission status: Accepted

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

cur_step = 0
steps = []
ans = 1
for a in A:
	if a-cur_step == 0:
		ans = -1
		break
	if a == 1:
		steps.append(1)
		cur_step = 2
		continue
	steps.append(a-1-cur_step)
	cur_step = a+1
#ごり押しパターン計算
pat = [1,2]
inf = 10**9+7
while len(pat) < max(steps):
	pat.append((pat[-1]+pat[-2])%inf)

if ans == -1:
	print(0)
else:
	for step in steps:
		if step == 0:
			continue
		ans = (ans*pat[step-1])%inf
	print(ans)