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:
def rec(i):
    global ans
    ans[N] = 1
    for i in range(N-1,-1,-1):
        if a[i+1] and a[i+2]:
            ans[i] = (ans[i+1] + ans[i+2])
        elif a[i+1]:
            ans[i] = ans[i+1]
        else:
            ans[i] = ans[i+2]
    return ans[0]

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

hantei = False
a = [True] * (N+1) + [False]
for i in range(0,M-1):
    if A[i+1] - A[i] == 1:
        hantei = True
        break

ans = [1] * (N+1)
if not hantei:
    for i in range(M):
        a[A[i]] = False
    Answer = rec(0)

if hantei:
    print(0)
else:
    print(Answer%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(150000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))

Submission status: Accepted

Solution code:
import bisect
M = 1000000007

# def dfs(i):
#     if i >= n - 1:
#         return 1
#     if dp[i] is not None:
#         return dp[i]
#     if i <= maxv and a[bisect.bisect_left(a, i)] == i:
#         dp[i] = 0
#         return 0
#     r = (dfs(i + 1) + dfs(i + 2)) % M
#     dp[i] = r
#     return r

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.sort()
maxv = m and max(a) or -1
# dp = [None] * n
# print(dfs(0) % M)

dp = [1] * (n + 2)
dp[-1] = 0
for i in range(n - 1, -1, -1):
    if i <= maxv and a[bisect.bisect_left(a, i)] == i:
        dp[i] = 0
    else:
        dp[i] = (dp[i + 1] + dp[i + 2]) % M

print(dp[0] % M)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [1]*(n+1)
#kubaru_dp = [1]*n

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

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [1]*(n+1)
#kubaru_dp = [1]*n

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
flag=0
c=[0 for i in range(n+1)]
b=0
a.append(-2)
c[0]=1
if(a[b]==1):
    c[1]=0
    b+=1
else:
    c[1]=1
for i in range(2,n+1):
    if (i==a[b]):
        c[i]=0
        b+=1
    else:
        c[i]=c[i-1]+c[i-2]
        c[i]=c[i] %1000000007
print('{0}'.format(c[n]))

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
d = [True] * (a+1)
for i in range(b):
    d[int(input())] = False
e = [0] * (a+1)
for i in range(0, a+1):
    if i < 2:
        if d[i]:
            e[i] = 1
        else:
            e[i] = 0
    elif not d[i] and not d[i-1]:
        print(0)
        exit()
    elif d[i]:
        e[i] = (e[i-2] + e[i-1]) % 1000000007
print(e[len(e)-1])

Submission status: Accepted

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

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

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


print(dp[N] % 1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
a = defaultdict(lambda: True)
for i in range(M):
    a[int(input())] = False

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

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = set(a)
li = [1] + [0 for _ in range(N)]

for i in range(1, N + 1):
    if i in b:
        #rint("pass!{}".format(i))
        continue
    else:
        li[i] = li[i - 1] + li[i - 2]

print(li[-1] % 1000000007)

Submission status: Accepted

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

def main():
	n, m = map(int, input().strip().split())
	v = [0] * (n+1)
	v[0] = 1
	v[1] = 1
	N = []
	for i in range(m):
		a = int(input().strip())
		N.append(a)
	N.append(-1)
	j = 0
	for i in range(1, n+1):
		if N[j] == i:
			v[i] = 0
			j += 1
		else:
			if i == 1:
				v[i] = 1
			else:
				v[i] = v[i-1] + v[i-2]
	print(v[n] % (10**9+7))

if __name__ == '__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

def steps(n):
    if memo[n] != -1:
        return memo[n]
    
    one = memo[n-1] if memo[n-1] != -1 else steps(n-1)    
    two = memo[n-2] if memo[n-2] != -1 else steps(n-2)

    memo[n] = one + two
    return memo[n]

n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
memo = [-1 for i in range(n+1)]
memo[0] = 1
memo[1] = 1
for b in broken:
    memo[b] = 0

print(steps(n) % (10**9+7))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

def input():
    return sys.stdin.readline().strip()

N, M = map(int, input().split())
a = set(int(input()) for _ in range(M))
li = [1] + [0 for _ in range(N)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

if M == 0:
    A = []
else:
    A = [0]*M
    for i in range(M):
        A[i] = int(input())

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
#DP[2] = 2

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

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )

Submission status: Accepted

Solution code:
# !/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr) if not __debug__ else None
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE

if __name__ == '__main__':

    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]"

    # write code
    issafe = [True for i in range(N + 10)]
    for i in a:
        issafe[i] = False
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if issafe[1]:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if issafe[n - 1]:
            dp[n] += dp[n - 1]
            debug(n, "!")
        if issafe[n - 2]:
            dp[n] += dp[n - 2]
            debug(n, "?")
    print(dp[N])

Submission status: Accepted

Solution code:
# !/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr)
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE

if __name__ == '__main__':

    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]"

    # write code
    issafe = [True for i in range(N + 10)]
    for i in a:
        issafe[i] = False
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if issafe[1]:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if issafe[n - 1]:
            dp[n] += dp[n - 1]
            debug(n, "!")
        if issafe[n - 2]:
            dp[n] += dp[n - 2]
            debug(n, "?")
    print(dp[N])

Submission status: Accepted

Solution code:
# !/usr/bin/env python3
import sys
from operator import itemgetter
# gcd
# from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# 提出時はコメントアウト+上のshebangを有効にする
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args): return print(*args, file=sys.stderr)
# template

MOD = 1000000007  # type: int

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

class Modint():
    '''
    自動でMODで割った余りを計算してくれる整数。MODは素数である必要があり，デフォルトは10**9+7。

    Parameters
    ----------
        n (int) : Modintの初期値
        MOD=10^9+7 (int) : 余りを計算するMOD。素数である必要がある。

    Methods
    ----------
        inverse(n: int) -> Modint
            n の逆元を返す。
    '''

    def __init__(self, n: int, mod=MOD):
        if n >= 0:
            self.n = n % mod
        else:
            self.n = (mod - (-n) % mod) % mod
        self.mod = mod

    def __eq__(self, other):
        return self.n == int(other)

    def __ne__(self, other):
        return not self == other

    def __neg__(self):
        return self.__class__(-self.n)

    def __str__(self):
        return str(self.n)

    def __int__(self):
        return self.n

    def __iadd__(self, other):
        self.n += int(other)
        self.n %= self.mod
        return self

    def __radd__(self, other):
        return self.__add__(other)

    def __isub__(self, other):
        self.n -= int(other)
        self.n %= self.mod
        return self

    def __rsub__(self, other):
        return self.__sub__(other)

    def __imul__(self, other):
        self.n = self.n * int(other) % self.mod
        return self

    def __rmul__(self, other):
        return self.__mul__(other)

    def inverse(self):
        '''
        フェルマーの小定理を考えると，MOD-2乗することでMODでの逆元を求めることができる。これは組み込み関数のpowを使うと十分に早い（O(log MOD)）。
        '''
        return self.__class__(pow(self.n, self.mod - 2, self.mod))

    def __ifloordiv__(self, other):
        self *= pow(int(other), self.mod - 2, self.mod)
        return self

    def __rfloordiv__(self, other):
        return self.__class__(other).__floordiv__(self)

    def __add__(self, other):
        return self.__class__(self.n + int(other))

    def __sub__(self, other):
        return self.__class__(self.n - int(other))

    def __mul__(self, other):
        return self.__class__(self.n * int(other))

    def __floordiv__(self, other):
        return self.__class__(self.n * Modint(int(other)).inverse())

    # def comb(self, n: int, k: int):
    #     '''
    #     コンビネーション絡みの定義。comb(n,k):特に前処理をせずnCkを求める
    #     毎回O(N)かかるので死ぬ覚悟でO(N^2)を投げるくらいしか無理

    #     ちなみにですが，これでABC132_D()を出すとPyPy3で1932msくらいですれすれセーフ
    #     '''
    #     if n < k or k < 0:
    #         return Modint(0)
    #     res = Modint(1)
    #     for i in range(int(k)):
    #         res *= Modint(n - i)
    #         res //= Modint(i + 1)
    #     return res

    # def H(self, n: int, k: int):
    #     if n < 0 or k < 0:
    #         return Modint(0)
    #     elif n == 0 and k == 0:
    #         return Modint(1)
    #     else:
    #         return self.comb(n + k - 1, n)


COMBINATION_MAX = 2 * 10**5
class Combination():
    def __init__(self, sz=COMBINATION_MAX):
        '''
        Nまでの階乗とその逆元（割り算用）を計算しておく。前処理にO(N)，P, C, Hそれぞれの計算はO(1)。N = 200000なら割と余裕で通る。
        '''
        self._fact = [Modint(0)] * (sz + 1)
        self._rfact = [Modint(0)] * (sz + 1)
        self._fact[0] = Modint(1)
        self._rfact[sz] = Modint(1)
        for i in range(1, sz + 1):
            self._fact[i] = self._fact[i - 1] * Modint(i)
        self._rfact[sz] = self._fact[sz].inverse()
        for i in range(sz - 1, -1, -1):
            self._rfact[i] = self._rfact[i + 1] * Modint(i + 1)

    def fact(self, k: int) -> int:
        """階乗の計算"""
        return self._fact[k]

    def rfact(self, k: int) -> int:
        """階乗の逆元の計算"""
        return self._rfact[k]

    def P(self, n: int, k: int) -> Modint:
        '''
        nPkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nPkのn (0<=n<=N)
            k (int) : nPkのk （0<=k<=n）

        Returns
        ----------
            Modint : nPkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        return self._fact[n] * self._rfact[n - k]

    def C(self, n: int, k: int) -> Modint:
        '''
        nCkの値を返す。nはあらかじめ前処理されたN以下でないとダメ

        Parameters
        ----------
            n (int) : nCkのn(0<=n<=N)
            k (int) : nCkのk（0<=k<=n）

        Returns
        ----------
            Modint : nCkをModint型で返す。Modintに依存。
        '''
        if k < 0 or n < k:
            return Modint(0)
        if n - k < k:
            k = n - k
        return self._fact[n] * self._rfact[k] * self._rfact[n - k]

    def H(self, n: int, k: int) -> Modint:
        '''
        nHkの値を返す。nはあらかじめ前処理された n+k-1 以下でないとダメ

        ちなみにnHkはn個の区別できないものをk個の箱に分けるパターンの数で，結局n+k-1Cnになる。

        Parameters
        ----------
            n (int) : nHkのn(0<=n<=N)
            k (int) : nHkのk（0<=k<=n）

        Returns
        ----------
            Modint : nHkをModint型で返す。Modintに依存。
        '''
        if n < 0 or k < 0:
            return Modint(0)
        elif k == 0:
            return Modint(1)
        return self.C(n + k - 1, k)

# END CUT HERE

if __name__ == '__main__':

    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]"

    # write code
    issafe = [True for i in range(N + 10)]
    for i in a:
        issafe[i] = False
    dp = [Modint(0) for i in range(N + 10)]
    dp[0] = Modint(1)
    if issafe[1]:
        dp[1] = Modint(1)
    for n in range(2, N + 2):
        if issafe[n - 1]:
            dp[n] += dp[n - 1]
            # debug(n, "!")
        if issafe[n - 2]:
            dp[n] += dp[n - 2]
            # debug(n, "?")
    print(dp[N])