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:
n,m=map(int,input().split())
a=[1]*n
for i in range(m):
        x=int(input())
        a[x-1]=0
mod=10**9+7
if a[0]==0:
        f=[1,1]
else:
        f=[1,2]
if n==1:
        print(f[0])
elif n==2:
        print(f[1])
else:
        for i in range(2,n):
                f.append((a[i-1]*f[i-1]+a[i-2]*f[i-2])%mod)
        print(f[-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = [int(input()) for i in range(m)]
B = [0 for i in range(10**5+10)]
for i in range(len(A)):
    B[A[i]] = 1

mod = 10**9 + 7

DP = [1,1]
if B[1] == 1:
    DP[1] = 0
for i in range(2,n+1):
    if B[i] == 0:
        DP.append((DP[i-1]+DP[i-2])%mod)
    else:
        DP.append(0)
    if i >= 3:
        DP[i-3]=0
print(DP[n])

Submission status: Accepted

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

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

pat=[0 for i in range(N+1)]
pat[0]=1
if a[1]==0: pat[1]=1

for i in range(2,N+1):
    if a[i]==0:
        if a[i-1]==0 and a[i-2]==0: pat[i]=pat[i-1]+pat[i-2]
        elif a[i-1]==0 and a[i-2]==-1: pat[i]=pat[i-1]
        elif a[i-1]==-1 and a[i-2]==0: pat[i]=pat[i-2]
        else:
            print(0)
            sys.exit()

    pat[i]%=MOD
print(pat[N])

Submission status: Accepted

Solution code:
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=1
def f(i):
        if i in A: return 0
        if i in dp: return dp[i]
        m1=0 if (i-1) in A else f(i-1)
        m2=0 if (i-2) in A else f(i-2)
        dp[i]=(m1+m2) % MOD
        return dp[i]

print(f(N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,M = LI()

st = set()
for i in range(M):
    st.add(int(input()))

pat1 = 1
pat2 = 0

for i in range(1, N):
    tmp = pat2
    pat2 = pat1
    pat1 = ((pat1 + tmp)%MOD) if not i in st else 0
    # print('pat1: {} pat2: {} i:{}'.format(pat1, pat2, i))
print((pat1+pat2)%MOD)

Submission status: Accepted

Solution code:
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    stairs = [0] * (N + 100)
    stairs[0] = 1
    for i in range(N):
        if i + 1 <= N and (i + 1) not in a:
            stairs[i + 1] += stairs[i]
        if i + 2 <= N and (i + 2) not in a:
            stairs[i + 2] += stairs[i]
    return stairs[N] % MOD

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

Submission status: Accepted

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

A = []
if len(A_pre)>0:
    A.append(A_pre[0])
    for i in range(1,M):
        if A[-1] != A_pre[i]:
            A.append(A_pre[i])
      

ans = [0] * (N+1)
ans[0] = 1
break_floor_count = 0
if break_floor_count < M and A[break_floor_count] == 1:
    break_floor_count += 1
else:
    ans[1] = 1

for i in range(2,N+1):
    if break_floor_count < M and A[break_floor_count] == i:
        break_floor_count += 1
    else:
        ans[i] = (ans[i-2]+ans[i-1])%mod_num 

print(ans[N])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, m = get_li()
    A = get_data(m, [int])
    MOD = 1000000007
    dp = [0] * (n + 2)
    dp[0] = 1
    dp[-1] = 0
    stepable = [True] * (n + 2)
    for a in A:
        stepable[a] = False
    for i in range(1, n + 1):
        if stepable[i]:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    print(dp[n])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N,M = map(int, input().strip().split(' '))
broken = set(int(line.strip()) for line in sys.stdin)
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  # 今i段目にいる
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

Submission status: Accepted

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

def solve():
    n, m = map(int, input().strip().split())
    am = set([int(input().strip()) for i in range(m)])
    ans = [0] * (n + 1000)
    ans[0] = 1
    md = (10 ** 9) + 7
    for i in range(n):
        if (i + 1) not in am:
            ans[i + 1] = (ans[i] + ans[i + 1]) % md
        if (i + 2) not in am:
            ans[i + 2] = (ans[i] + ans[i + 2]) % md
    print(ans[n])

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kaidan = [True] * (N+3)
for i in range(M):
    kaidan[int(input())] = False

dp = [0]*(N+3)
dp[0] = 1
for i in range(N):
    if kaidan[i+2]:
        dp[i+2] += dp[i]
        dp[i+2] %= 1000000007
    if kaidan[i+1]:
        dp[i+1] += dp[i]
        dp[i+1] %= 1000000007

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

n, m = list(map(int, input().split()))
aaa = set(map(int, sys.stdin))
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:
MOD = 1000000007

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

T = [0 for _ in range(N + 5)]

for a in A:
    T[a] = -1

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

print(T[N])

Submission status: Accepted

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

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

p[0]=1

for i in range(1,n+1):
  k = bisect.bisect_left(a,i)
  k2 = bisect.bisect_right(a,i)
  if k == k2:
    p[i] += p[i-1]
    if i >= 2:
      p[i] += p[i-2]
    p[i] = p[i]%mod
#print(p)
print(p[-1]%mod)

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
a = [I() for i in range(M)]

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

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

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

print(dp[N]%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] * (N + 2)
    dp[0] = 1
    a =set(a)

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


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]"
    result = solve(N, M, a)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n, m = [int(item) for item in input().split()]
a = set([-1]) 
dp = [0] * (n+10)
dp[0] = 1
for i in range(m):
    val = int(input())
    a.add(val)
for i in range(n):
    if i+1 in a and i+2 in a:
        print("0")
        exit()
    elif i+1 in a:
        dp[i+2] += dp[i]
    elif i+2 in a:
        dp[i+1] += dp[i]
    else:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
    dp[i+1] %= MOD
    dp[i+2] %= MOD
print(dp[n] % MOD)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(" ")))
A = {int(input()) for _ in range(M)}

memo = [0] * (N + 1)
memo[0] = 1
memo[1] = 0 if 1 in A else 1

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

    print(memo[N])

Submission status: Accepted

Solution code:
MOD = 1000000007

A = set()

# s = input()
# n = int(input())
# A = list(map(int, input().split()))
n, m = map(int, input().split())

for _ in range(m):
    a = int(input())
    A.add(a)

res = [0]*(n+1)

res[0] = 1
if 1 not in A:
    res[1] = 1

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

print(res[n])

Submission status: Accepted

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

for i in range(N):
  if a[i]==-1:
    continue
  if a[i+1]!=-1:
    a[i+1]+=a[i]
    a[i+1]%=MOD
  if i+2<=N and a[i+2]!=-1:
    a[i+2]+=a[i]
    a[i+2]%=MOD
print(max(0,a[N]))

Submission status: Accepted

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

bk = set()
for i in range(M):
    bk.update([int(input())])

DP = [0]*N
DP[0] = 1
if 1 not in bk:
    DP[1] = 1

for i in range(2, N):
    if i not in bk:
        DP[i] = DP[i-1] + DP[i-2]

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

Submission status: Accepted

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

dp = [0]*(N + 1)
dp[0] = 1
for step in range(N):
    if step in a:
        continue
    for width in [1, 2]:
        to = step + width
        if to <= N and not to in a:
            dp[to] = (dp[to] + dp[step]) % MOD

print(dp[N])

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

MOD = 1000000007

n,m = get_nums_l()
breaks = map(int, sys.stdin.readlines()) if m>0 else []

dp = [0] * (n+1)

for a in breaks:
    dp[a] = -1

dp[n] = 1

for i in range(n-1, -1, -1):
    if dp[i] == -1:
        continue
    
    x = 0
    if dp[i+1] != -1:
        x += dp[i+1]
    
    if i <= (n-2) and dp[i+2] != -1:
        x += dp[i+2]
    
    dp[i] = x % MOD

print(dp[0])

Submission status: Accepted

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

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

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

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

print(s[n])

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7

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

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

print(max(dp[n],0))

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
A = set()
for i in range(M):
    A.add(n())

dp = [0] * (N+1)
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]
    dp[i] %= 1000000007

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    A = []
    for _ in range(M):
        A.append(II())
    A.append(INF)
    dp = [0] * (N + 1)
    dp[0] = 1
    k = 0
    if A[0] == 1:
        dp[1] = 0
        k = 1
    else:
        dp[1] = dp[0]
    for i in range(2, N + 1):
        if i == A[k]:
            k += 1
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
    ans = dp[N]
    return ans

print(main())

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
arr  = set()
for _ in range(m):
    x = int(input())
    arr.add(x)


MOD = int(1e9) + 7

w = [0 for _ in range(n + 1)]
w[0] = 1
for i in range(1, n+1):
    if i in arr:
        continue

    if i - 1 >= 0 and i - 1 not in arr:
        w[i] += w[i-1]

    if i - 2 >= 0 and i - 2 not in arr:
        w[i] += w[i-2]
    
    w[i] %= MOD


# print(w)
print(w[n])

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += dp[i-2] + dp[i-1]
        dp[i] = int(dp[i] % mod)
print(dp[N])

Submission status: Accepted

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

mod = 10 ** 9 + 7

dp = [0] * (N + 100)
dp[0] = 1
not_use = [False] * (N + 100)
for a in a_list:
    not_use[a] = True

for i in range(N+1):
    not_u = not_use[i]
    if not_u:
        continue
    else:
        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:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0 for _ in range(n+10)]
dp[0] = 1
for x in a:
    dp[x] = -1
mod = 10**9 + 7
for i in range(n):
    if dp[i] < 0:
        continue
    if dp[i+1] >= 0:
        dp[i+1] += dp[i]
        dp[i+1] %= mod
    if dp[i+2] >= 0:
        dp[i+2] += dp[i]
        dp[i+2] %= mod
print(dp[n])

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, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
a = [INT() for _ in range(M)]
b = [0] * (N+2)  # こわれているところに１たてる
for i in a:
	b[i] = 1

dp = [0]*(N+2)
dp[0] = 1
if b[1] == 1:
	dp[1] = 0
else:
	dp[1] = 1

# print(dp)
for i in range(2, N+1):
	if b[i] == 1:  # こわれてる
		dp[i] = 0
	else:
		dp[i] = (dp[i-1] + dp[i-2])%MOD
# print(dp)
print(dp[N])

Submission status: Accepted

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

N, M = map(int, input().split())
hsh = {}
for i in range(M):
    hsh[int(input())] = True

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

for i in range(1,N+1):
    d = 0
    if i > 1 and i-2 not in hsh:  # 2段前が穴ではない
        if i-1 not in hsh:  # 1段前が穴ではない
            d += acc[i-1] + acc[i-2]
        else: 
            d += acc[i-2]
    else:  # 2段前が穴
        if i-1 not in hsh: # 1段前が穴ではない
            d += acc[i-1]
        else:
            d = 0
    acc[i] = d

# print(hsh)
# print(acc)
print(acc[-1]%1000000007)

Submission status: Accepted

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

MOD =  1000000007

def f(N, A):
    A.append(-1)

    a = A.pop(0)

    c0 = 0
    c1 = 1

    for i in range(1, N+1):
        c0, c1 = c1, (c0+c1)%MOD

        if i == a:
            c1 = 0
            a = A.pop(0)

    return c1
            


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

    print(f(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_array = [int(input()) for x in range(m)]
res = [1 for x in range(n + 1)]
res[1] = 1
for i in a_array:
    res[i] = -1

for i in range(2, n + 1):
    if res[i] == -1:
        continue
    if res[i - 1] != -1 and res[i - 2] != -1:
        res[i] = (res[i - 1] + res[i - 2])%1000000007
    elif res[i - 1] != -1 or res[i - 2] != -1:
        res[i] = max(res[i - 1], res[i - 2])%1000000007
    else:
        res[i] = 0
print(res[-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+5)
dp[0] = 1
for i in range(1,n+1):
        if i in a:
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    N, M = map(int, input().split())
    A = [0] * (N + 1)
    for i in range(M):
        bre = int(input())
        A[bre] = -1
    A[0] = 1
    A[1] = 1 if A[1] != -1 else -1
    # print(A)
    for i in range(N):
        if (A[i] == -1) & (A[i + 1] == -1):
            print(0)
            sys.exit()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007

dp = [0]*(n+2)
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:
N, M = list(map(int, input().split()))
V = 10 ** 9 + 7
a = [int(input()) for _ in range(M)]
A = set(a)
ANS = [0 for _ in range(100000 + 5)]

ANS[0] = 1
for i in range(N):
    #ANS[i] %= V
    if not i + 1 in A:
        ANS[i + 1] += ANS[i]
        #ANS[i + 1] %= V
    if not i + 2 in A:
        ANS[i + 2] += ANS[i]
        #ANS[i + 2] %= V
print(ANS[N] % V)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def main():
    N,M = ints_raw()
    As = [int_raw() for _ in range(M)]
    is_breake = [0]*(N+1)
    for a in As:
        is_breake[a]=1
    memo = [0]*(N+1)
    memo[0]=1
    memo[1]=1 if is_breake[1]==0 else 0
    for n in range(2,N+1):
        if is_breake[n]:
            memo[n] =0
            
        else:
            memo[n]=(memo[n-2]+memo[n-1])%DIV
    return memo[-1]

print(main())

Submission status: Accepted

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

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(1000000000)

#import numpy as np
#import scipy as sp

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5.  Import from math after it.
from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))

################################################################################

N, M = list(map(int, input().split()))
A = [None for i in range(M)]
for i in range(M):
    A[i] = int(input())
#A = list(map(int, stdin.read().split()))

BROKEN = [False for i in range(N)]
for a in A:
    BROKEN[a] = True

@lru_cache()
def dp(cur):
    if cur > N:
        return 0
    if cur == N:
        return 1
    if BROKEN[cur]:
        return 0
    return dp(cur + 1) + dp(cur + 2)

print(dp(0) % 1000000007)

Submission status: Accepted

Solution code:

def ispossible(a):
    d = [a[i] - a[i-1] for i in range(1, len(a))]
    return not 1 in d


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

    MOD = 10**9+7

    if not ispossible(a):
        print(0)
        return

    s = [1] * (N+1)

    a = set(a)

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

    for i in range(2, N+1):
        if i in a:
            continue

        s[i] = 0
        if i-1 not in a:
            s[i] += s[i-1] % MOD
        if i-2 not in a:
            s[i] += s[i-2] % MOD
        # print(s[:i+1])

    print(s[N] % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

tmp = [0 for _ in range(n + 1)]
tmp[0] = 1

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


print(tmp[-1] % 1000000007)

Submission status: Accepted

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

dp = [0] * (N+3)
dp[0] = 1
for i in range(M):
    dp[broken[i]] = -1 * float('inf')

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

print(dp[N] % mod)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
broken=[False]*(N+1)
for i in range(M):
    a=INT()
    broken[a]=True

dp=[0]*(N+1)
dp[0]=1
for i in range(N):
    if not broken[i+1]:
        dp[i+1]+=dp[i]
        dp[i+1]%=MOD
    if i!=N-1 and not broken[i+2]:
        dp[i+2]+=dp[i]
        dp[i+2]%=MOD
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


m = Mod(10**9 + 7)


def slv(N, M, A):
    dp = [0] * (N+3)
    b = [False] * (N+3)
    for a in A:
        b[a] = True

    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()