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 sys
n,m = map(int,input().split())
mark = [1 for x in range(n+3)]
score = [0 for x in range(n+3)]
score[0]=1
mod = 1000000007
for i in range(m):
    mark[int(sys.stdin.readline())] = 0
c = 0
for i in range(0,n+1):
    if mark[i+1]:
        score[i+1]+=score[i]
        score[i+1]%=mod
    if mark[i+2]:
        score[i + 2] += score[i]
        score[i + 2]%mod
print(score[n]%mod)

Submission status: Accepted

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

def solve():
    N, M = list(map(int, input().split()))
    A = {}
    for i in range(1, N+1):
        A[i] = True  # 踏める
    for i in range(M):
        a = int(input())
        A[a] = False  # 踏めない
    MOD = 10**9+7

    # dp[i] := i段目までの場合の数
    dp = [0] * (N+1)
    dp[0] = 1

    for i in range(1, N+1):
        if A[i] is False: continue

        dp[i] += dp[i-1]
        if i-2 >= 0:
            dp[i] += dp[i-2]
        dp[i] %= MOD
    
    print(dp[N]%MOD)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
def nibutan(x,l):
    low=0
    high=len(l)-1
    while low<=high:
      mid=(low+high)//2
      guess=l[mid]
      if guess==x:
         return True
      elif guess>x:
          high=mid-1
      elif guess<x:
          low=mid+1
    return False
if m==0:
  pass
else:
  for i in range(m):
    l.append(int(input()))
l1=[0 for i in range(n+1)]
if 1 in l:
  l1[0]=0
else:
  l1[0]=1

if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n>=3:
  for i in range(3,n+1): 
    if nibutan(i,l):
      pass
    else:
      l1[i-1]=(l1[i-2]+l1[i-3])%(((10**9)+7))
print(l1[n-1])

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

Submission status: Accepted

Solution code:
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
flag = 0
for i in range(3,100001):
	p[i] = p[i-1] + p[i-2]


n,m = map(int,input().split())
l = [0]*(m+2)
l[m+1] = n
for i in range(m):
	l[i+1] = int(input())

l1 = [0]*(m+1)
for i in range(m+1):
	l1[i] = l[i+1] - l[i]

# print(l1)

if m == 0:
	print(p[n] % 1000000007)
	flag = 1
else:
	for i in range(m+1):
		if i == 0 or i == m:
			ans = ans * p[l1[i]-1]
		else:
			if l1[i] == 1:
				print(0)
				flag = 1
				break
			else:
				if l1[i] == 0:
					ans = ans
				else:
					ans = ans * p[l1[i]-2]

if flag != 1:
	print(ans % 1000000007)

Submission status: Accepted

Solution code:
import sys
from itertools import product

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())

li = [input() for _ in range(m)]

for i in range(1,len(li)):
    if int(li[i]) - int(li[i-1]) == 1:
        print(0)
        sys.exit()

ans = ["a" for i in range(n+1)]

for i in li:
    ans[int(i)] = "#"
    
ans = "".join(ans)

ans = ans.split("#")

result = 1

for i in ans:
    result *= fib(len(i))

print(result%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

Submission status: Accepted

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

t = 1000000007
ans = 1


def Fib(n):
    a, b = 1, 2
    if n == 0:
        return 1
    elif 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(n)
elif m == 1:
    ans = ans * Fib(a[0] - 1) * Fib(n - a[0] - 1)
else:
    for i in range(m):
        # 最初の段
        if i == 0:
            ans = ans * Fib(a[i] - 1)
        # 二段壊れは0
        elif a[i] - a[i - 1] == 1:
            ans = 0
            break
        # 最後の段
        elif i == m - 1:
            ans = ans * Fib(a[i] - a[i - 1] - 2)
            if a[i] != n - 1:
                ans = ans * Fib(n - a[i] - 1)
            break
        # 壊れ段の間
        else:
            ans = ans * Fib(a[i] - a[i - 1] - 2)

print(ans % t)

Submission status: Accepted

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 = min(len(x)-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: Accepted

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

mod = int(1e9+7)
dp = [0 for i in range(n+1)]
dp[0] = 1
ind = 0

for i in range(1,n+1):
    if ind < m and a[ind] == i:
        dp[i] = 0
        ind += 1
    else:
        if i != 1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1]
print(int(dp[-1]%mod))

Submission status: Accepted

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

a.sort()
A = [0]*(N+1)
A[0] = 1

flag = True
if M==0: flag = False

for i in range(1, N+1):
  if flag and i == a[0]:
    A[i] = 0
    a.remove(i)
    if len(a)==0: flag = False
  else:
    if i==1: A[i] = 1
    else:
      A[i] = (A[i-1] + A[i-2])%div

print(A[N])

Submission status: Accepted

Solution code:
fib=[0,1]
for i in range(100000):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[-1]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
for i in range(len(hoge)-1):
  sa=hoge[i+1]-hoge[i]-1
  ans=ans*fib[sa]
  ans=ans%1000000007
print(ans)

Submission status: Accepted

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

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

if m==0:
    print(fb(n+1) % (10**9+7))
    
else:
    sum=fb(int(a[0]))

    for i in range(m-1):
        sum=sum*fb(int(a[i+1])-int(a[i])-1)

    sum=sum*fb(n-int(a[m-1]))

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

Submission status: Accepted

Solution code:
def howmany(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 = map(int,input().split())

x = 1
a = [0]*(m+2)
a[0] = -1
a[m+1] = n

if m == 0:
    print(howmany(n+1) % 1000000007)
else:
    for i in range(1,m+1):
        a[i] = int(input())

    if all(a[i+1]-a[i] != 1 for i in range(1,m)):
        for i in range(1,m+1):
            if a[i] - a[i-1] > 1:
                x *= howmany(a[i] - a[i-1] -1)
        if a[m] + 1 == n:
            print(x % 1000000007)
        else:
            x *= howmany(a[m+1]-a[m])
            print(x % 1000000007)
    else: print(0)

Submission status: Accepted

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])
    if len(a) >= 2:
        maxdif = max(maxdif, n - a[-1])
    else:
        maxdif = n
    MOD = 1000000007
    # Logic ############################################################################################################
    idx = 0
    total = 1
    fib = fibonacci(maxdif + 2)
    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: Accepted

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(2, n+1):
    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: Accepted

Solution code:
n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
p = (10**9)+ 7
a.append(n+1)
memo = [0,1,1]
for i in range(2,n+10):
    memo.append((memo[i-1]+memo[i])%p)

ans = 1
clist = []
for i in range(len(a)):
    if i == 0:
        cnt = a[0]+1
        clist.append(cnt)
    else:
        cnt = a[i]-a[i-1]
        clist.append(cnt)
    if cnt == 1:
        ans = ans * 0
        break
    
    ans = (ans * memo[cnt-1]) % p
print(ans)

Submission status: Accepted

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

dp_f = [None] * (10**5 + 2)
dp_f[1] = 1
dp_f[2] = 1
for i in range(3, 10**5 + 1):
    dp_f[i] = dp_f[i-1] + dp_f[i-2]
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif dp_f[n] is not None:
        return dp_f[n]
    v = f(n-1) + f(n-2)
    dp_f[n] = v
    return dp_f[n]

if M == 0:
    m = f(N+1)
    m %= 1000000007
    print(m)
    sys.exit(0)

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

S = []
S.append(A[0])
for i in range(1, M):
    if A[i] == A[i-1] + 1:
        print(0)
        sys.exit(0)
    S.append(A[i] - A[i-1] - 1)
S.append(N - A[-1])

m = 1
for s in S:
    m *= f(s)
    m %= 1000000007

print(m)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(30000)

N, M = map(int, input().split())
a = list(int(input()) for _ in range(M))

MOD = pow(10, 9) + 7

isOk = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        isOk = False
    
funcb = [-1] * 100001
def func(n):
    if n <= 0:
        return 1
    cnt = funcb[n]
    if cnt > 0:
        return cnt
    cnt = 0
    if n >= 2:
        cnt += func(n-2)
    if n >= 1:
        cnt += func(n-1)
    funcb[n] = cnt % MOD
    return funcb[n]

func(30000)
func(50000)
func(80000)
func(100000)

if not isOk:
    print(0)
else:
    ans = 1
    s = 0
    for i in range(M+1):
        if i >= M:
            e = N
        else:
            e = a[i] - 1

        ans = ans * func(e-s) % MOD

        if i >= M:
            break

        s = a[i] + 1

    print(ans)

Submission status: Accepted

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

import sys

input = sys.stdin.readline

cnt = 0

def main():
    N, M = map(int, input().split())
    m = {}
    for l in sys.stdin:
        m[int(l.strip())] = True

    # N 個の階段における移動方法
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    dp[1] = 1 if 1 not in m else 0

    # N-1の移動パターン + N-2の移動パターン
    for i in range(2, N+1):
        if i in m:
            dp[i] = 0
            continue
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[N] % 1000000007)

main()

Submission status: Accepted

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

m = 10**9+7

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

memo[0] = 0

A.append(N+1)
p = A[0]
ans = memo[p]
for i in range(1,M+1):
    ans *= memo[A[i]-p-1]
    p = A[i]

print(ans%m)

Submission status: Accepted

Solution code:
def Fib(n):
    a, b = 1, 1
    if n == 0:
        return a
    elif n == 1:
        return b
    else:
        for _ in range(n-1):
            a, b = b, a + b
        return b

N, M = map(int, input().split())
ai = -1
ans = 1


for _ in range(M):
    af = int(input())
    L = af - ai - 2
    if L == -1:
        ans = 0
        break
    else:
        ans *= Fib(L)
        ai = af
ans *= Fib(N - ai - 1)

ans = ans % 1000000007

print(ans)

Submission status: Accepted

Solution code:
N ,M= map(int, input().split())
memo =[1]*(N + 2)#start goal and hole
memo[N+1] = 0 #dead hole
impossible = False
back2 = 0
start_step =0
for i in range(M):
    a = int(input())
    memo[a] = 0 
  
def one_step(step):
    memo[step] = (memo[step+1] + memo[step+2])*memo[step]

for step in range(N-1 ,-1,-1):
    one_step(step)

print(memo[0]%1000000007)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = 10**9+7
nots = [int(input()) for i in range(m)]
leng = len(nots)
cnt = 0
dp = [0]*(n+1)
dp[0] = 1
if leng > 0 and nots[0] == 1:
  dp[1] = 0
  nots.pop(0)
  leng -= 1
else:
  dp[1] = 1
if n == 1:
  print(1)
  exit()

for i in range(2,n+1):
  if leng > 0 and nots[cnt] == i:
    dp[i] = 0
    if cnt < leng - 1:
      cnt += 1
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % num
print(dp[n] % num)

Submission status: Accepted

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

combination = [1,1,2]
for i in range(3,N+1):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []

if M > 0:
    next_a = int(input())
    lst.append(combination[next_a-a-1])
    a = next_a
    for i in range(M-1):
        next_a = int(input())
        if next_a-a == 1:
            ans = 0
            break
        elif next_a-a == 0:
            continue
        lst.append(combination[next_a-a-2])
        a = next_a

    next_a = N
    lst.append(combination[next_a-a-1])
else:
    lst.append(combination[N])
    
for tmp in lst:
    ans *= tmp
print(ans%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    if 1 == A[idx]:
        dp[1] = 0
        if idx < M-1:
            idx += 1

if len(A):
    for i in range(2, N+1):
        if i != A[idx]:
            dp[i] = (dp[i-1] + dp[i-2]) % P
        else:
            dp[i] = 0
            if idx < M-1:
                idx += 1
else:
    for i in range(2, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[N])

Submission status: Accepted

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 = [1, 1] + [0] * (total - 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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

lis = [1,1,2]
def num(n):
    if len(lis) >= n+1:
        return lis[n]
    else:
        res = num(n-2) + num(n-1)
        lis.append(res)
        return res

N,M = map(int,input().split())
count = 1
pre = 0
for i in range(M+1):
    if i == M:
        cur = N+1
    else:
        cur = int(input())
    number = cur-1-pre
    if number >= 0:
        count = count * num(number) % 1000000007
    else:
        count = 0
        break
    pre = cur + 1
print(count%1000000007)

Submission status: Accepted

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

def fb(num):
    fblist = []
    x, y = 1, 0
    for _ in range(num):
        fblist.append(x)
        x, y = x + y, x
    return fblist

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

l = fb(n + 1)

now = 0
p_cnt = []
for i in range(m):
    a = int(input())
    if now == a:
        print(0)
        exit()
    p_cnt.append(l[a - 1 - now])
    now = a + 1

# print(n)
# print(now)
# print(l)
p_cnt.append(l[n - now])

# print(p_cnt);
ans = 1
for j in range(len(p_cnt)):
    # print(ans)
    ans *= p_cnt[j]
    # print(ans)
    
print(ans %  1000000007)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
ans = 1
a = []
al = 0
for i in range(2,N+1):
    c[i] = c[i-1]+c[i-2]
    c[i] %= mod
for i in range(M):
    ai = int(input())
    if i == 0:
        a.append(ai)
    else:
        if ai - al == 1:
            print(0)
            exit()
        else:
            a.append(ai)
    al = ai
if M == 0:
    print(c[N])
    exit()
for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        if a[i+1] != a[i]:
            ans *= c[a[i+1]-a[i]-2]
            ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
base = 1000000007

x = [0] * (N+1)
x[0] = 1
ai = 0
if ai >= M or 1 != a[ai]:
    x[1] = x[0]
else:
    ai += 1
for i in range(2, (N+1)):
    if ai >= M or i != a[ai]:
        x[i] = (x[i-1] + x[i-2]) % base
    else:
        ai += 1
print(x[N])

Submission status: Accepted

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

p = [0]*(n+1)
for i in bk:
    p[i] = -100
if n == 1 and m == 0:
    print(1)
elif n == 1 and m == 1:
    print(0)
else:
    p[0] = 1
    if 1 in bk:
        p[1] = 0
    else:
        p[1] = 1
    for i in range(n-1):
        if p[i+2] < 0:
            p[i+2] = 0
        else:
            p[i+2] = p[i]+p[i+1]
            if p[i+2] >= 1000000007:
                p[i+2] -= 1000000007

    print(p[n])

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    if(len(a) >= 2):
        l = [a[i+1]-a[i] for i in range(M-1)]
        if(len(l) and min(l)<=1):
            print(0)
            exit()

    dp = [1] * (N+1)
    dp[1] = 1
    if(N >= 2):
        dp[2] = 2
    x = 0
    # if(M == 0):
    #     for i in range(2,N+1)
    
    for i in range(2,N+1):
        if(len(a) and a[x] == i-1):
            dp[i] = dp[i-2] % MOD
            # x = min(x+1,M-1)
        elif(len(a) and a[x] == i-2):
            dp[i] = dp[i-1] % MOD
            x = min(x+1,M-1)
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
    print(dp[N])
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Submission status: Accepted

Solution code:
R = lambda: map(int, input().split())
M = 10**9 + 7
n, m = R()
a = [-1] + [int(input()) for _ in range(m)]
s, t = 0, 1
for i in range(n - 1, -1, -1):
    if i == a[-1]:
        a.pop()
        s, t = t, 0
    else:
        s, t = t, (s + t) % M
print(t)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a = -1
List = []
for i in range(M):
    k = int(input())
    List.append(k-a)
    a = k
List.append(N - a + 1)
m = max(List)
mm = min(List)
LL = [0,1]
for i in range(2,m):
    k = LL[i-1] + LL[i-2]
    LL.append(k)
s = 1
for i in range(M+1):
    s = s * LL[List[i]-1]
print(s % 1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"
 
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N,M=LI()
    A=[]
    for i in range(M):
        A.append(I())

    tmp1=0
    tmp2=0
    tmp3=0
    out=1
    for n in range(N+1):
        # print(n)
        # print(n,A,tmp3)
        if A:
            if n==1 and A[0]==n:
                tmp1=0
                tmp2=0
                tmp3=0
                del A[0]
                if A:
                    if A[0]==n+1:
                        print("0")
                        exit()
                continue
            elif n!=0 and A[0]==n:
                out*=tmp3
                tmp1=0
                tmp2=0
                tmp3=0
                del A[0]
                if A:
                    if A[0]==n+1:
                        print("0")
                        exit()
                continue
        if tmp3==0:
            tmp3=1
        else:
            tmp1=tmp2
            tmp2=tmp3
            tmp3=tmp1+tmp2
        # print("outttt",A,n,tmp3)
    if tmp3>0:
        out*=tmp3
    print(out%1000000007)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ali = [int(input()) for _ in range(m)]
dif = []
cap = 0
for num in ali:
  dif.append(num-cap)
  cap = num
dif.append(n-cap+1)
dif[0] += 1
ref = [0,0,1,1]
a,b = 1,1
for i in range(100000):
  a,b = b,a+b 
  ref.append(b)
ans = 1
for num in dif:
  ans *= (ref[num] % 1000000007)
print(ans % 1000000007)

Submission status: Accepted

Solution code:
def sol(inp=input):
    mod=10**9+7
    n,m=map(int,inp().split())
    invalids=set(int(inp()) for _ in range(m))
    nums=[0 for _ in range(n+1)]
    nums[0]=1
    for i in range(n-1):
        if i+1 not in invalids:
            nums[i+1]+=nums[i]
        if i+2 not in invalids:
            nums[i+2]+=nums[i]
            nums[i+2]%=mod
    return str((nums[n-1]+nums[n])%mod)
print(sol())

Submission status: Accepted

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

a.append(N+1)    

step=[]

if a[0]==1:j=1
else:j=0

for i in range(2,N+1):
    if i <a[j]:
        step.append(i)
    else:
        step.append(0)
        j+=1

stepsum=[1]   #k段目までの組み合わせ
if a[0]==1:   #1段目がNGなら
    stepsum.append(0)
else:
    stepsum.append(1)
    
for i in step:
    if i==0:stepsum.append(0)
    else:stepsum.append(((stepsum[i-1]+stepsum[i-2]))%1000000007)


ans=stepsum[N]%1000000007
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
pre = 0
for i in range(M):
    broken = int(input())
    if pre == broken:
        continue
    pre = broken
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        ans %= 1000000007
        cur = broken + 1
else:
    if N > cur:
        ans *= F[N - cur - 1]
    print(ans % 1000000007)

Submission status: Accepted

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

mod = 1000000007
def mul(a, b):
  return ((a % mod) * (b % mod)) % mod


N, M = map(int, input().split())
if M != 0:
  a = int(input())
  ret = mul(1, Fib(a))
  pre_a = a

for i in range(M-1):
  a = int(input())
  if a - pre_a <= 1:
    ret = 0
    break
  else:
    num_step = a - pre_a - 1
    ret = mul(ret, Fib(num_step))
  pre_a = a
    
if M != 0:
  num_step = N - a
  ret = mul(ret, Fib(num_step))
else:
  ret = mul(1, Fib(N+1))
print(ret)

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 = map(int, input().split())

a= []

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

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)

# print(l)

if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))

        if result > 1000000007:
            result = result % 1000000007

    result = result % 1000000007

    print(result)

Submission status: Accepted

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