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 -*-
from math import factorial

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

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

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

Submission status: Accepted

Solution code:
n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)

Submission status: Accepted

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

Submission status: Accepted

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

step=[0]*(n+1)
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n-1):
    if step[i]==-1:
        continue
    if step[i+1]!=-1:
        step[i+1]+=step[i]
    if step[i+2]!=-1:
        step[i+2]+=step[i]
print(step[n-1]%c_mod)

Submission status: Accepted

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

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

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])

Submission status: Accepted

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


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

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

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
dp = [0] * (N + 1)
dp[0] = 1
for _ in range(M):
  stair = int(input())
  dp[stair] = 'broken'

for i in range(N + 1):
  if dp[i] != 'broken':
    dp[i] += dp[i - 1] if (i - 1 >= 0) and dp[i - 1] != 'broken' else 0
    dp[i] += dp[i - 2] if i - 2 >= 0 and dp[i - 2] != 'broken' else 0

BASE = 10**9 + 7
print(dp[-1] % BASE)

Submission status: Accepted

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

dp = [1] * (N+1)
for broken in broken_list:
    dp[broken] = 0
for i in range(2, len(dp)):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print (dp[N] % 1000000007)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
listA = [int(input()) for i in range(m)]
listB = [0]*(n+2)
for k in range(m):
    listB[listA[k]] = 1
if(n==1 and listB[1]==0):
    a,b = 1,1
elif(n==1 and listB[1]==1):
    a,b = 0,0
elif(listB[1]==1 and listB[2]==1):
    a,b = 0,0
elif(listB[1]==1):
    a,b = 0,1
elif(listB[2]==1):
    a,b = 1,0
else:
    a,b = 1,2

for j in range(1, n-1):
    if(listB[j+2]!=0):
        a,b = b,0
    if(listB[j+2]==0):
        a,b = b,a+b

print(b%1000000007)

Submission status: Accepted

Solution code:
#踏まない床を0としてフィボナッチ数列を考える
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

arrs = set([int(input()) for _ in range(M)])
anss = [0, 1]
for i in range(1, N+1):
    if i in arrs:
        anss.append(0)
    else:
        anss.append((anss[-2] + anss[-1]) % MOD)
print(anss[-1] % MOD)

Submission status: Accepted

Solution code:
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]:
        Block=Block[1:]+[sum(Block)%mod]
    else:
        Block=Block[1:]+[0]
print(Block[-1])

Submission status: Accepted

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

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])%mod
    if al[i] == 0:
        print(0)
        exit()

print(al[-1])

Submission status: Accepted

Solution code:
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]==1:
        Block=Block[1:]+[sum(Block)%mod]
        
    else:
        Block=Block[1:]+[0]
print(Block[-1])

Submission status: Accepted

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

mod = 10**9+7
dp = {}
for i in range(N+1):
    dp[i] = 1
dp[1] = 0 if 1 in l else 1

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

print(dp[N]%mod)

Submission status: Accepted

Solution code:
def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1)%1000000007)
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        #print(newlist)
        for w in newlist:
            #print(Fib(w-1))
            #print(ans)
            ans = (ans*Fib(w-1))%1000000007
        print(ans)

Submission status: Accepted

Solution code:
def culc(m):
    a1=0
    a2=1
    for i in range(m):
        a2_=a2
        a2=a1+a2
        a1=a2_
    return a2

N,M=map(int,input().split())
a=[-1]
b=[]
for i in range(M):
    a+=[int(input())]
    b+=[a[-1]-a[-2]-2]
    if a[-1]-a[-2]==1:
        b=[]
        break
else:
    b+=[N-a[-1]-1]
if b==[]:
    sm=0
else:
    sm=culc(b[0])
for i in b[1:]:
    sm=sm*culc(i)
print(sm%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

mod = int(1e9+7)

def dfs(i,dp,bad):
    if i == 0:
      return 1
    if i in dp:
      return dp[i]
    dp[i] = 0
    for d in (1,2):
      x = i-d;
      if 0 <= x and x not in bad:
        dp[i] += dfs(x,dp,bad)
        dp[i] %= mod
    return dp[i]

n,m = [int(a) for a in input().split()]
bad = set()
for _ in range(m):
  a = int(input())
  bad.add(a)
print(dfs(n,dict(),bad))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
an = [0]*m

for i in range(m):
#    s = input()
    an[i] = int( input() )
#an[-1] = n

#an.sort()
disjoint = False
for i in range(len(an)-1):
    if an[i] + 1 == an[i+1]:
        disjoint = True


if disjoint:
    print(0)

else:

    mod = 10**9+7
    tab = [0]*(10**5+2)
    tab[0] = 0
    tab[1] = tab[2]= 1

    for i in range(3, len(tab)):
        tab[i] = tab[i-1]+tab[i-2]
#        if i<100:
#            print(tab[i])

    an.append(n)
    prev = 0
    ans = 1
    for a in an:
        index = a-prev + (1 if a == n else 0)
#        print(a,prev,index,tab[index])
        ans *= tab[index]
        ans %= mod
        prev = a+1

    #ans *= tab[n - prev]
    #ans %= 1000000007

    print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
 
h = []
a = 1
b = 0
mod = 10 ** 9 + 7
 
for i in range(m):
    h += [int(input()),]
h += [0,]
    
cur = 0
for i in range(1,n):
    if i == h[cur]:
        a,b = 0,a
        cur += 1
    else:
        a,b = a + b,a
        a %= mod

print((a + b) % mod)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

NG = [False for _ in range(N+1)]
for _ in range(M):
    NG[int(input())] = True

dp = [None for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if NG[1] else 1
for i in range(2, N+1):
    if NG[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

Submission status: Accepted

Solution code:
from collections import deque
 
N, M = map(int, input().split())
 
a = []
aindex = 0
for _ in range(M):
    a.append(int(input()))
 
before1 = 1
before2 = 0
ai=0
if len(a)>0:
    ai = a[aindex]
 
for i in range(1, N+1):
    if i == ai:
        before2 = before1
        before1 = 0
        if aindex < len(a)-1:
            aindex += 1
            ai = a[aindex]
    else:
        current = divmod(before1 + before2, 10**9+7)[1]
        before2 = before1
        before1 = current
 
 
print(before1)

Submission status: Accepted

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

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


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

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

for i in range(M):
    flag_a[a[i]] = -1


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

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

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if flag_a[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_set=set()
 
for index in range(m):
    a_set.add(int(input()))
 
ans_list=[]
 
for index in range(n + 1):
    ans_list.append(0)
 
for index in range(n + 1):
    if index == 0:
        ans_list[index] += 1
        continue
    if index == 1 and (index not in a_set):
        ans_list[index] += ans_list[index - 1]
        continue
    
    if index not in a_set:
        if (index - 1) not in a_set:
            ans_list[index] += ans_list[index - 1]
            ans_list[index] %= 1000000007
        if (index - 2) not in a_set:
            ans_list[index] += ans_list[index - 2]
            ans_list[index] %= 1000000007
 
print(ans_list[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
ng = set([int(input()) for _ in range(M)])
ans = [0, 1] 
for i in range(1, N+1):
  if i in ng:
    ans.append(0)
  else:
    ans.append((ans[-2] + ans[-1]) % MOD)
print(ans[-1] % MOD)

Submission status: Accepted

Solution code:
md = 1000000007
n,m = list(map(int,input().split()))
broken = [0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
dp[0] = 1
for i in range(m):
	broken[int(input())]=1
# print(brok	en)
for j in range(1,n+1):
	if(broken[n-j]==1):
		continue
	if(j==1):
		dp[j]=1
	else:
		dp[j]=(dp[j-1]+dp[j-2])%md
# print(dp)
print(dp[n]%md)

Submission status: Accepted

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

MOD = pow(10, 9) + 7

if n == 1:
  if 1 in alist:
    print(0)
  else:
    print(1)
else:
  memo = [0 for _ in range(n)]
  memo[0] = 0 if 1 in alist else 1
  is_reach = True
  if 1 in alist and 2 in alist:
    is_reach = False
    memo[0] = 0
  elif 1 in alist:
    memo[1] = 1
  else:
    memo[1] = 2

  for i in range(2, n):
    if i+1 in alist:
      memo[i] = 0
    elif i in alist and i-1 in alist:
      memo[i] = 0
      is_reach = False
      break
    elif i in alist:
      memo[i] = memo[i-2]
    elif i-1 in alist:
      memo[i] = memo[i-1]
    else:
      memo[i] = (memo[i-1] + memo[i-2]) % MOD

  if is_reach:
    print(memo[-1])
  else:
    print(0)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mod=10**9+7
last = [0 for i in range(N+1)]
last[0] = 1
bro = [int(input()) for i in range(M)]

broken = [1 for i in range(N+1)]
for i in range(M):
  broken[bro[i]] = 0

for i in range(N):
  if i == 0:
    last[i+1] = last[i]*broken[i]
  else:
    last[i+1] = last[i]*broken[i]+last[i-1]*broken[i-1]
  last[i+1] %= mod
print(last[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, M = map(int, input().split())
m = 10**9+7
F = [0]*N
for _ in range(M):
    F[int(input())-1] = 1

a, b = 0, 1
for n in range(N):
    if F[n]:
        a, b = b, 0
    else:
        a, b = b, (a+b) % m
print(b)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [0]*m

l = [0] * (n+1)
for i in range(m):
  a = int(input())
  l[a] = -1

for i in range(n+1):
  if not l[i] == -1:
    if i == 0 or i == 1:
      l[i] = 1
    else:
      l[i] = max(l[i-2], 0) + max(l[i-1], 0)

print(l[-1] % 1000000007)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for i in range(0, m):
    a = int(raw_input())
    dp[a] = -1

for step in range(1, n + 1):
    if dp[step] < 0:
        continue

    ans = 0
    for prev in [1, 2]:
        if step - prev >= 0 and dp[step - prev] >= 0:
            ans += dp[step - prev]
    dp[step] = ans

# for i in range(0, len(dp)):
#     print(dp[i])

print(dp[n] % 1000000007)

Submission status: Accepted

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

n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)

Submission status: Accepted

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

b = [0]*(n+2)
b[0] = 1

for i in range(m):
    b[int(input())] = -1

for i in range(n):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= 1000000007

print(b[n]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)

Submission status: Accepted

Solution code:
MOD = (10**9 + 7)

     
line = [int(s) for s in input().split()]
     
N, M = line[0], line[1]
     
b = [0]*(N+1)
for i in range(M):
    step_num = int(input().split()[0])
    b[step_num] = 1
        
        
dp = [0]*(N+1)
dp[0] = 1
if b[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1
     
for i in range(2, N+1):
    if b[i] == 1:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1]+dp[i-2])%MOD
print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * (n+2)
D[0] = 1
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if D[i+1] != -1:
        D[i+1] += D[i]
    if D[i+2] != -1:
        D[i+2] += D[i]
    D[i]%=MOD
print(D[n] % MOD)

Submission status: Accepted

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

dp = [0] * (N+1)

dp[0] = 1

for i in range(N):
    for j in range(i+1, min(N, i+2)+1):
        if a[j]:
            dp[j] += dp[i]
            dp[j] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
fiblist = [0] * 100001
fiblist[0] = 1
fiblist[1] = 1
for p in range(2,100001):
    fiblist[p] = (fiblist[p-1]+fiblist[p-2]) % 1000000007

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

if m == 0:
    print(fiblist[n])
else:
    a = []
    for i in range(m):
        a.append(int(input()))

    d = [a[0]-1]
    for j in range(1,m):
        d.append(a[j]-a[j-1]-2)

    d.append(n-a[m-1]-1)




#print(d)

    if (-1 in d) or (-2 in d):
        print(0)
    else:
        ans = 1
        for k in range(m+1):
            ans = (ans * fiblist[d[k]]) % 1000000007

        print(ans)

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())
MOD = 10**9 + 7
dp = [0 for i in range(n+1)]
t = [True for _ in range(n+1)]
for i in range(m):
    a = int(input())
    t[a] = False

dp[0] = 1
for now in range(n):
    for next in range(now+1,min(n+1,now+3)):
        if t[next]:
            dp[next] += dp[now]
            dp[next] %= MOD

print(dp[n])

Submission status: Accepted

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

print(b[N]%1000000007)

Submission status: Accepted

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

pre=-1

li=[-1]

for i in range(m):
  a=int(input())
  if pre+1==a:
    print(0)
    exit()
  pre=a
  li.append(a)

li.append(n+1)

result=[]
for i in range(1,len(li)):
  sum1=1
  sum2=1
  sum3=1
  if 3>li[i]-li[i-1]:
    continue
  for j in range(3,li[i]-li[i-1]):
    sum3=sum1+sum2
    sum1=sum2
    sum2=sum3
  result.append(sum3)

result_=1
for i in result:
  result_*=i
#print(result)  
print(result_%1000000007)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

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

dp = {}
for i in range(n + 1):
    dp[i] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)

Submission status: Accepted

Solution code:
N, M  = map(int, input().split())
a  = {}
for _ in range(M):
  a[int(input())] = 1
sdic  = {}
nn1 = 1
nn2 = 0
for n in reversed(range(N)):
  if n in a:
    nn2 = nn1
    nn1 = 0
    continue
  t = nn1 + nn2
  if t == 0:
    print(0)
    quit()
  nn2 = nn1
  nn1 = t
  
print(nn1%1000000007)

Submission status: Accepted

Solution code:
import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
BIGNUM = 10 ** 9 + 7

if m > 0:
    last_ana = int(input())
    blocks = [last_ana]

    for _ in range(1, m):
        ana = int(input())
        blocks.append(ana - last_ana - 1)
        last_ana = ana
    blocks.append(n - last_ana)
else:
    blocks = [n + 1]

if 0 in blocks:
    ans = 0
else:
    b_max = max(blocks)
    c = [1, 1]
    for i in range(2, b_max):
        ctmp = c[i - 1] + c[i - 2]
        c.append(ctmp % BIGNUM)

    ans = 1
    for num in blocks:
        if num == 1:
            continue
        ans = (ans * c[num - 1]) % BIGNUM
        if ans == 0:
            break

print(ans)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*N
    dp[0] = 1 if is_ok(1,a) else 0

    if N > 1:
        if is_ok(2,a):
            if is_ok(1,a):
                dp[1] = 2
            else:
                dp[1] = 1

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

    print(dp[N-1] % MOD)
    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:
N, M = list(map(int,input().split()))

MOD = 1000000007

b = [0]*(N+2)
b[0] = 1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= MOD

print(b[N]%MOD)

Submission status: Accepted

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

def main():
    if M>0:
        B = [0]*(M+1)
        for i in range(M+1):
            if i==0:
                B[i] = A[i]-1
            elif i==M:
                B[i] = N-A[i-1]-1
            else:
                if A[i]==A[i-1]:
                    B[i] = 0
                else:
                    B[i] = A[i] - A[i-1] - 2
    else:
        B = [N]
    min_B = min(B)
    if min_B<0:
        return 0
    
    max_B = max(B)
    F = [1]*(max_B+1)
    for i in range(max_B+1):
        if i<2:
            pass
        else:
            F[i] = F[i-2] + F[i-1]
    ans = 1
    for b in B:
        ans *= F[b]
        if ans >= DIV:
            ans %= DIV
    return ans

print(main())

Submission status: Accepted

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

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

if M == 0:
  ans = kaidan[N - 1]
else:
  ans = 1

  if a[0] - 1 > 0:
      ans *= kaidan[a[0] - 2]

  for i in range(M-1):
    if((a[i] + 1) > (a[i+1] - 1)):
      ans *= 0
    elif((a[i] + 1) == (a[i+1] - 1)):
      ans *= 1
    else:
      ans *= (kaidan[a[i+1] - a[i] - 3])

  if N - (a[M - 1] + 1) > 0:
      ans *= kaidan[N - (a[M - 1] + 2)]
      
print(ans%1000000007)

Submission status: Accepted

Solution code:
from sys import stdin

n, m = [int(i) for i in stdin.readline().rstrip().split()]
a = [-1] + [int(stdin.readline()) for _ in range(m)] + [n+1]

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

def make_fib(n):
    fib_l[0] = fib_l[1] = 1
    for i in range(2, n):
        fib_l[i] = fib_l[i-1] + fib_l[i-2]

make_fib(n+3)
ret = 1
for i in range(m+1):
    t = a[i+1] - a[i] - 2
    if t < 0:
        ret = 0
        break
    ret *= fib_l[t]
print(ret % 1000000007)

Submission status: Accepted

Solution code:
import sys

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

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

b = []
for i in range(1,len(a)):
    if i == 1:
        b.append(a[1]-1-a[0])
    elif i == len(a)-1:
        b.append(a[i]-(a[i-1]+1))
    else:
        b.append(a[i]-1-(a[i-1]+1))

dp = []
for i in range(10**6):
    if i == 0:
        dp.append(1)
        continue
    if i == 1:
        dp.append(1)
        continue
    if i == 2:
        dp.append(2)
        continue
    dp.append((dp[i-1]+dp[i-2])%mod)

if m == 0:
  print(dp[n])
  sys.exit()
    
for i in range(len(b)):
    l = b[i]
    ans = (ans*dp[l])%mod
    
print(ans)

Submission status: Accepted

Solution code:
# ABC129C - Typical Stairs
import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
skip = set(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in skip else 0
b = 1 if not 1 in skip else 0

for i in range(2, n + 1):
    if a == 0 and b == 0:
        print(0)
        break
    if i in skip:
        a = b
        b = 0
    else:
        tmp = b
        b = (a + b) % MOD
        a = tmp
else:
    print(b)

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
a=[int(input()) for _ in range(M)]
tmp=[1,1,2]
for i in range(N):
    tmp.append(tmp[-1]+tmp[-2])
def func(x):
    if x==-1:
        return 0
    elif x==-2:
        return 1
    else:
        return tmp[x]

if M==0:
    print(func(N)%1000000007)
    exit(0)
s=func(a[0]-1)
for i in range(0, M-1):
    s*=func(a[i+1]-a[i]-2)
s*=func(N-a[M-1]-1)
print(s%1000000007)

Submission status: Accepted

Solution code:
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
n, m = (int(i) for i in input().split())
stops = [int(input())-1 for i in range(m)]
stops.append(n) # ここに止まらないといけない
current = 0
count = 1
for s, stop in enumerate(stops):
    steps = stop - current
    if steps < 0:
        count = 0
        break
    else:
        count *= fib(steps)


    current = stop + 2
print(count % 1000000007)

Submission status: Accepted

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

b = [0]*(N+2)
b[0] = 1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
        b[i] %= 1000000007

print(b[N]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 2)
pat[0] = 1
pat[1] = 1

for i in range(m):
    a = int(input())
    pat[a] = -1

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

print(pat[n])

Submission status: Accepted

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

b = [0]*(N+2)
b[0] = 1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]

print(b[N]%1000000007)

Submission status: Accepted

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

dp = [1]
n_with_a = [[i, False] for i in range(n+1)]



for a in a_s:
    n_with_a[a][1] = True



if 1 in a_s:
    dp.append(0)
else:
    dp.append(1)

for i, is_broken in n_with_a[2:]:
    if is_broken:
        dp.append(0)
    else:
        dp.append((dp[i-1] + dp[i-2]) % 1000000007)

print(dp[-1])

Submission status: Accepted

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

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

	dp[0] = 1
	if dp[1]==-1:
		dp[1] = 0
	else:
		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]

	print(dp[N]%1000000007)

solve()

Submission status: Accepted

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


def climb_stairs(n):
    """
    :param n: int
    :param danger: list
    :return: int
    """
    if n == 1 or n == 2:
        return n
    else:
        a, b = 1, 2
        for i in range(n-2):
            a, b = b, a + b
        return b


now_s = 0
cost = 1
for j in a:
    if now_s == j:
        cost *= 0
        break
    elif now_s == j - 1:
        now_s = j + 1
    else:
        cost *= climb_stairs((j - 1) - now_s)
        now_s = j + 1

if now_s != N:
    cost *= climb_stairs(N - now_s)

print(cost % 1000000007)

Submission status: Accepted

Solution code:
def fib(num):
    a, b = 0, 1 
    for _ in range(num - 1):
#         print(a)
        a, b = a + b, a
    return a + b

def culcC(num):
    if num  < 2:
         return 1
    return fib(num) + fib(num-1)
            
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

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