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:
class TypicalStairs:
    def __init__(self):
        self.N, self.M = map(int, input().split())
        self.a = []
        for i in range(self.M):
            self.a.append(int(input()))

    def combination(self):
        consecSteps = self.__consecSteps()
        fibs = self.__fibonacci(max(consecSteps))
        comb = 1

        if not self.__canClear():
            print(0)
            return

        # 連続n個続くステップは、fib(n)通り渡り方があるとみた
        # それの掛け算で、組み合わせを求められるか?
        for n in consecSteps:
            comb *= fibs[n]

        print(comb % 1000000007)

    # 連続しているステップの個数を配列に格納
    def __consecSteps(self):
        consecSteps = []
        # 開始は-1が穴だったことにする
        preNum = -1
        for a in self.a:
            consecSteps.append((a - 1) - preNum)
            preNum = a

        # 最後のステップから、直前の穴までもステップを追加
        consecSteps.append(self.N - preNum)

        return consecSteps

    # クリアできるか確かめる
    def __canClear(self):
        result = True
        preNum = -1
        # 2連続で落ちていると、クリア不可とする
        for a in self.a:
            if a - preNum != 1:
                preNum = a
            else:
                result = False
                break

        return result

    # フィボナッチ数列を計算
    def __fibonacci(self, n):
        fibs = [0, 1, 1]

        if n < 3:
            return fibs
        else:
            for i in range(2, n):
                fibs.append(fibs[i - 1] + fibs[i])

        return fibs


typicalStairs = TypicalStairs()
typicalStairs.combination()

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections


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

# def fib(n):
#     return int((1 / math.sqrt(5)) * (math.pow((1 + math.sqrt(5)) / 2, n) - math.pow((1 - math.sqrt(5)) / 2, n)))

def fib(n):
    return fib_list[n-1]


# for i in range(-10, 10):
#     print(fib(i))

N, M = map(int, sys.stdin.readline().rstrip().split(" "))
As = []
for i in range(M):
    a, = map(int, sys.stdin.readline().rstrip().split(" "))
    As.append(a)
As.append(N+1)
result = 1
current = 0
for a in As:
    diff = a - current - 1
    if diff < 0:
        print(0)
        exit(0)
    # 1: 1
    # 2: 2
    # 3: 3C0 + 2C1 = 3
    # 4: (1,1,1,1) (1,1,2) (1, 2, 1) (2, 1, 1), (2, 2): 4C4 + 3C1 + 2C2 = 1+ 3 + 1 = 5
    # 5: 5C0 + 4C1 + 3C2 = 1 + 4 + 3 = 8
    # 6: 6C0 + 5C1 + 4C2 + 3C3 = 1+5+6+1 = 13
    # 7: 7C0 + 6C1 + 5C2 + 4C3 = 1+6+10+4 = 21
    # print(current, a, fib(diff+1))
    result *= fib(diff+1)
    result %= 1000000007
    # print("res", result)
    current = a + 1
print(result)
exit(0)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())
    
cnt_1 = 1
cnt_2 = 0
for i in range(1,N+1):
    tmp = cnt_1
    if a != [] and a[0] == i:
        cnt_1 = 0
        a.pop(0)
    else:
        cnt_1 += cnt_2
    cnt_2 = tmp

print(cnt_1 % 1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import bisect

N, M = list(map(int, input().split()))
a = [0]*M
for m in range(M):
    a[m] = int(input())
a = set(a)
MOD = 10**9 + 7

def main(): 
    dp = [0]*(N+2)
    dp[0] = 1
    for n in range(1,N+1):
        if n ==1:
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-1]
                
        else:                        
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-2] + dp[n-1]
                
    #print(dp)
    print(dp[N]%MOD)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=1000000007
def Fib(n):
  a, b = 1, 2
  if n == 1 or n==0:
    return a
  elif n == 2:
    return b
  else:
    for i in range(n-2):
      a, b = b%mod, (a+b)%mod
    return b
n,m=map(int,input().split())
al=[]
zeroflag=0
fa=-1
cnt=0
for iii in range(m):
  a=int(input())
  cnt+=1
  al.append(a)
  if abs(fa-a)==1:
    zeroflag=1
  fa=a

if zeroflag==1:
  print(0)
else:
  ans=1
  if m==0:
    print(Fib(n))
  else:
    for iii in range(m):
      if iii==0:
        ans=Fib(al[iii]-1)
      if iii==m-1:
        break
      if len(al)>1:  
        num=Fib(al[iii+1]-al[iii]-2)
        ans*=num%mod
    ans*=Fib(n-al[-1]-1)%mod
    print(ans%mod)

Submission status: Accepted

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

li = []
lia = [-1]
ans = 1
mod = 1000000007

for i in range(n+10):
    if i == 0 or i == 1:
        li.append(1)
    else:
        li.append((li[i-1] + li[i-2]) % mod)

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        ans = 0
    ans %= mod

print(ans%mod)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import itertools
import bisect

INF = 10 ** 10

MODN = 1000000007

# N段の階段
# a段目の床は壊れている
N, M = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(stdin.readline().rstrip()) for _ in range(M)]

# N段目まで行く総数
dp =[0] * (N+10)

for ai in a:
    dp[ai] = -1 

dp[0] = 1

for i in range(N+1):
    if dp[i] == -1:
        continue

    one_step = i + 1
    two_step = i + 2

    if dp[one_step] != -1:
        dp[one_step] += dp[i]
        
    if dp[two_step] != -1:
        dp[two_step] += dp[i]

print(dp[N] % MODN)

Submission status: Accepted

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


nm = input().split()
n = ["o"] * (int(nm[0])+1)
for i in range(int(nm[1])):
    this_index = int(input())
    n[this_index] = "x"
n_str = "".join(n)
if "xx" in n_str:
    print(0)
    exit()

n_list = n_str.split("x")
res = 1
for i in n_list:
    res *= fib(len(i)-2)
print(res % 1000000007)

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
a = []
p = 0
max_wid = 0
if m == 0:
    max_wid = n
else:
    for i in range(m):
      b = int(input())
      a.append(b)
      if i > 0:
          max_wid = max(max_wid, b)
    max_wid = max(max_wid, n - a[m-1])

fib = [1, 1]
for i in range(max_wid):
    l = len(fib)
    fib.append(fib[l-2] + fib[l-1])
ans = 1
if m == 0:
  print(fib[n]%1000000007)
else:
  
  if a[0] == 0:
      ans *= 0
  else:
      ans *= fib[a[0]-1]
  for i in range(m-1):
      if a[i+1] == a[i] + 1:
          ans *= 0
      else:
          ans *= fib[a[i+1]-a[i]-2]
  ans *= fib[n - a[m-1]-1]
  ans %= 1000000007
  print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = { i_inpl(): True for _ in range(M)}
# for _ in range(M):
#     ai = i_inpl()
#     a.append(ai)

dp = [None] * (N+1)

dp[N] = 1
# print(dp)
for i in range(N-1, -1, -1):
    if i in a:
        dp[i] = 0
    else:
        if N-1 == i:
            dp[i] = 1
        else:
            if i+1 in a and i+2 in a:
                dp[i] = 0
            elif i+1 in a:
                dp[i] = dp[i+2]
            elif i+2 in a:
                dp[i] = dp[i+1]
            else:
                dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % 1000000007)

Submission status: Accepted

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

memo = {
    0: 1
}
queue = [0]
counter = 0
def step(height, n):
    if height + n not in memo:
        memo[height + n] = memo[height]
        queue.append(height + n)
    else:
        memo[height + n] += memo[height]


while counter < len(queue):
    # print(memo, queue, counter)
    item = queue[counter]
    counter += 1
    if item + 1 not in a and item + 1 <= N:
        step(item, 1)
    if item + 2 not in a and item + 2 <= N:
        step(item, 2)

if N not in memo:
    print(0)
else:
    print(memo[N] % 1000000007)

Submission status: Accepted

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

sum1 = 0
sum2 = 0
for i in range(n+1):
    if i == 0:
        sum1 = 1
        continue
    else:
        if A[i]==1 and i != 1:
            sum1 = sum2
            sum2 = 0
        elif i == 1:
            if A[i] == 1:
                sum1 = 1
                sum2 = 0
            else:
                sum2 = 1
        else:
            sum3 = sum1
            sum1 = sum2
            sum2 = sum3 + sum2
            #print(sum2)
print(sum2%1000000007)

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
F = [0,1]
for i in range(N):
    F.append(F[i]+F[i+1])

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

a.append(N+1)
ans = 1
for i in range(M+1):
    length = a[i+1] - a[i] - 1
    if length == 0:
        print(0)
        exit()
    else:
        ans *= F[length]

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

Submission status: Accepted

Solution code:
# 1 <= N <= 10 ** 5
# 0 <= M <= N − 1
# 1 <= a <= N - 1
N, M = map(int, input().split())

memo = {1: 1, 0: 1}
for i in range(2, int(10**5) + 1):
  memo[i] = memo[i-1] + memo[i-2]


stairs = [False for _ in range(N + 1)]
pattern = 1
prev = 0
for _ in range(M):
  a = int(input())
  sub = a - prev - 1
  if sub == -1:
    print(0)
    break
  pattern *= memo[sub]
  prev = a + 1
else:
  sub = N - prev
  pattern *= memo[sub]
  print(pattern % 1000000007)

Submission status: Accepted

Solution code:
def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n)%1000000007)

Submission status: Accepted

Solution code:
# coding: utf-8


def fib(p):
    lst = [1, 2]
    if p >= 1:
        for i in range(p - 2):
            lst.append(lst[i + 1] + lst[i])
        return lst[p - 1]
    elif p == 0:
        return 1
    else:
        print(0)
        exit()


n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
broken.insert(0, -1)
broken.append(n + 1)
ans = 1
for i in range(1, m + 2):
    ans *= fib(broken[i] - broken[i - 1] - 2)
    ans %= 1000000007


print(ans)

Submission status: Accepted

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

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

for i in range(N+1):
    if A:
        a = A[0]
    else:
        a = 0
    if len(A) >= 2:
        b = A[1]
    else:
        b = 0

    dp[i] = dp[i] % (10**9 + 7)
    if not i+1 == a:
        dp[i+1] += dp[i]
    else:
        A.popleft()
    if not i+2 == b and not i+2 == a:
        dp[i+2] += dp[i]
print(dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
dp = [-1] * (N + 10)
dp[0] = 1
dp[1] = 1
#print(dp[0])
#print(dp[1])
for i in range(M):
    dp[int(input())] = 0

for i in range(2, N + 1):
    if dp[i] == 0:
        #print(dp[i])
        continue
    
    else:
        dp[i] = dp[i - 2] + dp[i - 1]
        #print("i = " + str(i))
        #print(dp[i])

print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
b=[]
b_clone=[]

for i in range(m):
    t=int(input())
    b.append(t)
    b_clone.append(t)


ans_list=[1]

if len(b)!=0 and b[0]==1:
    b.pop(0)
    ans_list.append(0)
else:
    ans_list.append(1)

for i in range(2,n+1):
    if len(b)!=0 and i==b[0]:
        b.pop(0)
        ans_list.append(0)
        continue
    else:
        ans_list.append((ans_list[i-2]+ans_list[i-1])%1000000007)

print(ans_list[n])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
MOD = 10 **9 + 7

import sys
for i in range(M-1):
    flag = a[i+1]-a[i]
    if flag == 1:
        print(0)
        sys.exit()
        
        
dp = [0] * (N+10)
dp[1] = 1
dp[2] = 1
for i in range(1,N+5):
    dp[i+2] = dp[i+1] + dp[i]
    dp[i+2] %= MOD
    
if M == 0:
    print(dp[N+1])
    sys.exit()
ans = 1
for i in range(M+1):
    if i == 0:
        number = a[i]
    elif i == M:
        number = N - a[i-1]
    else:
        number = a[i]-a[i-1] - 1
    number = max(1,number)
    ans *= dp[number]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
b = [int(input()) for _ in range(m)] + [n+1]
now = 0
A = [0,1]
if b[0] == 0:
  print(0)
else:
  for i in range(1,n+1):
    if b[now] == i:
      A.append(0)
      now += 1
    else:
      A.append( (A[-1]+A[-2]) % (10**9+7) )
  print(A[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] * M
for _ in range(M):
    data[_] = (int(stdin.readline().rstrip()))
 
ans = [1] + [0] * (N)
for i in (set(range(1,N+1)) - set(data)):
    ans[i] = ans[i-1] + ans[i-2]
print(ans[-1] % 1000000007)

Submission status: Accepted

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

now = 0
ans = 1
j = 0
for i in range(M):
    if now == a[i] - 1:
       now = a[i] + 1 
    elif now == a[i]:
        ans = 0
        break
    else:
        j = (a[i] - 1) - now
        k1 = 0
        k2 = 1
        k3 = 1
        for n in range(j):
            k3 = k2
            k2 += k1
            k1 = k3
        ans *= k2
        now = a[i] + 1
if ans > 0:
  j = N - now
  k1 = 0
  k2 = 1
  k3 = 1
  for n in range(j):
      k3 = k2
      k2 += k1
      k1 = k3
  ans *= k2
print(ans % 1000000007)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = list(int(input())for i in range(M))
a= [-1]+a+[N+1]
r = []
for i in range(M+1):
    r.append(a[i+1]-a[i]-1)
fi = [0,1,1]
for i in range(max(r)):
    fi.append(fi[-1]+fi[-2])
ans = 1
for i in r:
    ans = (ans*fi[i])%(10**9+7)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
broken = []
for i in range(0, N+1):
	broken.append(False)
for i in range(0, M):
	broken[int(input())] = True
dp = [1, 1]
if broken[1]: dp[1] = 0
for i in range(2, N+1):
	if broken[i]: dp.append(0)
	else:
		dp.append(dp[-1]+dp[-2])
print(dp[N]%1000000007)

Submission status: Accepted

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

# a = [int(input()) for i in range(M)]
a.append(N+1)
# print(N,M)
# print(a)

diff = []
diffmax = 0
for i, v in enumerate(a):
  if i != len(a)-1:
    steps = a[i+1] - a[i]
    diff.append(steps)
    if diffmax < steps:
      diffmax = steps

#print(diff)
      
actptn = [0,1]
for i in range(2,diffmax):
  actptn.append(actptn[i-1] + actptn[i-2])
#print(len(actptn))

ans = 1
for i in diff:
  ans = (ans* actptn[i-1]) % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import math
from fractions import Fraction
import sys


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a;
        self.b = b;
        self.c = c;
        self.d = d;
    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)
    
def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a



n, m =map(int, input().split())  #複数数値入力
a = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:
#         y = 1/root5 *(((1+root5)/2)**x - ((1-root5)/2)**x) 
        count *= fib(x)
print(int(count)%1000000007)

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
dp = [1]*(n+1)
for _ in range(m):
    dp[int(input())] = 0

for index,value in enumerate(dp):
    if index == 0 or index == 1:
        continue
    if dp[index] == 0:
        continue
    dp[index] = dp[index-1] + dp[index -2]
print(dp[n]%1000000007)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
stairs = [0] * (n + 1)
a = [int(input()) for i in range(m)]
mod = (10 ** 9 + 7)
stairs[0] = 1

if n == 1:
    print(1)
    exit()

for i in a:
    stairs[i] = -100


for i in range(1, n + 1):
    if stairs[i] >= 0:
        stairs[i] = max(stairs[i-1], 0) + max(stairs[i-2], 0)
        stairs[i] = stairs[i] % mod


print(stairs[n] % mod)

Submission status: Accepted

Solution code:
def step(num):
	a = 1
	b = 1
	for i in range(1,num):
		c = a
		a = b
		b += c
	return b

def main():
	data = input().split()
	person = 0
	road = 1
	for i in range(int(data[1])):
		a = int(input())
		if a - person == 0:
			print(0)
			return
		length = a - 1 - person
		road_1 = step(length)
		road *= (road_1 % 1000000007)
		person = a + 1
	length = int(data[0]) - person
	road_1 = step(length)
	road *= (road_1 % 1000000007)
	print(road % 1000000007)
	return

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限。素数しか使用不可。
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# need to calculate factorials to n+k-1
def combinations_with_repetition(n, k):
    return cmb(n+k-1, k, mod)

def num_of_pattern(n):
    sum_of_pattern = 0
    if n%2 == 1:
        for k in range(0,n,2):
            sum_of_pattern += combinations_with_repetition(((n-k)//2)+1, k)
        return sum_of_pattern % mod
    else:
        for k in range(1,n,2):
            sum_of_pattern += combinations_with_repetition(((n-k)//2)+1, k)
        return sum_of_pattern % mod

def main(): 
    N, M = LI()
    a_li = [-1]
    prev = INF
    for _ in range(M):
        now = II()
        if prev+1 == now:
            print(0)
            return
        elif prev == now:
            continue
        prev = now
        a_li.append(now)
    a_li.append(N+1)

    ans = 1
    for i in range(len(a_li)-1):
        ans *= num_of_pattern(a_li[i+1] - a_li[i] - 1)
        ans %= mod

    print(ans)

main()

Submission status: Accepted

Solution code:
from sys import stdin
data = stdin.readline().split()
N, M = int(data[0]), int(data[1])
a = [None] * M
fib = [None] * N
if N == 1:
    print(1)
    exit()
for i in range(M):
    a[i] = int(stdin.readline().rstrip())
    fib[a[i] - 1] = 0
    if i > 0 and a[i] - a[i-1] == 1:
        print(0)
        exit()
if not 1 in a:
    fib[0] = 1
    if not 2 in a:
        fib[1] = 2
    else:
        fib[1] = 0
else:
    fib[0] = 0
    fib[1] = 1
for i in range(2,N):
    if fib[i] == 0:
        continue
    else:
        fib[i] = fib[i-1] + fib[i-2]
# print(fib)
print(fib[N-1] % 1000000007)

Submission status: Accepted

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys

WARU = 1000000007

N, M = [ int(x) for x in input().split() ]
A = {}
for i in range(M):
    A[int(input())] = 1

ans = [None for i in range(N + 1)]
ans[0] = 1
ans[1] = 1
for a in A:
    ans[a] = 0

for i in range(N):
    n = i + 1
    if ans[n] is not None:
        continue
    ans[n] = (ans[n-2] + ans[n-1]) % WARU


print(ans[N])

Submission status: Accepted

Solution code:
import sys
N,M = map(int, input().split())
mod = 1000000007
if N == 1:
    print(1)
    sys.exit()
a = set()
b = -1
for _ in range(M):
    c = int(input())
    a.add(c)
    if abs(b-c) == 1:
        print(0)
        sys.exit()
    b = c
dp = [0]*(N+2)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, N+2):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i-1]%mod + dp[i-2]%mod
print(dp[N]%mod)

Submission status: Accepted

Solution code:
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


def main():
    N, M = map(int, input().split())  # 複数数値入力
    li = list()
    last = -1
    current = N
    ans = 1
    beforeBroken = 0
    for i in range(M):
        current = int(input())
        beforeBroken = current
        if last == current - 1 and last != 0:
            print(0)
            return

        if current != 1:
            li.append(current - last-2)
        last = current

    if M != 0:
        li.append(N - beforeBroken-1)
    else:
        li.append(N)
    for i in li:
        ans *= Fib(i+2)
    print(ans % 1000000007)


main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) # 禁止地帯

for i in range(1,N+1):
  if i in A:
    continue
  x = dp[i-1]
  if i > 1:
    x += dp[i-2]
  dp[i] = x%MOD

answer = dp[N]
print(answer)

Submission status: Accepted

Solution code:
mod = 1000000007
n, m = map(int, input().split())
dat_m = []
dp = [0] * (n + 1)
for i in range(m):
    t = int(input())
    dp[t] = -1

dp[0] = 1
for i in range(1, n + 1):
    if dp[i] == -1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1]
    if i > 1:
        dp[i] += dp[i - 2]
    if i in dat_m:
        dp[i] = 0
    dp[i] = dp[i] % mod

print(dp[n])

Submission status: Accepted

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

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

step = [0 for _ in range(N+1)]

ptr = 0

step[0] = 1
step[1] = 1
if ptr < M and A[ptr] == 1:
    step[1] = 0
    ptr += 1

for i in range(2, N+1):
    if ptr < M and i == A[ptr]:
        ptr += 1
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    N, M = map(int, input().split())
    A = [int(input()) for _ in [0] * M]

    stair = [0] * (N + 1)
    stair[0], stair[1] = 1, 1
    for a in A:
        stair[a] = -1

    mod = 1000000007
    for i in range(2, N + 1):
        if stair[i-1] == stair[i-2] == -1:
            print(0)
            return
        elif stair[i] == -1:
            continue
        if stair[i-1] > -1:
            stair[i] += stair[i-1]
        if stair[i-2] > -1:
            stair[i] += stair[i-2]
        stair[i] = stair[i] % mod
    print(stair[-1])

input = lambda: stdin.readline()
main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D=[1]*(N+1)
MOD=1000000007
for _ in range(M):
    i = int(input())
    D[i]=0

C = [0]*(N+1)
C[0]=1
for i in range(N-1):
    C[i+1]+=(C[i]*D[i])%MOD
    C[i+2]+=(C[i]*D[i])%MOD
C[N]+=(C[N-1]*D[N-1])%MOD
    #print(C)
print(C[N]%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
r = [0, 1]
mod = 1000000007
a = []
for i in range(m):
  a.append(int(input()))
j = 0
for i in range(n):
  if j < m and i == a[j] - 1:
    r = [r[1], 0]
    j += 1
  else:
    r = [r[1], (r[0] + r[1]) % mod]
print(r[-1])

Submission status: Accepted

Solution code:
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
#これを消すとなぜかWAになる呪い
for i in range(m-1):
    if a[i]+1 == a[i+1]:
        print(0)
        exit(0)
if n == 1:
    print(1)
else:
    p = 0
    dp = [0 for i in range(n+1)]
    dp[1]  = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1]+dp[i-2]
    left = [i+1 for i in a]
    right = [i-1 for i in a]
    left.insert(0,0)
    right.append(n)
    s = 1
    for i in range(len(right)):
        if right[i] != left[i] :s*=dp[right[i]-left[i]]
        s%=rem
    print(s)

Submission status: Accepted

Solution code:
def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]


n, m = [int(i) for i in input().split()]
a = []
frag = 1
ans = 0
step = []
for i in range(m):
    a.append(int(input()))
for i in range(m-1):
    if(a[i] == a[i+1] - 1):
        frag = 0
if(frag == 0):
    ans = 0
else:
    ans = 1
    sirusi = 0
    for i in range(len(a)):
        step.append(a[i] - 1 - sirusi)
        sirusi = a[i] + 1
    step.append(n - sirusi)
    for i in range(len(step)):
        ans = ans * fib(step[i]+1)
    ans = ans % 1000000007
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 1000000007
a = [0] * (N+1)
can_pass = True
for i in range(M):
    ai = int(input())
    if a[ai-1] == 1:
        can_pass = False
        break
    a[ai] = 1

if not can_pass:
    print(0)
else:
    c = [0] * (N+1)
    c[0] = 1
    for i in range(1, N+1):
        if a[i] == 0:
            if i > 1:
                c[i] = (c[i-1] + c[i-2]) % MOD
            else:
                c[i] = c[i-1]
        else:
            c[i] = 0
    print(c[N])

Submission status: Accepted

Solution code:
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
a_list.append(-1)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
    j=1
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1
else:
    dp[1]=1
    j=0
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1

print(dp[n]%modulo)

Submission status: Accepted

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

MOD = 1000000007

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

p[N] = 1
if p[N-1] != -1:
    p[N-1] = 1

for i in range(N-2, -1, -1):
    if p[i] == -1:
        continue
    if p[i+1] == -1 and p[i+2] == -1:
        p[i] = -1
    elif p[i+1] == -1:
        p[i] = p[i+2]
    elif p[i+2] == -1:
        p[i] = p[i+1]
    else:
        p[i] = p[i+1] + p[i+2]

    if p[i] > 0:
        p[i] %= MOD

ans = p[0]
if ans < 0:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
list1=set([int(input()) for i in range(M)])
list2=[1]+[0]*N
if not 1 in list1:
    list2[1]=1
for i in range(N-1):
    if not i+2 in list1:
        list2[i+2]=(list2[i]+list2[i+1])%1000000007
print(list2[N])

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
a = []
for _ in range(M):
    a.append(int(input()))
a = sorted(list(set(a)))
if len(a)>0:
    dif = [a[0]-1]
    dif.extend([(a[i]-1)-(a[i-1]+1) for i in range(1,len(a))])
    dif.extend([N-a[-1]-1])
else:
    dif = [N]
max_dif = max(dif)
Fiblist = {-1:0,0:1,1:1,2:2}
for n in range(3,max_dif+1):
    Fiblist[n]=Fiblist[n-1]+Fiblist[n-2]
ans = 1
for part in dif:
    ans= ans*Fiblist[part]%1000000007
print(ans)