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
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(int)
    for i in range(m):
        d[int(readline())]
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if i not in d:
            if i == 1:
                dp[i] += dp[i-1]
            else:
                dp[i] += dp[i-1]
                dp[i] += dp[i-2]
            dp[i] %= mod
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

i = -3
for _ in range(n - 1):
    if S[i] != 0:
        S[i] = S[i + 1] + S[i + 2]
    i -= 1

ans = S[0] % (10**9 + 7)
print(ans)

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
mod = 1000000007
result = [0 for i in range(N+1)]
for j in range(M):
    a = int(input())
    result[a] = -1
result[0] = 1
result[1] = 1 if result[1] != -1 else 0
for i in range(2,N+1):
    if result[i] != -1:
        before1 = result[i-1] if result[i-1] != -1 else 0
        before2 = result[i-2] if result[i-2] != -1 else 0
        result[i] = (before1 + before2) % mod
print(result[-1])

Submission status: Accepted

Solution code:
from collections import deque

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

comb_stairs = [1]
D = deque(A)

for i in range(1, N + 1):
    if i == 1:
        if len(D) == 0:
            comb_stairs.append(1)
        elif D[0] == 1:
            comb_stairs.append(0)
            D.popleft()
        else:
            comb_stairs.append(1)
    else:
        if len(D) == 0:
            comb_stairs.append(comb_stairs[i - 1] + comb_stairs[i - 2])
        elif D[0] == i:
            comb_stairs.append(0)
            D.popleft()
        else:
            comb_stairs.append(comb_stairs[i - 1] + comb_stairs[i - 2])

print(comb_stairs[-1] % 1000000007)

Submission status: Accepted

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]+ a+ [N+1]
fib = [0,1]
for i in range(10**5):
    fib.append((fib[-1]+fib[-2])%1000000007)
ans = 1
for i in range(len(b)-1):
    ans= (ans*fib[b[i+1]-b[i]-1])%1000000007
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
# dp = [0]*(n+1)
dp = [None]*(10**5+1)
mod = 10**9+7
dp[0] = 0

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
x = [1] + [0] * N
broken = [False] * (N+1)
mod = 10**9 + 7

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

if not broken[1]:
  x[1] = 1

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

print(x[N])

Submission status: Accepted

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

for i in range(1, n+1):
    if i in stairs: 
        dp[i] = 0
        continue

    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[n])

Submission status: Accepted

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

    out = [1]*(N+1)
    for _ in range(M):
        out[int(input())] = 0
        
    for i in range(2, N+1):
        if out[i] == 1:
            out[i] = (out[i-1] + out[i-2])
    return out[-1]%1000000007
    
if __name__ == '__main__':
    print(main())

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=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+2)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

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

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])

Submission status: Accepted

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

for i in range(M):
    is_broken[items[i]] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
#from scipy.misc import comb

MOD = 10**9+7

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

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

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

print(ans[N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
dp = [0]*(N+1)
li_A = [0]*(N+1)
for i in range(M):
    li_A[int(input())] = 1

dp[0] = 1
dp[1] = 1
if li_A[1] == 1:
    dp[1] = 0

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

Submission status: Accepted

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

for i in a:
    b[i]=-1

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

Submission status: Accepted

Solution code:
# 2019/12/26

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

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

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
for i in a:
    dp[i]=-1
for i in range(2,N+1):
    if dp[i]==-1:
        continue
    if dp[i-1]!=-1:
        dp[i] = (dp[i]+dp[i-1])%MOD
    if dp[i-2]!=-1:
        dp[i] = (dp[i]+dp[i-2])%MOD

print(dp[N])

Submission status: Accepted

Solution code:
def calculate(n, arr2):
    steps = [0]*(n)
    steps[0] = 1

    if arr2.get(0) == True:
        steps[0] = 0
    else:
        steps[0] = 1

    if n == 1:
        return steps

    if arr2.get(1) == True:
        steps[1] = 0
    else:
        steps[1] = 1 + steps[0]

    if n == 2:
        return steps

    for index in range(2,n):
        if arr2.get(index) == True:
            steps[index] = 0
        else:
            steps[index] = steps[index-1] + steps[index-2]

    return steps

S = input().split(" ")
N = int(S[0])
M = int(S[1])


arr2 = {}
for i in range(M):
    index = int(input())
    arr2.setdefault(index-1, True)

result = calculate(N, arr2)

print(result[N-1] % 1000000007)

Submission status: Accepted

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

A.insert(0,0)

is_safe=[True]*(N+1)#0段目も含めて、0～N段目、合計N+1段分

for a in A:
    is_safe[a]=False#0段目スタートなので、a段目が壊れていることになる

dp=[0]*(N+1)#0段目から、N段目までの組み合わせを各段ごとに挿入するリスト
dp[0]=1
if 1 not in A:
    dp[1]=1

#最初0段目に立っている前提で開始、len(dp)=len(is_safe)=N+1
for i in range(2,N+1):#indexとしては、Nまで調べたいのでN+1を入れておく
    if is_safe[i]:
        dp[i]=dp[i-1]+dp[i-2]
    else:
        dp[i]=0
print(dp[N]%MOD)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
a = set([int(input()) for i in range(M)])
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2,N+1):
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
mod = 1000000007
broken = [0 for i in range(n+1)]
for j in range(m):
    a = int(input())
    broken[a] = -1
broken[0] = 1
broken[1] = 1 if broken[1] != -1 else 0
for i in range(2,n+1):
    if broken[i] == -1:
        continue
    one = broken[i-1] if broken[i-1] != -1 else 0
    two = broken[i-2] if broken[i-2] != -1 else 0
    broken[i] = (one + two) % mod
print(broken[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP


from copy import deepcopy


def full(shape, full_value):
    if isinstance(shape, tuple):
        if len(shape) == 2:
            return [[full_value] * shape[1] for _ in range(shape[0])]
        else:
            import numpy as np
            return np.full(shape, full_value).tolist()
    else:
        return [full_value] * shape


MOD = 10**9 + 7
# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = full((N + 1), False)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = full((N + 1), -1)
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP


def full(shape, full_value):
    if isinstance(shape, tuple):
        NotImplementedError()
    else:
        return [full_value] * shape


MOD = 10**9 + 7
# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = full((N + 1), False)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = full((N + 1), -1)
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP

MOD = 10**9 + 7
import numpy as np
# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False).tolist()
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = np.full((N + 1), -1).tolist()
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP

MOD = 10**9 + 7
import numpy as np
# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False, dtype=bool)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = np.full((N + 1), -1, dtype='int64')
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[i - 2] + dp[i - 1]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP

MOD = 10**9 + 7
import numpy as np
# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = np.full((N + 1), False, dtype=bool)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = np.full((N + 1), -1, dtype='int64')
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = 0 if to_zero[i] else dp[(i - 2):i].sum()
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# 典型的なDP

MOD = 10**9 + 7

# dp[i]をi段目までの通りの数とする。
N, M = list(map(int, input().split()))
to_zero = [False] * (N + 1)
for _ in range(M):
    to_zero[int(input())] = True  # 床が抜けているところ

# dpテーブルの用意
dp = [-1] * (N + 1)
dp[0] = 1
dp[1] = 0 if to_zero[1] else 1
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
    if to_zero[i]:
        dp[i] = 0

    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Submission status: Accepted

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

arr = [int(input()) for i in range(0, m)]
dp = [0] * (n + 1)
dp[0] = 1

def solve():

  ok = [True] * (n+1)
  for i in range(0, m):
    ok[arr[i]] = False

  for step in range(1, n+1):
    if ok[step] == False:
      dp[step] = 0
    else:
      if step == 1:
        dp[step] = 1
      else:
        dp[step] = dp[step-1] + dp[step-2]

  print(dp[n] % mod)

def main():
  solve()

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# Typical Stairs
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    n, m, *a = map(int, read().split())
    MOD = 10**9 + 7

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

    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    is_broken = [False] * (n+1)
    for i in a:
        is_broken[i] = True
    if 1 in a:
        dp[1] = 0
    else:
        dp[1] = 1

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

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq


# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def reduce(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# # from itertools import accumulate
# # from collections import deque

# from operator import mul
# from functools import reduce

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# import random

def crange(m,n):
    return range(m,n+1)

def main():
    n,m = map(int, input().strip().split())
    a = [0 for _ in range(m)]
    for i in range(m):
       a[i]  = int(input().strip())
    a = set(a)
    #eprint("a ",end=": ")
    #eprint(a)
    l=[0 for _ in crange(0,n)]
    l[0]=1
    l[1]=0 if 1 in a else 1
    for i in crange(2,n):
        l[i] = 0 if i in a else l[i-2] + l[i-1]
        #eprint("l[",i,"] ",end=": ")
        #eprint(l[i])
    print(l[n]%(10**9 + 7))


    return

if __name__ == '__main__':
    main()


'''
find a_cnt such that
for given
n (1<=n<=10**5),
m (0<=m<=n-1),
when m>=1 then 列[a_i] ( 1<=i<=m<=n-1,1<= a[i]<=n-1),

let T := { (i,j) in [0...n]**2 | i + 2*j == n and } # i,j はそれぞれ「1段登る」「2段登る」コマンドﾞを使った回数

let 列 B :=[b[i] \in {1,2}] and sum(B)==n and \forall i in [0...].sum(B[0:i]) \notin





n=|T|


'''

Submission status: Accepted

Solution code:
def examC():
    N, M = LI()
    A = [I() for _ in range(M)]
    A.append(N+1)
    fib = [1]*(N+2)
    for i in range(1,N):
        fib[i+2] = fib[i+1] + fib[i]
    fib[0] = 0
#    print(fib)
    ans = fib[A[0]]%mod
    for i in range(M):
        ans *= fib[A[i+1]-A[i]-1]
        ans %=mod
    print(ans)
    return

def examD():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = int(1e+9 + 7)
A = [-1] + [int(input()) for i in range(M)] + [N+1]
B = []
for i in range(M+1):
  B.append(A[i+1] - A[i] - 1)
C = [0, 1]
for i in range(max(B)):
  C.append(C[i] + C[i+1])
com = 1
for i in range(len(B)):
  com *= C[B[i]] % mod
  com %= mod
print(com)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[-1 for i in range(n+1)] #dp[i]=はi段目
for i in range(m):
	a=int(input())
	dp[a]=0
dp[0]=1
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]%1000000007)

Submission status: Accepted

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

if n == 1:
    print(1)
else:
    for i in range(m):
        a = int(input())
        ans[a-1] = 0

    if ans[0] != 0 and ans[1] != 0:
        ans[0] = 1
        ans[1] = 2

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

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if _next not in A:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.ones(N + 2, dtype='bool')
for _ in range(M):
    A[int(input())] = False
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if A[_next]:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for j in range(M):
    b[a[j]]=-1

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

Submission status: Accepted

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

dp = [0] * 100100
dp[0] = 1
dp[1] = 0 if 1 in A else 1
for i in range(N):
    if i+2 in A:
        continue
    dp[i+2] = dp[i] + dp[i+1]

print(dp[N] % 1000000007)

Submission status: Accepted

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

dp = [0] * 101000
dp[0] = 1
dp[1] = 0 if 1 in A else 1

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

print(dp[N])

Submission status: Accepted

Solution code:
import sys

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

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

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

print(dp[N]%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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

dp = [0] * (N+1)
#どうやってもスタート地点から始まるから、0に行く方法は1通りのみ
dp[0] = 1

#1が壊れていなければ1に行く方法は0->1の1通りのみ
if 1 not in a:
    dp[1] = 1
    not_broken_stairs = set(range(2, N+1)) - set(a)
else:
    not_broken_stairs = set(range(1, N+1)) - set(a)    

#i=2or3から始まる。
#１が壊れていなければ2に行く方法は(0->2の1通り)+(1->2の1通り)で2通り。
for i in not_broken_stairs:
    dp[i] = dp[i-2] + dp[i-1]
    
print(dp[-1] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
a_ls = set()
MOD = 10**9+7
for i in range(m):
    a = int(sys.stdin.readline())
    a_ls.add(a)

memo_ls = [0 for i in range(n+1)]
memo_ls[0] = 1
for i in range(1, n+1):
    if i in a_ls:
        memo_ls[i] = 0
    else:
        memo_ls[i] = memo_ls[i-1] + memo_ls[i-2]
    memo_ls[i] %= MOD
print(memo_ls[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def solve():
	mod = 10 ** 9 + 7
	#input
	N, M, *a = map(int, open(0).read().split())

	dp = [0] * (N + 2)
	dp[0] = 0 # i = -1 don't exist 
	dp[1] = 1
	
	#not destroyed
	ok = sorted(set(range(1, N + 1)) - set(a))

	for i in ok:
		dp[i + 1] += (dp[i] + dp[i - 1]) % mod
	print(dp[-1])
solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
f = defaultdict(int)
for i in range(m):
    a = I()
    f[a] = 1

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

Submission status: Accepted

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

dp[0]=1 #0が１なのは２段目の回答を合わせるためdp[０]＝０、dp[1]=0,ds[2]=1
#は入力が1,0のきエラーになるので、だめ
dp[1]=1
for i in range(m):
    dp[t[i]]=0#ここはそもそもいけないので０になる


for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=dp[i-1]+dp[i-2]#このばしょにくるほうほうは二個前からくるか一個前からくるか、そこのあたいをたっせばいい
print(dp[-1]%mod)

Submission status: Accepted

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

dp[0]=1
dp[1]=1
for i in range(m):
    dp[t[i]]=0


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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [int(input()) for _ in[0]*m]
l=set(l)
dp=[0]*(n+1)#0〜n段目までのn+1通り。
#1段目までは手動。
dp[0]=1
dp[1]=0 if 1 in l else 1
MOD =10**9+7
#dp 貰うタイプ
for i in range(2,n+1):
  if i not in l:#床が壊れてなければ
    dp[i] = (dp[i-1] + dp[i-2])%MOD
print(dp[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
a=set(a)
dp=[0]*(n+2)
dp[0]=1
div=1000000007
for i in range(n):
  dp[i]%=div
  if i+1 in a:
    dp[i+1]=0
  else:
    dp[i+1]+=dp[i]
  if i+2 in a:
    dp[i+2]=0
  else:
    dp[i+2]+=dp[i]
print(dp[n]%div)

Submission status: Accepted

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

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    #dp[i] = i段目までの移動総数
    dp = [-1]*(N+1)
    dp[0]=1
    dp[1]=1 
    for i in range(M):
        dp[a[i]] = 0
    
    for i in range(2,N+1):
        if dp[i] == 0:
            continue
        dp[i] = dp[i-1]+dp[i-2]
        dp[i]%=MOD
    print(dp[N]%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [0] * (n + 10)
dp[0] = 1
mod = 10**9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

if ok[1]:
    dp[1] = 1

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

Submission status: Accepted

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

dp = [0] * (n + 10)
dp[0] = 1
mod = 10**9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

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

Submission status: Accepted

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

dp = [0] * (n + 10)
dp[0] = 1
mod = 1e9 + 7

ok = [1] * (n + 10)
for i in a:
    ok[i] = 0

for i in range(n):
    if ok[i + 1]:
        dp[i + 1] += dp[i]
        dp[i + 1] %= mod
    if ok[i + 2]:
        dp[i + 2] += dp[i]
        dp[i + 2] %= mod
print(int(dp[n]))

Submission status: Accepted

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

cnt2 = 0
cnt1 = 1
aa.append(-1)
a = aa.pop(0)


for i in range(1,n):
    if i == a:
        cnt2, cnt1 = cnt1, 0
        a = aa.pop(0)
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
mod=10**9+7
flag=1
S=[0 for i in range(n+3)]
S[0]=1
SET=set(A)
for i in range(n):
    if i in SET:
        S[i]=0
        if i+1 in SET:
            flag=0
    S[i+1]+=S[i]
    S[i+2]+=S[i]
    
print(S[n]%mod if flag==1 else 0)
#配る方で解いてみた。

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = (10**9)+7
dp = [0] * (n + 1)
dp[n] = 1
for i in reversed(range(n)):
    if(breaks[i] == 1):
        dp[i] = 0
        continue
    if(i == n - 1):
        dp[i] = dp[i+1]
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0] % mod)

Submission status: Accepted

Solution code:
mod = 1000000007

N, M = map(int, input().split())
broken = [0] * (N+1)
s = [0 for _ in range(N+1)]
for _ in range(M):
    a = int(input())
    broken[a] = 1
s[0] = 1
for i in range(1, N+1):
    if broken[i]:
        s[i] = 0
    else:
        s[i] = (s[i-1] + s[i-2]) % mod
        s[i] %= mod
print(s[N] % mod)
'''
s[0] = 0
s[1] = 1
s[2] = 2

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

for i in range(3, N+1):
    if cur_ix < len(a) and a[cur_ix] == i:
        s[i] = 0
        cur_ix += 1
    else:
        s[i] = (s[i-1] + s[i-2]) % 1000000007
'''

Submission status: Accepted

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

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

dp = [0] * (n + 1)
dp[0] = 1
b = a[0]
j = 1
for i in range(1, n + 1):
    if i == b:
        b = a[j]
        j += 1
    else:
        tmp = dp[i - 2] + dp[i - 1]
        if tmp >= mod:
            tmp -= mod
        dp[i] = tmp
print(int(dp[-1]))

Submission status: Accepted

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

dp = [0] * (n + 1)
dp[0] = 1
b = a[0]
j = 1
for i in range(1, n + 1):
    if i == b:
        b = a[j]
        j += 1
    else:
        tmp = dp[i - 2] + dp[i - 1]
        if tmp >= mod:
            tmp -= mod
        dp[i] = tmp
print(int(dp[-1]))