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:
# -*- coding: utf-8 -*-
n,m=map(int,input().split())

m_lst=[-1]
for i in range(m):
    m_lst.append(int(input()))
m_lst.append(n+1)
d_lst=[]
for i in range(len(m_lst)-1):
    d_lst.append(m_lst[i+1]-m_lst[i]-1)
def f(length):
    d=length-1
    if d==-1:
        return 0
    elif d==0:
        return 1
    elif d == 1:
        return 1
    elif d == 2:
        return 2
    else:
        last_two=1
        last_one=2
        last=0
        for i in range(d-2):
            last=last_two+last_one
            last_two=last_one
            last_one=last
        return last

output =1 
for d in d_lst:
    output*=f(d)
print(output%1000000007)

Submission status: Accepted

Solution code:
mod = 1000000007
N,M = [int(i) for i in input().split()]
A = []
for _ in range(M):
    A.append(int(input()))
steps = [0]*N
for a in A:
    steps[a-1] = 1
cnt = []
for n in range(N):
    if n == 0:
        if steps[n]==0:
            cnt.append(1)
        elif steps[n]==1:
            cnt.append(0)
    elif n == 1:
        if steps[n]==0:
            cnt.append(cnt[n-1]+1)
        elif steps[n]==1:
            cnt.append(0)
    elif steps[n] == 0:
        cnt.append((cnt[n-2]+cnt[n-1])%mod)
    elif steps[n] == 1:
        cnt.append(0)
print(cnt[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        exit()
dp=[0 for x in range(n+1)]
for j in range(m):
    dp[a[j]]=-1
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for k in range(1,n):
    if dp[k+1]!=-1:
        dp[k+1]=dp[k]+dp[k-1]
    else:
        dp[k+1]=0
print(dp[n]%1000000007)

Submission status: Accepted

Solution code:
# -*- Coding: utf-8 -*-
import numpy as np
MOD = 1000 * 1000 * 1000 + 7

N,M = map(int,raw_input().split())
A = np.zeros(N+1, dtype=np.int32)

for i in xrange(M):
	a = int(raw_input())
	A[a] = -1

A[0] = 1
for i in xrange(1,N+1):
	if A[i] == -1:
		A[i] = 0
	else:
		if  i == 1:
			A[i] = A[i-1]
		else:
			A[i] = A[i-1]+A[i-2]

		A[i] %= MOD

print A[N]

Submission status: Accepted

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

is_broken = [1] * (n+1)

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

step = [i for i in range(n+1)]
step[0] = 1

for i in range(n):
    if i - 1 >= 0:
        step[i+1] = step[i] * is_broken[i] + step[i-1] * is_broken[i-1]
    else:
        step[i+1] = step[i] * is_broken[i]
    step[i+1] %= mod

print(step[n])

Submission status: Accepted

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

j = 0
sum = []

for i in range(N+1):
    if j < M and i == A[j]:
        sum.append(0)
        if j < M-1:
            j += 1
    elif i == 0 or i == 1:
        sum.append(1)
    else:
        sum.append(sum[i-2] + sum[i-1])


print(sum[N]%1000000007)

Submission status: Accepted

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

li_m = list()

for _ in range(m):
    li_m.append(int(input()))


if set(li_m).intersection([l + 1 for l in li_m]):
    print(0)
    exit(0)


answer = 1

def pt(length):

    if length == 0:
        return 1

    li_test = [0] * length
    for i in range(length):
        if i == 0:
            li_test[i] = 1
        elif i == 1:
            li_test[i] = li_test[i - 1] + 1
        elif i == len(li_test):
            li_test[i] = li_test[i - 1] + 1
        else:
            li_test[i] = li_test[i - 1] + li_test[i - 2]

    return li_test[-1]


idx_start = 0
idx_end = 0

if len(li_m) != 0:

    for idx, v in enumerate(li_m):
        if idx == 0:
            idx_end = v - 1
        else:
            idx_start = idx_end + 2
            idx_end = v - 1

        subkaidan = idx_end - idx_start

        answer = answer * pt(subkaidan)

        if idx == len(li_m) - 1:
            idx_start = idx_end + 2
            idx_end = n
            subkaidan = idx_end - idx_start

            answer = answer * pt(subkaidan)
else:
    answer = answer * pt(n)


print(answer % 1000000007)

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
bf = -1
way = [-1] * (n+1)
way[0] = 1
way[1] = 1
mod = 10 ** 9 + 7
for i in range(m):
    tmp = int(input())
    if bf + 1 == tmp:
        print(0)
        sys.exit()
    bf = tmp
    way[tmp] = 0
for i in range(2, n+1):
    if way[i] == -1:
        way[i] = way[i-2] + way[i-1]
print(way[n] % mod)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
A = [0]*M
for i in range(M):
    A[i] = int(input())
if M != 0:
    
    L = A[0]+1
    if L < N - A[M-1]:
        L = N - A[M-1]
    for i in range(M-1):
        L1 = A[i+1]-A[i]
        if L1 > L:
            L = L1
else:
    L = N +2
    
x = [0]*L
x.insert(0,0)
x.insert(1,1)
if L >2:
    for i in range(L-2):
        x[i+2] = x[i+1] + x[i]
if M != 0:
    S = x[A[0]] * x[N - A[M-1]]
    for i in range(M-1):
        S *= x[A[i+1]-A[i]-1]
else:
    S = x[N+1]
print(S%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[0]*(n+1)
for i in range(m):dp[int(input())]=-1
dp[0]=1
if dp[1]!=-1:dp[1]=1
for i in range(2,n+1):
    if dp[i]==0:dp[i]=(max(dp[i-2],0)+max(dp[i-1],0))%(10**9+7)
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
dp = [-1] * (N+1)
#0段目と1段目に行く方法は1通り
dp[0] = 1
dp[1] = 1

for i in range(M):
    tmp = int(input())
    dp[tmp] = 0
    
for i in range(2, N+1, 1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
        #dp[i] %= 1000000007
print(dp[N]%1000000007)

Submission status: Accepted

Solution code:
# coding: utf-8
N, M = map(int, input().split())
dp = [-1] * (N+1)
#0段目と1段目に行く方法は1通り
dp[0] = 1
dp[1] = 1

for i in range(M):
    tmp = int(input())
    dp[tmp] = 0
    
for i in range(2, N+1, 1):
    if dp[i] != 0:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007
print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
#リスト内包表記でaに入れる
a = [int(input()) for _ in range(m)]

#MODに'1000000007'を入れる
MOD = 10**9 + 7
#zに集合を作成する
z = set(a)
 
#i段目までにたどりつく方法を順に求める
x = [0 for _ in range(n + 1)]
#0段目の場合1とする
x[0] = 1
#1段目の場合は集合の中に1が含まれていないかどうか、含まれていない:1、含まれている:0
x[1] = int(1 not in z)
#2段目以降の場合
for i in range(2, n + 1):
#集合の中にiが含まれていない場合
    if i not in z:
#i段目に1段か2段で上ってきた経路数を足して、MODで割る、dp[i]に蓄積する
        x[i] = (x[i - 1] + x[i - 2]) % MOD
print(x[n])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

for n in range(1, N + 1):
	if n in A:
		continue
	dp[n] = (dp[n - 1] + (dp[n - 2] if 2 <= n else 0)) % MOD

print(dp[N])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

am = set()
for a in A:
	am |= {a}

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

for n in range(1, N + 1):
	if n in am:
		continue
	dp[n] = (dp[n - 1] + (dp[n - 2] if 2 <= n else 0)) % MOD

#print(dp)
print(dp[N])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

am = {}
for a in A:
	am[a] = True

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

for n in range(1, N + 1):
	if n in am:
		continue
	dp[n] = (dp[n - 1] + (dp[n - 2] if 2 <= n else 0)) % MOD

#print(dp)
print(dp[N])

Submission status: Accepted

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

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

for i in range(N):
    if l[i] == -1:
        continue
    if l[i+1] != -1:
        l[i+1] = (l[i+1]+l[i])%(10**9+7)
    if l[i+2] != -1:
        l[i+2] = (l[i+2]+l[i])%(10**9+7)

print(l[N])

Submission status: Accepted

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

dp = [0 for _ in range(n+1)]
broken_id = 0

dp[0] = 1
if broken_id < m and a[broken_id] == 1:
  broken_id += 1
  dp[1] = 0
else:
  dp[1] = 1

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

Submission status: Accepted

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

MOD = 10**9 + 7
A = set(a)

# i段目までにたどりつく方法を順に求める
dp = [0 for _ in range(N + 1)]
dp[0] = 1
dp[1] = int(1 not in A)
for i in range(2, N + 1):
    if i not in A:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
ans = dp[N]

# 出力
print(ans)

Submission status: Accepted

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


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = (a1 + a2) % 1000000007
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

    ans = ans * fib(n - li[m-1]) % 1000000007
    print(ans)

else:
    print(fib(n+1))

Submission status: Accepted

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

import sys

N, M = list(map(int, input().split()))
if M > 0:
    broken = set(map(int, sys.stdin))
else:
    broken = set()

dp = [0] * (N + 1)

dp[0] = 1
dp[1] = 1 if 1 not in broken else 0

MOD = 10 ** 9 + 7

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys

n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split(" "))
a = set()
for i in range(m):
    a.add(int(input()))

waysFrom = {}
waysFrom[n - 1] = 0 if n - 1 in a else 1
waysFrom[n - 2] = 0 if n - 2 in a else 1 + waysFrom[n - 1]

for i in reversed(range(n - 2)):
    if i in a:
        waysFrom[i] = 0
    else:
        waysFrom[i] = waysFrom[i + 1] + waysFrom[i + 2]
        if waysFrom[i] == 0:
            waysFrom[0] = 0
            break

print(waysFrom[0] % 1000000007)

Submission status: Accepted

Solution code:
from collections import deque

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

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

now = 0
if 1 not in A:
    tmp[1] = 1
    
else:
    now += 1
    
if (2 not in A) and N >= 2:
    tmp[2] = tmp[1] + 1
    
else:
    now += 1

for i in range(3, N+1):
    
    try:
        if i != A[now]:
            tmp[i] = tmp[i-1] + tmp[i-2] 
            
        else:
            now += 1
        
    except:
        tmp[i] = tmp[i-1] + tmp[i-2] 

    
print(tmp[-1]%(10**9+7))

Submission status: Accepted

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

broken = [False] * (N + 1)
for ai in a:
  broken[ai] = True

memo = [0] * (N + 1)
memo[0] = 1

idx = 0
for pos in range(1, N + 1):
    if broken[pos]:
        memo[pos] = 0
    elif pos < 2:
        memo[pos] = (memo[0]) % (10 ** 9 + 7)
    else:
        memo[pos] = (memo[pos - 2] + memo[pos - 1]) % (10 ** 9 + 7)

# print("#", memo)
print(memo[-1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a_s = []
for _ in range(M):
  a_s.append(int(input()))
a_s.append('END')
  
dp = []
a_cursor = 0
for i in range(N+1):
  if i == a_s[a_cursor]:
    dp.append(0)
    a_cursor += 1
  else:
    if i == 0:
      dp.append(1)
    elif i == 1:
      dp.append(1)
    else:
      dp.append((dp[i-1]+dp[i-2])%1000000007)
      
print(dp[-1])

Submission status: Accepted

Solution code:
### 解説読んでから書いたコード ###

n, m = map(int, input().split())
MOD = 1000000007
if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []

a.append(-1) # 末尾に-1を追加(壊れている床がもう無い事を示す)
a_i = 0

## n段目への移動方法は、step[n]通り存在する
## step[n] = step[n-2] + step[n-1]

step = [0] * (n+2)
step[-1] = -1 # 存在しない段(計算用)
step[0] = 1 # 0段目は1通り

for i in range(1, n+1):
    if a[a_i] == i:
        step[i] = -1 # 壊れている床は-1
        a_i += 1
    else:
        if step[i-2] == step[i-1] == -1:
            print(0) # 2段続けて壊れている場合は0通り
            exit()
        elif step[i-2] == -1 or step[i-1] == -1:
            step[i] = max(step[i-2], step[i-1]) # [1,2]段前が壊れている場合
        else:
            step[i] = (step[i-2] + step[i-1]) % MOD # 通常の場合

print(step[n])

Submission status: Accepted

Solution code:
def fib(num_steps):
    xb = 0
    xa = 1
    if num_steps == 0:
        return xa
    else:
        for i in range(num_steps):
            tmp = xa
            xa = xa + xb
            xb = tmp
    
    return xa

N, M = map(int, input().split())
ways = 1
now = 0

for i in range(M):
    hole = int(input())
    diff = (hole - 1) - now

    if diff < 0:
        ways *= 0
    else:
        ways *= fib(diff)

    now = hole + 1

if now < N:
    ways *= fib(N - now)

print(ways % 1000000007)

Submission status: Accepted

Solution code:
### 解説読んでから書いたコード
n, m = map(int, input().split())
MOD = 1000000007
if m > 0:
    a = [int(input()) for i in range(m)]
else:
    a = []

a.append(-1)
a_i = 0

step = [0] * (n+2)
step[-1] = -1
step[0] = 1
for i in range(1, n+1):
    if a[a_i] == i:
        step[i] = -1
        a_i += 1
    else:
        if step[i-2] == step[i-1] == -1:
            print(0)
            exit()
        elif step[i-2] == -1 or step[i-1] == -1:
            step[i] = max(step[i-2], step[i-1])
        else:
            step[i] = (step[i-2] + step[i-1]) % MOD
            
print(step[n])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
#print(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  if i in a:
    dp[i] = 0
print(dp[-1])

Submission status: Accepted

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

step = [-1]*(N+1)
step[0] = 1
for i in a:
    step[i] = 0

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

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
inf=1000000007
dp=[-1]*(N+1)
for i in range(M):
	dp[int(input())]=0
dp[0]=1
if dp[1]==-1:
	dp[1]=1
for i in range(2,N+1):
	if dp[i]==0:
		continue
	else:
		dp[i]=(dp[i-2]+dp[i-1])%inf
print(dp[N]%inf)

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,M = na()
MOD=1000000007
#壊れいている段の数
a=[]
dp = [0]*(N+1)
dp[0]=1
a = [ni() for i in range(M)]
isbro = [1]*(N+1)
for i in range(M):
    isbro[a[i]]=0
#print(isbro)
for i in range(N):
    if(i-1>=0):
        dp[i+1] = dp[i]*isbro[i] + dp[i-1]*isbro[i-1]
    else:
        dp[i+1] = dp[i]*isbro[i]
    dp[i+1]%=MOD
#print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
if m > 0:
    a = [int(input()) for i in range(m)]
    interval_max = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()
        interval_max = max(interval_max, a[i+1] - a[i])
else:
    a = []
    interval_max = n
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

fibb = [0]*(max(interval_max+2, 3))
fibb[0] = fibb[1] = fibb[2] = 1
for i in range(3,interval_max+2):
    fibb[i] = (fibb[i-2] + fibb[i-1]) % 1000000007
sum_step = 1
# print(a)
if m == 0:
    sum_step = fibb[n+1]
else:
    for i in range(len(a)-1):
        if i == 0 or i == len(a)-2:
            sum_step *= fibb[a[i+1] - a[i]]
            # print(fibb[a[i+1] - a[i]])
        else:
            sum_step *= fibb[a[i+1] - a[i] - 1]
            # print(fibb[a[i+1] - a[i]] - 1)
        sum_step = sum_step % 1000000007
print(sum_step)
# print(step)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM
 
 
STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0
 
 
listM={int(input()) for i in range(M)}
dp[0] = 1
 
for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

Submission status: Accepted

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

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

A = [0]*N
a_prev = None
for i in range(M):
  a_i = int(input())
  if a_prev == a_i:
    print(0)
    exit()
  A[a_i] = 1  
  a_prev = a_i

N_2 = 1
N_1 = 1  
ans = 0
for i in range(1, N):
  if A[i]==1:
    N_1 = 0
  ans = (N_1 + N_2)%1000000007
  N_2 = N_1
  N_1 = ans
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[-1]+[int(input()) for i in range(M)]+[N+1]
res=1
for i in range(1,len(A)):
  steps=A[i]-A[i-1]-2
  if steps<0:
    patern_nmu=0
  else:
    p,q=1,0
    for j in range(steps):
      p,q=p+q,p
    patern_nmu=p
  res*=patern_nmu
  res%=1000000007
print(res)

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:
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

if n==1:
    print(1)
    exit()
 
if d[0]==1:
    s[0]=0
else:
    s[0]=1
 
if d[1]==1:
    s[1]=0
else:
    s[1]= s[0]+1
 
 
for i in range(2,n):
    if d[i]==1:
        s[i]=0
    else:
        s[i]=(s[i-1]+s[i-2])%1000000007
 
print( s[n-1] % 1000000007)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

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

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

Submission status: Accepted

Solution code:
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)

Submission status: Accepted

Solution code:
import sys
N, M = list(map(int, input().split()))
broken_set = set([
    int(input())
    for _ in range(M)
])

f = [0] * (N + 1)

f[0] = 1
f[1] = int(1 not in broken_set)

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

print(f[N])

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
A = []
A = [0 for i in range(N + 1)]
for i in range(M):
    a = int(raw_input())
    A[a] = -1

dp = []
dp = [0 for i in range(N + 1)]
dp[0] = 1

for i in range(N):
    if (i + 1) <= N and A[i + 1] == 0:
        dp[i + 1] += dp[i]
    if (i + 2) <= N and A[i + 2] == 0:
        dp[i + 2] += dp[i]


print str(dp[N]%1000000007)

Submission status: Accepted

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

res = 1
for i in range(1, len(a)):
    steps = a[i] - a[i-1] - 2
    if steps < 0:
        patern_nmu = 0
    else:
        p, q = 1, 0
        for j in range(steps):
            p, q = p+q, p
        patern_nmu = p
    res *= patern_nmu
    res %= 1000000007

print(res)

Submission status: Accepted

Solution code:

N,M = list(map(int,input().split(" ")))
NUM = 1000000007
ans = 1
f = [-1] * (N+1)
f[0] = 1
f[1] = 1
for _ in range(M):
    now = int(input())
    f[now] = 0

for i in range(2,N+1):
    if f[i] == -1:
        f[i] = (f[i-1] + f[i-2])%NUM

ans = f[N]
print(ans )

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

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

def main_nondp():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    D = [0] * (M+1)
    if M == 0:
        D[0] = N
    else:
        D[0] = A[0] - 1
        for i in range(1, M):
            t = A[i] - A[i-1] - 2
            if t <= -1:
                print(0)
                return
            D[i] = t
        D[M] = N - A[M-1] - 1
    n = 1
    memo = fib_memo(max(D))
    for d in D:
        n = (n * memo[d]) % MOD
    print(n)

def main():
    N, M = i2nn()
    A = ii2nn(M)
    MOD = int(1e+9) + 7
    AS = set(A)
    dp = [0] * (N+9)  # i段目のパターン数
    dp[0] = 1
    for i in range(1, N+1):
        if i in AS:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    print(dp[N])

main()

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
a=[True for _ in range(N+10)]
for _ in range(M):
  a[int(input())]=False
D=1000000007

DP=[0 for _ in range(N+10)]
DP[0]=1
for i in range(N):
  for j in [1,2]:
    if a[i+j]:
      DP[i+j]+=DP[i]
      
print(DP[N]%D)

Submission status: Accepted

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

A = [False] * (N + 1)

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

step = [0] * (N + 1)

step[0] = 1

for s in range(1, N + 1):
    if A[s]:
        step[s] = 0
        continue
    if s == 1:
        step[s] = 1
        continue
    else:
        step[s] = step[s - 1] + step[s - 2]
        step[s] %= 1000000007

print(step[N])

Submission status: Accepted

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

for i, x in enumerate(z):
     if i == 0:
          z[i] = 1
     elif i == 1 and z[i] != 0:
          z[i] = 1
     elif z[i] == 0:
          continue
     elif z[i-1] == 0 and z[i-2] == 0:
          print(0)
          exit()
     else:
          z[i] = z[i-1] + z[i-2]
print(z[-1] % 1000000007)

Submission status: Accepted

Solution code:
mod=10**9+7
def f(a,r):
    s=[[0,0],[0,0]]
    s[0][0]=(a[0][0]*r[0][0]+a[0][1]*r[1][0])%mod
    s[0][1]=(a[0][0]*r[0][1]+a[0][1]*r[1][1])%mod
    s[1][0]=(a[1][0]*r[0][0]+a[1][1]*r[1][0])%mod
    s[1][1]=(a[1][0]*r[0][1]+a[1][1]*r[1][1])%mod
    return s
b=[[1,1],[1,0]]
k=[b]
for i in range(20):
    k.append(f(k[-1],k[-1]))
n,m=map(int,input().split())
t=0
ans=1
if m==0:
    s=bin(n-t)[2:]
    s="0"*(21-len(s))+s
    s=s[::-1]
    p=[[1,0],[0,1]]
    for j in range(21):
        if s[j]=="1":
            p=f(p,k[j])
    ans=(ans*p[0][0])%mod
    print(ans)
else:
    for i in range(m):
        a=int(input())
        if t==a:
            print(0)
            break
        else:
            s=bin(a-1-t)[2:]
            s="0"*(21-len(s))+s
            s=s[::-1]
            p=[[1,0],[0,1]]
            for j in range(21):
                if s[j]=="1":
                    p=f(p,k[j])
            ans=(ans*p[0][0])%mod
            t=a+1
            if i==m-1:
                s=bin(n-t)[2:]
                s="0"*(21-len(s))+s
                s=s[::-1]
                p=[[1,0],[0,1]]
                for j in range(21):
                    if s[j]=="1":
                        p=f(p,k[j])
                ans=(ans*p[0][0])%mod
    else:
        print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

# 0-num段目までのパターン数を取得する
# numは連続した階段の一番高いところが何段目かを意味する


def getPatternNum(num):
    pattern = [0] * num
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern


def solve():
    # 階段の連続してる数のリスト

    if M > 0:
        stepsList = [0] * (M + 1)
        maxSteps = 0
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N + 1]

    # 連続数が一番大きいところの一番上の段を引数でわたす
    pattern = getPatternNum(max(stepsList) + 1)

    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            # 連続段数が３なら一番上の段は０段目から数えて２段目になるため１引く
            total = pattern[stepsList[k] - 1]

        else:
            total = (total * (pattern[stepsList[k] - 1])) % MOD

    return total


print(solve())

Submission status: Accepted

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

s_flag = [True] * (N+1)

for m in xrange(M):
    a = int(raw_input())
    s_flag[a] = False

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

print dp[N]

Submission status: Accepted

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

hole = [False]*(N+1)
a = [int(input()) for _ in range(M)]
for i in a:
  hole[i] = True
  
dp = [0]*(N+1)
dp[0] = 1


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

Submission status: Accepted

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

cnt = [1, 2]

for i in range(1, n - 1):
    cnt.append(cnt[i] + cnt[i - 1])

if m == 0:
    print(cnt[n - 1] % 1000000007)
    exit()

l = [int(input()) for _ in range(m)]

l_diff = [l[0] - 1]
for i in range(1, m):
    l_diff.append(l[i] - l[i - 1] - 2)
l_diff.append(n - l[m - 1] - 1)

for k in range(1, m):
    if l[k] - l[k - 1] == 1:
        print(0)
        exit()


total = 1
for j in l_diff:
    if j == 0:
        pass
    else:
        total *= cnt[j - 1]

print(total % 1000000007)

Submission status: Accepted

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

dp[0] = 1
for i in range(n):
	if a[i]: dp[i] = 0
	if i+1 <= n: dp[i + 1] += dp[i]
	if i+2 <= n: dp[i + 2] += dp[i]
	dp[n] %= MOD
print(dp[n])

Submission status: Accepted

Solution code:
def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N, M] = list(map(lambda x: int(x), inputs[0].split()))
    broke_steps = {}
    for b in map(lambda x: int(x), inputs[1:]):
        broke_steps[b] = True

    SSSS = 1000000007

    patterns = [1]
    for step in range(1, N + 1):
        if step in broke_steps:
            ap = 0
        elif step == 1:
            ap = 1
        else:
            ap = (patterns[step - 1] + patterns[step - 2]) % SSSS
        patterns.append(ap)

    return patterns[-1]


if __name__ == "__main__":
    first = input()
    [N, M] = list(map(lambda x: int(x), first.split()))
    inputs_str = inputs(M)
    inputs_str.insert(0, first)
    ret = solve(inputs_str)
    print(ret)

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
a = list(map(int,sys.stdin))
a.append(0)
prev=0
cur=1
m=0
for i in range(1,n+1):
  if a[m]==i:
    prev,cur = cur,0
    m += 1
  else:
    prev,cur = cur,(cur+prev)%1000000007
print(cur)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

if M == 0:
    ans = fib(N) % (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

if M == 0:
    ans = fib(N) % (10**9+7)


elif M == 1:
    ans = fib(a[0]-1) * fib(N-a[0]-1)
    ans %= (10**9+7)

else:
    ans = fib(a[0]-1)
    for i in range(M-1):
        ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

    ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)