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
input = sys.stdin.readline


def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Submission status: Accepted

Solution code:
def typical_stairs():
    n, m = map(int, input().split())
    dangerous = set(int(input()) for _ in range(m))
    mod = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in dangerous:
        dp[1] = 1
    for i in range(2, n + 1):
        if i not in dangerous:
            dp[i] = dp[i - 2] + dp[i - 1]
    print(dp[-1] % mod)


if __name__ == '__main__':
    typical_stairs()

Submission status: Accepted

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

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

for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]

print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
stairs = [1] * (N+1)
for m in range(M):
    a = int(input())
    stairs[a] = 0
for n in range(2, N+1):
    stairs[n] = (stairs[n-1] + stairs[n-2])*stairs[n]
print(stairs[N]%1000000007)

Submission status: Accepted

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

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 = map(int, input().split())
if m == 0:
    print(fib(n) % 1000000007)
    exit()
a = [int(input()) for _ in range(m)]

total = 1
i = 0
for x in a:
    if x == i:
        print(0)
        exit()
    total *= fib(x - i - 1)
    i = x + 1
if a[-1] != n:
    total *= fib(n - (a[-1] + 1))

print(total % 1000000007)

Submission status: Accepted

Solution code:
import math
def fib(number):
    a, b = 0, 1
    for _ in range(number):
        a, b = b, a + b
    return b
N, M = map(int, input().split())
a = []
ans = 1
tmp = 0
for _ in range(M):
    a.append(int(input()))
for i in a:
    number = i-tmp
    if i == 1:
        tmp = 2
        continue
    else:
        if number<1:
            print(0)
            exit()
        else:
            ans *= fib(number-1)
            tmp = i+1
print((ans*fib(N-tmp))%1000000007)

Submission status: Accepted

Solution code:
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    # aとbを足した値をmodする(a + b mod p)
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    a = [True] * (N + 1)
    for i in map(int, lines[1:]):
        a[i] = False
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if a[1] else 0
    for i in range(2, N + 1):
        if a[i]:
            dp[i] = modadd(dp[i - 1], dp[i - 2])
    print(dp[N])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    # aとbを足した値をmodする(a + b mod p)
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    M = [True] * (N + 1)
    for i in map(int, lines[1:]):
        M[i] = False
    dp = [0] * (N + 1)
    dp[:2] = 1, 1 if M[1] else 0
    for i in range(2, N + 1):
        if M[i]:
            dp[i] = modadd(dp[i - 1], dp[i - 2])
    print(dp[N])
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin
INF = int(1e9+7)


def modadd(a, b):
    # aとbを足した値をmodする(a + b mod p)
    return (a + b) % INF


def main():
    lines = stdin.readlines()
    N = int(lines[0].split()[0])
    M = [True] * (N + 1)
    for i in map(int, lines[1:]):
        M[i] = False
    dp = [0] * (N + 1)
    dp[0] = 1
    for cur in range(N + 1):
        for i in range(cur + 1, min(cur + 2, N) + 1):
            if M[i]:
                dp[i] = modadd(dp[cur], dp[i])
    print(dp[N])
    return


main()

Submission status: Accepted

Solution code:
def run():
  N, M = map(int, input().split())
  stairs = [1] * (N+1)
  for m in range(M):
    a = int(input())
    stairs[a] = 0
  #print(stairs)
  for n in range(2, N+1):
    stairs[n] = (stairs[n-1] + stairs[n-2])*stairs[n]
  print(stairs[N]%1000000007)
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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

# 壊れた階段が2つ以上連続しているとき、0を出力して終了
for i in range(1,M):
    if a[i]-a[i-1] == 1:
        print(0)
        exit()
        
# 壊れた階段が連続していないならば、ゴールする方法が少なくとも1通り存在する
# stair[i]を、i段目の階段に到達する方法の数とする。ただし、i段目が壊れた階段であるときstair[i] = 0
stair = [-1]*(N+1)
stair[0] = 1
stair[1] = 1

for i in range(M):
    stair[a[i]] = 0
    
for i in range(2,N+1):
    if stair[i] != 0:
        stair[i] = stair[i-1] + stair[i-2]

print(stair[-1]%1000000007)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(2, n + 1):
    if dp[i] != 0:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:
#bin/usr/env python3

n,m = map(int, input().split())
mod = 10**9+7

br = [0 for i in range(n+2)]
for i in range(m):
    a = int(input())
    br[a] = 1

can = [0 for i in range(n+2)]

can[1] = 1
can[2] = 2

if br[1] == 1:
    can[1] = 0
    can[2] = 1
if br[2] == 1:
    can[1] = 1
    can[2] = 0
if br[1] == 1 and br[2] == 1:
    can[1] = 0
    can[2] = 0

for i in range(3, n+1):
    if br[i]!=1 :
        can[i] = (can[i-1] + can[i-2])%mod
    
    else:
        can[i] = 0

print(can[n])

Submission status: Accepted

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

b = [0] * (n + 1)
b[0] = 1
if 1 not in a:
    b[1] = 1
for i in range(2, n + 1):
    if i in a:
        b[i] = 0
    else:
        b[i] = b[i - 1] + b[i - 2]
print(b[n] % 1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# INF=10^7程度じゃインプットの桁数ふえた時に更新処理が正しく走らず結果エラーになってしまう..
MOD_KEY = 1000000007
n, m = map(int, input().split())
dp = [0]*(n+1)
for i in range(m):
    a = int(input())
    dp[a] = -1

dp[0] = 1

for i in range(n):
    # print("i: " + str(i))
    for j in range(1, 3):
        #print("j: " + str(j))
        if i + j < n+1:
            if (dp[i+j] >= 0) & (dp[i] >= 0):
                dp[i+j] += dp[i]
                dp[i+j] %= MOD_KEY

if dp[n] > 0:
    print(dp[n])
else:
    print(0)

Submission status: Accepted

Solution code:
CONST = 1000000007

def noboru(n):
    a1 = 1
    a2 = 2
    ans = 0
    if (n == 0 or n == 1): return a1
    elif (n == 2): return a2
    else:
        for i in range(1, n-1):
            ans = a2 + a1
            a1 = a2
            a2 = ans
        return a2

def func(N, M, a):
    ans = 1
    pos = 0
    for i in range(M):
        if (pos == a[i]):
            return 0
        else:
            ans = (ans * noboru(a[i] - pos - 1)) % CONST
            pos = a[i] + 1
    ans = (ans * noboru(N - pos)) % CONST
    return ans

N, M = map(int, input().split(" "))
a = [int(input()) for _ in range(M)]
print(func(N, M, a))

Submission status: Accepted

Solution code:
BASE =  1000000007

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = []
    for i in range(M):
        not_available.append(int(input()))
    x = 0
    y = 1
    predicted_next = 1
    is_available = [True] * N
    for idx in not_available:
        is_available[idx - 1] = False

    for flag in is_available:
        if flag:
            z = x + y
            x = y
            y = z
        else:
            x = y
            y = 0

    print(y % BASE)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
broken = [False] * (N + 1)
dp = [0] * (N + 1)
for a in A:
    broken[a] = True

dp[0] = 1
if broken[1]:
    dp[1] = 0
else:
    dp[1] = 1


for i in range(2,N+1):
    if broken[i] and broken[i-1]:
        print(0)
        exit(0)
    if broken[i]:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
#print(dp)
print(dp[N] % 1000000007)
#print(13 % 4)

Submission status: Accepted

Solution code:
#129c
import sys
sys.setrecursionlimit(1000000)

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

now_step = 0
ans = 1
calculated_jump = {}
mod_number = 1000000007 

#開いている段数の移動パターンを算出する関数
def jump(now_step):
    
    if now_step in calculated_jump:
        return calculated_jump[now_step]
    else:
        if now_step == 2:
            return 2
        elif now_step == 1:
            return 1
        else:
            if now_step not in calculated_jump:
                calculated_jump[now_step] = jump(now_step-1) + jump(now_step-2)
                return jump(now_step-1) + jump(now_step-2)

for _ in range(M):
    a = int(input())
    
    if a == now_step:
        print("0")
        break
    elif a - 1 - now_step != 0: #左記成立時は1通りしかない。
        target_step_count = a - 1 - now_step #aは踏んではいけない段なので、その前がターゲット
        ans = ans * jump(target_step_count) % mod_number
            
    now_step = a + 1

else:
    if now_step != N:
        target_step_count = N - now_step
        ans = ans * jump(target_step_count) % mod_number
    
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def fib(n):
    if n==1:
        a=1
        return a
    if n==2:
        a=1
        return a
    a0=1
    a1=1
    cnt=2
    while cnt <n:
        a=a0+a1
        cnt+=1
        a0=a1
        a1=a
    return a


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

mod=10**9+7

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

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)
ans=(ans*c)%mod

print(ans)

Submission status: Accepted

Solution code:
def fib(n):
    if n==1:
        ans=[1]
        return ans

    ans=[1,1]
    cnt=2
    while cnt <n:
        ans.append(ans[-2]+ans[-1])
        cnt+=1
    return ans

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

mod=10**9+7

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

a0=-1
ans=1
for i in range(M):
    a=int(input())
    n=(a-1)-(a0+1)
    if a-a0==1:
        print(0)
        exit()
    c=fib(n+1)[-1]
    ans=(ans*c)%mod
    a0=a

a = N+1
n = (a - 1) - (a0 + 1)
c = fib(n+1)[-1]
ans=(ans*c)%mod

print(ans)

Submission status: Accepted

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())-1
    chk[a]=False

mod=10**9+7

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

f=[0]*(N+1)

if not chk[0]:
    f[0]=0
else:
    f[0]=1

if not chk[1]:
    f[1]=0
else:
    f[1]=f[0]+1

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

    f[i]=f[i]%mod

print(f[N-1])

Submission status: Accepted

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

chk=[True]*(10**5+1)
for i in range(M):
    a=int(input())
    chk[a]=False

mod=10**9+7

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

f=[0]*(N+1)
f[0]=1
if chk[1]:
    f[1]=1
else:
    f[1]=0


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

print(f[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [0] * (10**5+10)
jud = [True]*(10**5)
for k in range(m):
    a = int(input())
    jud[a] = False

dp[0] = 1
if jud[1]:
    dp[1] = 1
else:
    dp[1] = 0

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
M = 1000000007
dp = {}
dp[0] = 1
for i in range(1, n+1):
    if i in a:
        dp[i] = 0
        continue
    if i - 2 < 0:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % M)

Submission status: Accepted

Solution code:
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
for _ in  range(m):
    a.add(int(input()))

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
p = 10**9 + 7
n,m = list(map(int, input().split()))
a = set()
for _ in  range(m):
    a.add(int(input()))

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

for i in range(n):
    if i+2 not in a:
        dp[i+2] += dp[i]%p
    if i+1 not in a:
        dp[i+1] += dp[i]%p

print(dp[-2]%p)

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
fib = [1,1]
for i in range(n):
    fib.append((fib[i]+fib[i+1])%1000000007)
if m == 0:
    print(fib[n]%1000000007)
    sys.exit()
answer = fib[a[0]-1]
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        answer = 0
    else:
        answer = answer * fib[a[i+1]-a[i]-2] % 1000000007
answer = answer * fib[n-a[m-1]-1] % 1000000007
print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

ai=0
n1,n2=0,1
for i in range(1,n+1):
      if ai<m and i==A[ai]:
            ai+=1
            n1=n2
            n2=0
      else:
            tmp=n2
            n2=(n1+n2)%1000000007
            n1=tmp
print(n2)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
ai=0
n1,n2=0,1
for i in range(1,N+1):
    if ai<M and i==A[ai]:
        ai+=1
        n1=n2
        n2=0
    else:
        tmp=n2
        n2=(n1+n2)%1000000007
        n1=tmp
print(n2)

Submission status: Accepted

Solution code:
N , M = map(int ,input().split())
mod = 10 ** 9 + 7
A = []
crash = 0
idx = 0
for i in range(M):
    A.append(int(input()))
    if i == 0:
        crash = A[0]
    if A[i] - 1 == A[i - 1] and i > 0:
        print("0")
        exit()
dp = [0] * (N + 1)
dp[0] = 1

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

Submission status: Accepted

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

ans=1


def fb(num):
    """num番目のフィボナッチ数を返す
    """
    a, b = 1, 1
    for i in range(num):
        a, b = a + b, a
    return b
    
#print(fb(3))

if m==0:
	ans=ans*fb(n)
	
else:
	for i in range(m-1):
		if (lista[i]+1==lista[i+1])&(m>=2):
			ans=0
  	
  	
	else:
		lista.append(n)
		if lista[0]!=1:
				ans=ans*(fb(lista[0]-1))
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		 
					
		if lista[0]==1:
				for i in range(1,m):
						ans=ans*(fb(lista[i]-lista[i-1]-2))
					
		
		ans= ans*(fb(lista[m]-lista[m-1]-1))
		
print(ans%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
if not alist[1]:
    dp[1] = 1
for i in range(2,N+1):
    if alist[i]:
        continue
    dp[i] += dp[i-1] + dp[i-2]

print(dp[N]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(int)
    for i in range(m):
        d[int(input().rstrip('\n'))]
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in d else 0
    dp[1] = 1 if 1 not in d else 0
    for i in range(2, len(dp)):
        dp[i] = (dp[i-1] + dp[i-2]) % (1000000007) if i not in d else 0
    print(dp[-1])


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def f(i):
    if dp[i] != -1 and dp[i] != 0: return dp[i]
    if dp[i] == -1: return 0

    if i == -1:
        return f(i - 1)
    elif i > 1:
        dp[i] = f(i - 1) + f(i - 2)
    else:
        dp[i] = f(i - 1)
    return dp[i]

n,m = map(int,input().split())
dp = [0]*(n+1)
ary = [int(input()) for _ in range(m)]
dp[0] = 1
for i in ary:
    dp[i] = -1
    if dp[i-1] == -1 and dp[i] == -1:print(0);exit()
print(f(n)%(10**9+7))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dp = [0]*(n+1)
ary = [int(input()) for _ in range(m)]
dp[0] = 1
for i in ary:
    dp[i] = -1
    if dp[i-1] == -1 and dp[i] == -1:print(0);exit()
for i in range(1,n+1):
    if dp[i] == -1:continue
    elif dp[i-1] == -1:dp[i] = dp[i-2]
    elif dp[i-2] == -1:dp[i] = dp[i-1]
    elif i > 1: dp[i] = dp[i-1]+dp[i-2]
    else: dp[i] = dp[i-1]
print(dp[n]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    # N = int(input())
    N,M = map(int, input().split())
    MOD = 1000000007
    AS = [int(input()) for _ in range(M)]
    AS = set(AS)
    dp = [0]*(N+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in AS else 0
    for n in range(2,N+1):
        if n in AS: continue
        if n-1 not in AS:
            dp[n] += dp[n-1]
            dp[n] %= MOD
        if n-2 not in AS:
            dp[n] += dp[n-2]
            dp[n] %= MOD
    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

p=10**9+7
N,M=map(int,input().split())
a=[]
for i in range(M):
    a.append(int(input()))
x=[0 for i in range(N+1)]
x[0]=1
if 1 in a:
    x[1]=0
else:
    x[1]=x[0]
for i in range(2,N+1):
    if bisect.bisect_right(a,i-1)-bisect.bisect_left(a,i-1)==0: # i-1 not in a
        x[i]+=x[i-1]
    if bisect.bisect_right(a,i-2)-bisect.bisect_left(a,i-2)==0: # i-2 not in a
        x[i]+=x[i-2]
    x[i]%=p

print(x[N])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
kaidan = [-1] * (n + 1)
for i in range(len(l)):
    kaidan[l[i][0]] = 0
for i in range(1, len(kaidan) + 1):
    if not (kaidan[-i] == 0):
        if i == 1:
            kaidan[-1] = 1
        elif i == 2:
            kaidan[-2] = kaidan[-1]
        else:
            kaidan[-i] = kaidan[-i + 1] + kaidan[-i + 2]
print(kaidan[0] % 1000000007)

Submission status: Accepted

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

lists=[]
for i in range(m):
    a=int(input())
    lists.append(a)

fiblist=[1,1]
for j in range(10**5):
    nums=(fiblist[-1]+fiblist[-2])%(10**9+7)
    fiblist.append(nums)
lists.insert(0,0)
lists.append(n)
ans=1
if m>=2:
    for i in range(m+1):
        if i==0:
            ans=ans*fiblist[lists[1]-lists[0]-1]
            ans=ans%(10**9+7)
        elif i==m:
            ans=ans*fiblist[lists[m+1]-lists[m]-1]
            ans=ans%(10**9+7)
        elif i!=0 and i!=m:
            if lists[i+1]-lists[i]==1:
                ans=0
                break
            else:
                ans=ans*fiblist[lists[i+1]-lists[i]-2]
                ans=ans%(10**9+7)
    print(ans) 
if m==0:
    print(fiblist[n])
if m==1:
    print(fiblist[lists[1]-1]*fiblist[n-lists[1]-1]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def f(num):
    if memo[num] != 0 and memo[num] != -1:return memo[num]

    if memo[num] == -1:
        return f(num-1)
    if memo[num-1] == -1:
        memo[num] = f(num-1)
    elif memo[num-2] == -1:
        memo[num] = f(num-1)
    elif num > 1:memo[num] = f(num-1)+memo[num-2]
    else:memo[num] = f(num-1)


    return memo[num]

n,m = map(int,input().split())
memo = [0 for _ in range(n+1)]
for i in [int(input()) for _ in range(m)]:
    memo[i] = -1
    if memo[i] == -1 and memo[i-1] == -1:print(0);exit()
memo[0] = 1
print(f(n)%(10**9+7))

Submission status: Accepted

Solution code:
def main():

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def fibonacci(N):
    prev = []
    for i in range(1, N+1):
        if i == 1 or i == 2:
            prev.append(1)
        else:
            prev.append(prev[-2] + prev[-1])
    return(prev[-1])


a.append(N + 1)

for i in range(M+1):
    dis = a[i] - pos
    if dis == 0:
        ans = 0
        break
    ans *= fibonacci(dis)
    pos = a[i]+1
print(ans % ((10**9)+7))

Submission status: Accepted

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

oks = [True for _ in range(n + 1)]
for _ in range(m):
  a = int(input())  
  oks[a]=False


dp = [0 for _ in range(n+1)]
dp[0] = 1
for now in range(n):
  for next in range(now+1, min(n, now+2)+1):
    if(oks[next]):
      dp[next]+=dp[now]
      dp[next]%=10**9+7
print(dp[n])

Submission status: Accepted

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



ary = []
flag = 0
n, m = map(int, input().split())
for i in range(m):
  a = int(input())
  ary.append(a)
  if ary[i] == ary[i-1]+1:
    flag = 1
    break
if flag == 1:
  print(0)
else:
  ary.append(n+1)
  count = max(1,ary[0])
  count = fb(count)
  for i in range(1,len(ary)):
    sa = ary[i]-ary[i-1]-1
    if sa == 0:
      pass
    else:
        count*=fb(sa)
  count = count%1000000007
  print(count)

Submission status: Accepted

Solution code:
import sys

n,m = map(int,input().split())
t = [0] * 2
t[0] = 1
t[1] = 2
a = []
for _ in range(m):
	a.append(int(input()))
mod = 10**9 + 7

for i in range(1,m):
	if a[i] - a[i-1] == 1:
		print(0)
		sys.exit()
a.append(n+1)

l = []
dan = 0
for i in range(m+1):
	l.append(a[i]-1-dan)
	dan = a[i] + 1
	if dan == n+2:
		break

if max(l) > 2:
	for i in range(2,max(l)):
		t.append(t[i-1] + t[i-2])

ans = 1
for i in l:
	if i != 0 and t[i-1] != 0:
		ans *= t[i-1]
		ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
a=set(int(input()) for i in range(m))
ans = [0 for _ in range(n)]

for i in range(n):
    if i+1 in a:
        ans[i] = 0
    else:
        if i == 0:
            ans[i] = 1
        elif i == 1:
            ans[i] = 1+ans[i-1]
        else:
            ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[-1])

Submission status: Accepted

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

dp=[0]*(n+1)
dp[0]=1

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

Submission status: Accepted

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

mod = 10**9+7
for _ in range(m):
    a.append(int(input()))

dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
if a:
    if a[0]==1:
        dp[1] = 0

A = set(a)
 
for i in range(2,n+1):
    if i not in A:
        dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[n])

Submission status: Accepted

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

#フィボナッチ数列
def Fib(n):
    a, b = 1, 1
    if n == 0:
        return 0
    elif n== 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていた理由:
#・Fib(0)が定義されていなかったから
#・フィボナッチ数列を再帰的(=Fib(n-1)+Fib(n-2))で定義していると、
#Nが大きい(100000とか）のときに深く潜りすぎるのでRE

if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [1] * (N+2)
for _ in range(M):
    a = int(input())
    A[a+1] = 0
dp = [0] * (N+2)
dp[1] = 1
e = 1e9 + 7
for i in range(2, N+2):
    if A[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[-1]))

Submission status: Accepted

Solution code:
#C問題
mod = 10**9+7
N,M = map(int,input().split())

step = []
for i in range(N+2):
    if i <= 1:
        step.append(1)
    elif i == 2:
        step.append(1)
    else:
        step.append(step[i-1]+step[i-2])
    
A = []
for j in range(M):
    A.append(int(input()))

stairs = []
flag = 0
old = -1
for a in A:
    if a-old == 1:
        flag = 1
        break
    else:
        stairs.append(a-old-1)
        old = a
stairs.append(N-old)

if flag == 1:
    print(0)
else:
    #print(stairs)
    ans = 1
    for s in stairs:
        ans*=step[s]
        
    print(ans%mod)

Submission status: Accepted

Solution code:
import bisect

N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
dp = [0] * (N+2)
dp[0] = 1

for i in range(1, N+1):
  idx = bisect.bisect_left(A, i)
  if idx < len(A) and A[idx] == i:
    continue
  if i < 2:
    dp[i] = dp[i-1]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
a = [1] * (N+1)
for i in range(M):
    a[int(input())] = 0
mod = 1000000007
ans = [0] * (N+1)
ans[0] = 1
for i in range(1,N+1):
     ans[i] = (ans[i-2]*a[i-2] + ans[i-1]*a[i-1]) % mod
print(ans[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
mod = 1000000007

n, m  = map(int, input().split())
dp = [0 for _ in range(n+1)]
broken = [False for _ in range(n+1)]
for _ in range(m):
    a = int(input())
    broken[a] = True

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

print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [1] * (N + 1)
ans = [0] * (N + 1)
ans[0] = 1
for _ in range(M):
    A[int(input())] = 0
for i in range(1, N + 1):
    ans[i] = (ans[i - 2] * A[i - 2] + ans[i - 1] * A[i - 1]) % 1000000007

print(ans[N])