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

n, m = map(int, input().split())
broken = set([int(input()) for _ in range(m)]) # ここが'list'だとPypyでも通らない
#print(broken_steps)

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0 # 連続して壊れている階段を記録, '2'でゴール不可
        if 1 in broken: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken: # 階段が壊れている場合...
                cnt += 1
                if cnt == 2: # 2段連続壊れている場合は...
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)

Submission status: Accepted

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

n, m = map(int, input().split())
broken_steps = set([int(input()) for _ in range(m)])
#print(broken_steps)

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0
        if 1 in broken_steps: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken_steps: # 階段が壊れている場合...
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)

Submission status: Accepted

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

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

if dp[0] != -1:
  dp[0] = 1
if dp[1] != -1:
  dp[1] = 1

mod = 10 ** 9 + 7

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

print(dp[n])

Submission status: Accepted

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

mod = 1000000007

from collections import deque

d = deque()

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

old = 0
new = 1

for i in range(1, n+1):
    if len(d):
        if i != d[0]:
            old, new = new, (old+new) % mod
        else:
            old, new = new, 0
            d.popleft()
    else:
        old, new = new, (old+new) % mod



print(new)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])

Submission status: Accepted

Solution code:
import sys

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

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

dp[0]=1
if dp[1]!=-1:
	dp[1]=1

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

print(dp[N]%1000000007)

Submission status: Accepted

Solution code:
def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    # n, m = map(int, readline().split())
    # a = set(map(int, read().split()))
    n, m = map(int, input().split())
    a = set(int(input()) for i in range(m))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = set(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 動的計画法

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

ban = [False] * (n+1)

for i in range(m):
    a = int(input())
    ban[a] = True

# dpテーブル
dp = [0] * (n+1)
dp[0] = 1

# 貰うdp
for i in range(n):
    # ban[i] が　True ならば dp[i] = 0
    if (ban[i]):
        dp[i] = 0
    
    if (i + 1) <= n:
        dp[i+1] += dp[i]
    if (i + 2) <= n:
        dp[i+2] += dp[i]

mod = 10**9 + 7
print(dp[n] % mod)

Submission status: Accepted

Solution code:
S=[0]*100010
S[1]=1
S[2]=1
for i in range(3,100010):
    S[i]=(S[i-2]+S[i-1])%1000000007

N,M=map(int,input().split())
if M==0:
    ans=1
    print(S[N+1])
    exit()
T=[]
for i in range(M):
    T.append(int(input()))
    if i>=1:
        if T[i]-1==T[i-1]:
            print(0)
            exit()

U=[]
U.append(T[0])
for i in range(1,M):
    U.append(T[i]-T[i-1]-1)

U.append(N-T[M-1])

ans=1
for i in range(len(U)):
    ans=(ans*S[U[i]])%1000000007
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = set(map(int, read().split()))

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
cnt = 0
for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print('0')
            exit()
print(dp[n])

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()
mod = 10**9 + 7


def solve():
    N, M = map(int, input().split())
    A = [0 for _ in range(N + 1)]
    for i in range(M):
        a = int(input())
        A[a] = 1

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

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

    print(dp[N])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    a = set([int(input()) for i in range(M)])
    mod = 10**9+7
    #dp[i]　iの位置に到達する最小の値
    dp = [0]*(N+1)
    dp[0] = 1
    for i in range(N):
        if (i+1)<=N and (not i+1 in a):
            dp[i+1] += dp[i]
            dp[i+1] %= mod
        if (i+2)<=N and (not i+2 in a):
            dp[i+2] += dp[i]
            dp[i+2] %= mod

    print(dp[N])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])
q = collections.deque([1])
mod = (10 ** 9) + 7
w = 1
while(w <= n):
	if w == 0:
		q.append(1)
	else:
		q.append((1 if w not in forbidden else 0) * (sum(q) % mod))
	w += 1
	if len(q) == 3: q.popleft() 
print q[-1]

Submission status: Accepted

Solution code:
import collections
q = collections.deque([1])
n,m = map(int, raw_input().split(' '))
forbidden = set([int(raw_input()) for _ in range(m)])

mod = (10 ** 9) + 7
for w in range(1,n+1):
	if w not in forbidden:
		q.append(sum(q) % mod)
	else:
		q.append(0)
	if len(q) == 3:
		q.popleft() 
print q[-1]

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 + 2)
DP[0] = 1
STEP = set(range(N + 1)) - set(A)

for s in STEP:
  if s + 1 in STEP:
    DP[s + 1] += DP[s]
  if s + 2 in STEP:
    DP[s + 2] += DP[s]

print(DP[N]%mod)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(int(input()))
a=set(b)
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    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 = []
for m in range(M):
    A.append(int(input()))


broken = [0]*(N+2)
for a in A:
    broken[a] = 1

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

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

Submission status: Accepted

Solution code:
r = 10 ** 9 + 7
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
a = sorted(set(a))

if 1 in a:
    dp[1] = 0
    del a[0]
else:
    dp[1] = 1

if N == 1:
    print(dp[1])
    exit()

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

if N == 2:
    print(dp[2])
    exit()

for i in range(1,N-1):
    if a == [] :
        dp[i+2] = (dp[i] + dp[i+1]) % r
    elif i+2 == a[0]:
        dp[i+2] = 0
        del a[0]
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % r

print(dp[N])

Submission status: Accepted

Solution code:
import sys

N, M = map(int, sys.stdin.readline().strip().split())
A = set()
for _ in range(M):
    A.add(int(sys.stdin.readline()))

# i段目の階段への到達方法の数
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

print(dp[N])

Submission status: Accepted

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

a = []
for _ in range(m):
    tmp = int(input())
    a.append(tmp)
a = set(a)

dp = [0] * (10**5 + 7)
dp[0] = 1

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

print(dp[n]%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

from itertools import product

def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def Fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]
    
    
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

x=0
L=[]
for i in range(M):
    L += [A[i] - 1 - x]
    x = A[i] + 1
L += [N - x]
L = [Fib(i+1)%1000000007 for  i in L]

X=1
for i in range(len(L)):
    X *= L[i]
    X %= 1000000007 
print(X)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = [1] * (n + 1)
    for _ in range(m):
        idx = int(input())
        a[idx] = 0

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

    print(dp[-1] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import itertools
import collections
N,M = map(int, input().split())
A = [list(list(input().split())) for i in range(M)]
AList = list(itertools.chain.from_iterable(A))
cnt = collections.Counter(AList)
INF = 10**9+7
dp = [INF]*(N+1)
MOD = 10**9+7

def solve(val1, val2):
    if val1 == 0 and val2 == 0:
        print(0)
        exit()
    else:
        return val1 + val2

for i in range(N+1):
    if i == 0:
        dp[0] = 1
    elif i == 1:
        if cnt['1'] == 0:
            dp[1] = 1
        else:
            dp[1] = 0
    else:
        if cnt[str(i)] == 1:
            dp[i] = 0
        else:
            dp[i] = solve(dp[i-2], dp[i-1])
print(dp[N] % MOD)

Submission status: Accepted

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

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

Submission status: Accepted

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

safe_out = [True] * (n + 1)
for i in range(m):
    a = int(input())
    safe_out[a] = False
    
way_cnt = [0] * (n + 1)
way_cnt[0] = 1
way_cnt[1] = 1

for i in range(2, n + 1):
    if safe_out[i - 1]:
        way_cnt[i] += way_cnt[i - 1]
    
    if safe_out[i - 2]:
        way_cnt[i] += way_cnt[i - 2]
        
    way_cnt[i] %= (10**9 + 7)

print(way_cnt[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
h = [0]*(N+1)
mod = 1000000007

for _ in range(M):
  h[int(input())] = 1

for i in range(1,N):
  if h[i]+h[i+1] == 2:
    print(0)
    exit()

memo = [0]*(N+1)
memo[0] = 1
if h[1] == 0:
  memo[1] = 1
else:
  memo[1] = 0

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Q = 1000000007
A = set()
for _ in range(M):
    A.add(int(input()))

p = []
for i in range(1, N+1):
    if i in A:
        p.append(0)
    elif i == 1:
        p.append(1)
    elif i == 2:
        p.append(p[0] + 1)
    else:
        p.append(p[i-2] + p[i-3])

print(p[N-1] % Q)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[n] % 1000000007)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    n,m=map(int,readline().split())
    a=[int(readline()) for _ in range(m)]
    flags=[True]*(n+1)
    for i in a:
        flags[i]=False

    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        if flags[i]==False:
            continue
        elif i==1:
            dp[i]+=dp[i-1]
        else:
            dp[i]+=dp[i-1]+dp[i-2]
        dp[i]%=mod

    print(dp[-1])
        
if __name__=="__main__":
    main()

Submission status: Accepted

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

stairs[0] = 1
if stairs[1] != "*":
    stairs[1] = 1

for i in range(2, N+1):
    if stairs[i] != "*":
        if stairs[i-1] != "*" and stairs[i-2] != "*":
            stairs[i] = (stairs[i-1] + stairs[i-2]) % q
        elif stairs[i-1] == "*" and stairs[i-2] != "*":
            stairs[i] = stairs[i-2] % q
        elif stairs[i-1] != "*" and stairs[i-2] == "*":
            stairs[i] = stairs[i-1] % q
        else:
            stairs[i] = 0
print(stairs[N] % q)

Submission status: Accepted

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

mod = 10**9 + 7

no = [False] * (n+1)

for _ in range(m):
    a = int(input())
    no[a] = True
    
dp = [0] * (n+1)
dp[0] = 1

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

Submission status: Accepted

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


for i in range(M):
    step[a[i]] = False

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

print(dp[-1])

Submission status: Accepted

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

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

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

ans = dp[N] % mod
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

CONST = 1000000007

n,m = map(int,input().split())
lis = deque([int(input()) for _ in range(m)])
lis.append(n+1)
nhole = lis.popleft()

memo = deque([0, 1])
for i in range(1,n+1):
    if i == nhole:
        memo.append(0)
        nhole = lis.popleft()
    else:
        memo.append((memo[-1] + memo[-2])%CONST)
print(memo[-1])

Submission status: Accepted

Solution code:
import math
from collections import deque

memo = deque([1, 2])
floor = 1
def search(x):
    global memo, floor
    while x > floor:
        memo.append(memo[-1] + memo[-2])
        floor += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    ans = (ans * search(v)) % CONST
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))
 
MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1#二段目の調節　0段目の場合の数
 
for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD

ans = dp[N]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

N,M = map(int,input().split())
is_broken = [0]*(N+1)#1-broken 0-not
for i in range(0,M,1):
    a = int(input())
    is_broken[a]=1

method = [0]*(N+1)
method[0]=1
method[1]=1-is_broken[1]
for i in range(2,N+1,1):
    if is_broken[i]== 0:
        method[i]= (method[i-1]+method[i-2])%MOD
    else:
        method[i]=0
print(method[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs
    #nCr = (factorials[n]%MOD * invs[r]%MOD * invs[n-r]%MOD)%MOD
def main():
    MOD = 1000000007

    n,m=map(int, input().split())
    dd={i:0 for i in range(0,n+1)}
    a = [2]*(n)
    a[-1]=1
    for i in range(m):
        s  = int(input())
        dd[s]+=1
    dp=[0]*(n+1)
    dp[0]=1
    if dd[1]==0:
        dp[1]=1
    else:
        dp[2] = 1
        if dd[2]>0:
            print(0)
            exit()
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
        if dd[i]>0:
            dp[i]=0
    print(dp[n]%MOD)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

now = 0
point = 1
mod = 10**9+7

def fib(n,mod):
    a, b = 1, 1
    for _ in range(n):
        a, b = b %mod, (a + b)%mod
    return a%mod

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

for i in a:
    point *= fib((i-1-now),mod)
    point %= mod
    now = i+1
    if now == n:
        break

point *= fib(n-now,mod)
point %= mod

print(point)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ 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
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD
 
ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
flag = [True] * (n + 1)
cnt = [0] * (n + 1)
for i in range(m):
    a = int(input())
    flag[a] = False

for i in range(n, -1, -1):
    if flag[i]:
        if i == n or i == n - 1:
            cnt[i] = 1
        else:
            cnt[i] = (cnt[i + 1] + cnt[i + 2]) % (10 ** 9 + 7)
    else:
        cnt[i] = 0
print (cnt[0])

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * N
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)

Submission status: Accepted

Solution code:

N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ 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
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD

ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
mod = 10**9 + 7

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

Submission status: Accepted

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

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])

Submission status: Accepted

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

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

for i in range(2, N+1):
    # 壊れた床がなく単純に求める場合
    #dp[i] = dp[i-1]+dp[i-2]

    if not i-1 in A:
        dp[i] += dp[i-1]
    if not i-2 in A:
        dp[i] += dp[i-2]

print(dp[N] % 1000000007)

Submission status: Accepted

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

A = set(A)

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

for i in range(n):
    if i in A:
        continue
    if i+1 <= n and i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if i+2 <= n and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
#print(dp)
print(dp[-1]%mod)

Submission status: Accepted

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

Submission status: Accepted

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

step = [0]*N

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

mod = int(1e9+7)

dp = [0]*N

if N == 1:
    if step[0]:
        print(0)
    else:
        print(1)
    exit()

if not step[0] and not step[1]:
    dp[0] = 1
    dp[1] = 2
elif step[0] and not step[1]:
    dp[0] = 0
    dp[1] = 1
elif not step[0] and step[1]:
    dp[0] = 1
    dp[1] = 0
else:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]
is_broken = [0]*(N+1)
for x in a:
	is_broken[x] = 1

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

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
s = set(a)
dp = [0]*(N+1)
MOD = 10**9+7
dp[0] = 1

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys
class Fib:
  def __init__(self):
    self.memo = {}
  def calc(self, n):
    if n == 1 or n == 2:
      self.memo[n] = 1
      return 1
    if n <= 0:
      self.memo[n] = 0
      return 0
    if n in self.memo.keys():
      return self.memo[n]
    self.memo[n] = self.calc(n - 1) + self.calc(n - 2)
    return self.memo[n]
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
ans = 1
mod = 10 ** 9 + 7
pre = -1
for i in range(M):
  a = int(input())
  if a == 1:
    pre = a
    continue
  if a == pre + 1 and pre != 0:
    print(0)
    sys.exit()
  ans *= Fib().calc(a - pre - 1) % mod
  pre = a
ans *= Fib().calc(N - pre) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
import numpy as np

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

brk_stair = np.ones(N+1, dtype = int)
dp = np.zeros(N+1, dtype= int)

for _ in range(M):
    brk_stair[int(input())] = 0

#print(brk_stair)

dp[0] = 1
dp[1] = 1 * brk_stair[1]

for i in range(2, N + 1):
    dp[i] = (dp[i - 1] + dp[i-2]) * brk_stair[i]
    if(dp[i] > 1000000007):
        dp[i] = dp[i] % 1000000007

#print(dp)
print(dp[-1] % 1000000007)

Submission status: Accepted

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

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

for _ in range(M):
    brk_stair[int(input())] = 0

#print(brk_stair)

dp[0] = 1
dp[1] = 1 * brk_stair[1]

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

print(dp[-1] % 1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

fl = [True] * N

for i in range(M):
    fl[a[i]] = False

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

for i in range(1, N+1):
    if i > 0 and fl[i-1]:
        dp[i] += dp[i-1] % divisor
    if i > 1 and fl[i-2]:
        dp[i] += dp[i-2] % divisor
    
print(dp[N]%divisor)