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, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n,m = MAP()
a = [INT() for _ in range(m)]
dp = [0 for _ in range(n+2)]
dp[0] = 0
dp[1] = 1
j = 0
for i in range(2, n+2):
    if j >= m or a[j] != i - 1:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
    else:
        dp[i] = 0
        j += 1
print(dp[n+1])

Submission status: Accepted

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


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

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

# 配る
for i in range(N):
    if i == a[-1]:
        a.pop()
        dp[i] = 0
        continue
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
    dp[i + 2] += dp[i]
    dp[i + 2] %= mod

ans = dp[N]
print(ans)

Submission status: Accepted

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

mod = 10**9+7

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M= map(int, input().split())
    mod = 7 + 10 ** 9
    A = [True] * (N + 1)
    for _ in range(M):
        A[int(input())] = False
    DP = [0] * (N + 1)
    DP[0] = 1
    for i in range(N):
        if i < N - 1:
            if A[i + 2]: 
                DP[i + 2] += DP[i]
                DP[i + 2] %= mod
        if A[i + 1]:
            DP[i + 1] += DP[i]
            DP[i + 1] %= mod

    print(DP[N])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    A = {int(input()) for i in range(M)}
    MOD = 10**9 + 7
    dp = [0]*(N+1)
    dp[0] = 1
    for i in range(N):
        if 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[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

N,M = list(map(int, input().rstrip().split()))
a_list = [int(input().strip()) for _ in range(M)]
#-----

step = [1,1] + ["x"]*(N-1)

for i in a_list:
    step[i] = 0

for i in range(2,N+1):
    if step[i] == "x":
        step[i] = ( step[i-1] + step[i-2] ) % (10**9 + 7)

print(step[N])

Submission status: Accepted

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

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        a, b = 1, 1
        for _ in range(n-2):
            a, b = b, a + b
        return b

ans = 1
for i in range(M+1):
    dansuu = (A[i+1]-1)-(A[i]+1)
    if dansuu == -1:
        ans *= 0
        break
    else:
        ans *= fibonacci(dansuu + 1)

print(ans%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# i段目に到達するまでの組み合わせをまとめた配列
possible_count = [0 for n in range(N + 1)]
for _ in range(M):
  i = int(input())
  possible_count[i] = -1

possible_count[0] = 1
for i in range(N):
  if possible_count[i] == -1:
    continue

  if i + 2 > N:
    possible_count[i+1] += possible_count[i] if possible_count[i+1] != -1 else 0
    continue

  possible_count[i+1] += possible_count[i] if possible_count[i+1] != -1 else 0
  possible_count[i+2] += possible_count[i] if possible_count[i+2] != -1 else 0

print(possible_count[len(possible_count) - 1] % 1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ngs = [int(input()) for _ in range(M)]
mae = -10**9
for ng in ngs:
    if abs(ng - mae) == 1:
        print(0)
        exit()
    mae = ng
fib = [1, 1]
for i in range(N):
    fib.append(fib[-1]+fib[-2])
ans = 1
now = 0
for ng in ngs:
    l = ng - now - 1
    ans *= fib[l]
    ans %= (10**9+7)
    now = ng + 1
if now == N-1:
    print(ans)
    exit()
# print(fib)
l = N - now
ans *= fib[l]
ans %= (10**9+7)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(' '))
dp = [0 for _ in range(N + 1)]
for _ in range(M):
    i = int(input())
    dp[i] = -float('inf')

mod = 10**9 + 7
dp[0] = 1
for i in range(N+1):
    if dp[i] ==  -float('inf'):
        continue

    if 0 <= i-1 < N and dp[i-1] != -float('inf'):
        dp[i] += dp[i-1]

    if 0 <= i-2 < N and dp[i-2] != -float('inf'):
        dp[i] += dp[i-2]

    dp[i] = dp[i] % mod

print(dp[N] )

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
stairs = [1 for i in range(N)]
for i in range(M):
  kari = int(input())
  stairs[kari-1] = 0
mod = 1000000007
if N <= 2:
  ans = sum(stairs)
else:
  if stairs[0]==1 and stairs[1]==1:
    stairs[1] = 2
  for i in range(2, N):
    stairs[i] = (stairs[i] * (stairs[i-1] + stairs[i-2])) % mod
  ans = stairs[N-1]
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N, M = [int(i) for i in input().strip().split()]
dirty_step_idxs = [0] * M
for i in range(M):
  dirty_step_idx = int(input())
  dirty_step_idxs[i] = dirty_step_idx

def fibonacci(n):
  # 0, 1, 1, 2, 3, 5, 8, ...
  a, b = 0, 1
  for i in range(n-1):
    a, b = b, a + b
  return a
  
if M == 0:
  res = fibonacci(N + 2)
else:
  res = 1
  now_step_idx = 0
  for i in range(M):
    n_step = dirty_step_idxs[i] - now_step_idx - 1
    if n_step == -1:
      res = 0
      break
    res *= fibonacci(n_step + 2)
    now_step_idx = dirty_step_idxs[i] + 1
  rest_steps = N - now_step_idx
  res *= fibonacci(rest_steps + 2) 
    
print(res % MOD)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
skip = [False] * (N+1)
for _ in range(M):
  skip[int(input())] = True

div = 1e9 + 7
path = 0
prev1 = 1
prev2 = 0

for n in range(1, N+1):
  if skip[n]:
    path = 0
  else:
    path = int((prev1 + prev2) % div)

  prev1, prev2 = path, prev1

print(path)

Submission status: Accepted

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


def main():
    N, M = map(int, 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

        if i == 1:
            dp[1] = dp[0]
            continue

        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

broken = [0 for _ in range(n+1)]
for i in a:
    broken[i] = 1
dp = [0 for _ in range(n+2)]
dp[n] = 1

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

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

Submission status: Accepted

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

# i段目が壊れているならa[i] = 1,そうでないならa[i] = 0
a = [0 for _ in range(n+1)]
for i in IN:
    a[i] = 1

# dp[i] := i段目から最上段にたどり着くまでの移動方法の数
# dp[i] = 0 (a[i] が 1)
# dp[i] = dp[i+1] + dp[i+2] (それ以外)
dp = [-1 for _ in range(n+1)]

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod = 10**9 + 7

pat = [1 for _ in range(N+1)]
for j in a :
    pat[j] = 0

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

print(pat[N])

Submission status: Accepted

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

print(dp[n])

Submission status: Accepted

Solution code:
from collections import deque
def main():
  N,M,*A=map(int, open(0).read().split())
  mod=10**9+7
  dp = [0] * (N+1)
  A=deque(A+[N+1])
  tmp=A.popleft()
  dp[:2] = [1, 1 if tmp!=1 else 0]
  if tmp==1:
    tmp=A.popleft()
  for i in range(2, N+1):
    if i==tmp:
      tmp=A.popleft()
      continue
    dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()

Submission status: Accepted

Solution code:
def main():
  N,M,*alst=map(int, open(0).read().split())
  mod=10**9+7
  if M==0:
    dp = [0] * (N+1)
    dp[:2] = [1, 1]
    for i in range(2, N+1):
      dp[i] = (dp[i-2] + dp[i-1])%mod
    print(dp[N])
    quit()
  tmp=0
  a0=alst[0]
  alst+=[N+1]
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if alst[tmp]!=1 else 0]
  if a0==1:
    tmp=1
  for i in range(2, N+1):
    if i!=alst[tmp]:
      dp[i] = (dp[i-2] + dp[i-1])%mod
    else:
      tmp+=1
  print(dp[N])
main()

Submission status: Accepted

Solution code:
def main():
  N,M,*alst=map(int, open(0).read().split())
  alst=set(alst)
  mod=10**9+7
  dp = [0] * (N+1)
  dp[:2] = [1, 1 if 1 not in alst else 0]
  for i in range(2, N+1):
    if i not in alst:
      dp[i] = (dp[i-2] + dp[i-1])%mod
  print(dp[N])
main()

Submission status: Accepted

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

mod = 10**9 + 7

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

print(ans[-1])

Submission status: Accepted

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

        if head < m and a[head] == i:
            ans[i] = 0
            head += 1
        else:
            if i == 1:
                ans[i] = 1
            else:
                
                ans[i] = (ans[i-1] + ans[i-2]) % MOD

    print(ans[n] % MOD)



if __name__ == '__main__':
    main()

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(N):
    if 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[-1]%MOD)

Submission status: Accepted

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

if 0 in A:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if 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[-1])

Submission status: Accepted

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

t=[True]*(n+1)

for i in range(m):
    a=int(input())
    t[a]=False

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

for i in range(0,n):
    for j in range(i+1,min(n,i+2)+1):
        if t[j]:
            dp[j]+=dp[i]
            dp[j] %=(1000000007)

#print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=set()
for i in range(m):
  a.add(int(input()))
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
if n==1:
  print(dp[1])
  exit()
if 2 in a:
  dp[2]=0
else:
  dp[2]=dp[1]+1
for i in range(3,n+1):
  if i in a:
    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())
a = set([int(input()) for _ in range(m)])
p = [0]*(n+1)
p[0] = 1
if 1 not in a:
  p[1] = 1

t = 1000000007

for i in range(2, n+1):
  if i in a:
    continue
  s = p[i-1] + p[i-2]
  s = s%t
  p[i] = s
  
print(p[n])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in a:
        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())
a = [False] * (N+1)
for i in range(M):
    a[int(input())] = True
 
memo = [None] * (N+1)
memo[0] = 1 #0番目にたどり着く方法は1通りと定義する。
memo[1] = 1 if not a[1] else 0
 
for i in range(2, N+1):
    memo[i] = memo[i-1] + memo[i-2] if not a[i] else 0
 
print(memo[N] % 1000000007)

Submission status: Accepted

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

broken = [False] * (n + 1)
for i in range(m):
    broken[int(input())] = True

mod = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if broken[1] else 1

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

print(dp[n])

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:



mod=10**9+7
n,m=list(map(int,input().split()))
a=[int(input()) for _ in range(m)]
fib=[1,1]
c=0
if m>0 and a[0]==1:
    fib[1]=0
    c+=1
for i in range(2,n+1):
    if c<m and a[c]==i:
        fib.append(0)
        c+=1
    else:
        fib.append((fib[i-2]+fib[i-1])%mod)

print(fib[n])

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  for i in range(2,n+1):
    if ans[i]>0:
      ans[i]=(ans[i-1]+ans[i-2])%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  mod=pow(10,9)+7
  ans=[1]*(n+1)
  for _ in [0]*m:
    ans[int(input())]=0
  for i in range(n+1):
    ans[i]=ans[i] if ans[i]==0 or i<2 else (ans[i-1]+ans[i-2])%mod
  print(ans[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if step[i] == -1:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#虚無疲れAC
mod=10**9+7
n,m=map(int,input().split())
broken={i:False for i in range(n+1)}
for i in range(m):
    a=int(input())
    broken[a]=True
way_to_go=[0 for i in range(n+1)]
way_to_go[0]=1
if broken[1]==True:
    way_to_go[1]=0
else:
    way_to_go[1]=1
for j in range(2,n+1):
    if broken[j]==False:
        if broken[j-1]==False:
            way_to_go[j]+=way_to_go[j-1]
        if broken[j-2]==False:
            way_to_go[j]+=way_to_go[j-2]
        way_to_go[j]%=mod
print(way_to_go[n])

Submission status: Accepted

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

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

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

ans = int(dp[N-1])%1000000007
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])

Submission status: Accepted

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

Submission status: Accepted

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

a.append(N+10)
dp=[0]*(N)
j=0

for i in range(1,N+1):
    if i==1 and 1!=a[j]:
        dp[0]=1
    elif i==2:
        if 2==a[j]:
            dp[1]=0
            j+=1
        else:
            dp[1]=dp[0]+1

    elif i!=a[j]:
        dp[i-1]=dp[i-2]+dp[i-3]
    else:
        j+=1
    

print(dp[N-1]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

lst = []
for i in range(m):
    lst.append(int(input()))
lst.sort()

#フィボナッチ数列
dp = [-1 for i in range(n+2)]
dp[0] = 1
dp[1] = 1
for i in lst:
    dp[i] = 0
for i in range(2,n+2):
    if dp[i]<0:
        dp[i] = dp[i-1] + dp[i-2]

# print(lst)
# print(lst2)
# print(dp)
print(dp[n]%mod)

Submission status: Accepted

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

#フィボナッチ数列
dp = [0 for i in range(n+2)]
dp[0] = 1
dp[1] = 1
for i in range(2,n+2):
    dp[i] = dp[i-1] + dp[i-2]

#穴が無い場合
if m==0:
    print(dp[n]%mod)
    exit()

lst = []
for i in range(m):
    lst.append(int(input()))
lst.sort()

#2連続穴がある場合
for i in range(len(lst)-1):
    if lst[i]+1 == lst[i+1]:
        print(0)
        exit()

lst2 = []
for i in range(len(lst)):
    if i==0:
        lst2.append(lst[0]-1)
    else:
        lst2.append(lst[i]-lst[i-1]-2)
lst2.append(n-lst[-1]-1)

ans = 1
for i in lst2:
    ans *= dp[i]
    ans %= mod

# print(lst)
# print(lst2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD=1000000007
N,M=map(int,input().split())
a=[]
dp=[0]*100010
for i in range(M):
    tmp=int(input())
    a.append(tmp)
    dp[tmp]=-1
dp[0]=1
for i in range(1,N+1):
    if(dp[i]==-1):
        continue
    if(dp[i-1]!=-1):
        dp[i]=(dp[i]+dp[i-1])%MOD
    if(i>1):
        if(dp[i-2]!=-1):
            dp[i]=(dp[i]+dp[i-2])%MOD
print(dp[N])

Submission status: Accepted

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


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


dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(1, 3):
        if (i+j) > N or a[i+j] == False:
            continue
        dp[i+j] += dp[i]
        dp[i+j] %= mod

print(dp[N])

Submission status: Accepted

Solution code:
MOD = 10**9+7
n,m = map(int,input().split())

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

cur = 0
ans = 1
for i in range(m):
    a = int(input())
    if a==cur:
        print(0)
        break
    ans *= f[a-cur-1]
    ans %= MOD
    cur = a+1
else:
    ans *= f[n-cur]
    ans %= MOD
    print(ans)

Submission status: Accepted

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

inf = 10**9+7

dp = [0]*diff
dp[0] = 0
dp[1] = 1
for i in range(2,diff):
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] = dp[i]%inf

cnt = 1
for i in range(1,M+2):
    da = a[i]-a[i-1]-1
    if da == 0:
        cnt = 0
        break
    else:
        cnt *= dp[da]
        cnt = cnt%inf

print(cnt%inf)

Submission status: Accepted

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

def main():
  MAX = 10**9+7
  
  n, m = map(int, input().strip().split())
  As = set([int(input()) for _ in range(m)])
  
  dp = [0] * (n + 1)
  dp[0] = 1
  dp[1] = 1 if 1 not in As else 0
  for i in sorted(list(set(range(2, n+1)) - As)):
    dp[i] = (dp[i-1] + dp[i-2]) % MAX
  print(dp[-1] % MAX)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():

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

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

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

    if A[N-1]:
        dp[N] += dp[N - 1]

    print(dp[N] % 1000000007)


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(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])%p
print(DP[N])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
#0からn段の階段を作成
j = [True for i in range(n+1)]
#0,1段は1通り
ans = [1,1]+[0 for i in range(n-1)]
p = 10**9+7
#どこが壊れているかcheck
for i in range(m):
    j[int(input())] = False
    
#もし1段目が壊れていたら101となる
if j[1] == False:
    ans[1] = 0
    ans[2] = ans[0]
#二段目から調べる
for i in range(2,n+1):
    #壊れていない場合
    if j[i] == True:
        ans[i] = ans[i-1] + ans[i-2]
        ans[i] %= p
    #壊れている場合
    else:
        ans[i] = 0
        
print(ans[n]%p)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
j=[True for _ in range(n+1)]
ans=[1,1]+[0 for _ in range(n-1)]
p=10**9+7
for _ in range(m):
    j[int(input())]=False
if j[1]==False:
    ans[1]=0
    ans[2]=ans[0]
for i in range(n-1):
    if j[i+2]==True:
        ans[i+2]=ans[i+1]+ans[i]
        ans[i+2]%=p
    else:
        ans[i+2]=0
print(ans[n]%p)

Submission status: Accepted

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

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

ok = [True]*(N+1)
for i in a:
  ok[i] = False

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= mod
      
print(dp[N])

Submission status: Accepted

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

mod = 10 ** 9 + 7
ok = [True] * (n + 1)
for i in a:
    ok[i] = False

dp = [0 for i in range(n+1)]
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n+1, i+3)):
        if ok[j]:
            dp[j] += dp[i]
            dp[j] %= mod

print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
#A = [int(input()) for i in range(M)]
flag = [0]*N
for i in range(M):
    flag[int(input())-1] = 1
#A = [i*3 for i in range(N//3)]
#for i in range(N//3):
    #flag[i] = 1

mod = 10**9+7

dp = [0] * N

if flag[0]==0:
#if 1 not in A:
    dp[0] = 1
    if N>1:
        if flag[1]==0:
    #if (2 not in A) and N > 1:
            dp[1] = 2
elif N > 1:
    if flag[1]==0:
    #if 2 not in A:
        dp[1] = 1
    else:
        dp[1] = 0

loop = []
'''
for i in range(2, N):
    if i not in A:
        loop.append(i)
'''
for i in range(2, N):
    if flag[i]==0:
        dp[i] = (dp[i-2] + dp[i-1]) % mod
        #dp[i] = (sum(dp[i-2:i])) % mod

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

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)
dp[0] = 1
dp[1] = 1

for i in a:
    dp[i] = 0

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
CONST = 10**9 + 7
n,m = map(int,input().split())

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
dp=[-1]*(n+1)
for i in a:
    dp[i]=0
dp[0]=1 
for i in range(1,n+1):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]*(i>1)
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[0] = 1
broken = [0]*(n+1)
for i in range(m):
    broken[int(input())] = 1
    
for i in range(1, n+1):
    if broken[i] == 1:
        continue
    else:
        if i != 1:
            dp[i] = dp[i-1] + dp[i-2]
        elif i == 1:
            dp[i] = dp[i-1]

print(dp[-1]%MOD)

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(50000000) #追加
N,M=map(int,input().split())
a=[]
for i in range(0,M):
    a.append(int(input()))
a=set(a)
if M==0:
    a=[-1]
ans=1
s=[-1]*(N+1)
s[0]=1
def dp(n):
    if n==0:
        return 1
    elif n==1:
        return 0 if 1 in a else 1
    if s[n-1]!=-1:
        c=s[n-1]
    elif n-1 in a:
        s[n-1]=0
        c=0
    else:
        c=dp(n-1)%1000000007
        s[n-1]=c
    if s[n-2]!=-1:
        b=s[n-2]
    elif n-2 in a:
        s[n-2]=0
        b=0
    else:
        b=dp(n-2)%1000000007
        s[n-2]=b
    return (c+b)%1000000007
print(dp(N)%1000000007)

Submission status: Accepted

Solution code:
const = 1000000007
n, m = [int(_) for _ in input().split()]
dp = [0]* (n+2)

for _ in range(m):
    dp[int(input())] = -1

dp[0] = 1
dp[n+1] = -1

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

print(dp[n]%const)

Submission status: Accepted

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

Submission status: Accepted

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