题目描述

$N$ 段の階段があります。高橋君は現在、上り口($0$ 段目)にいます。 高橋君は一歩で $1$ 段か $2$ 段上ることができます。

ただし、$a_1,a_2,a_3,....a_M$ 段目の床は壊れており、その段に足を踏み入れることは危険です。

壊れている床を踏まないようにしながら、最上段($N$ 段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 総数を $1,000,000,007$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $M$ $a_1$ $a_2$ $.$ $.$ $.$ $a_M$

输出格式

条件を満たすような移動方法の総数を、$1,000,000,007$ で割った余りを出力してください。

题目大意

有 $n$ 级台阶，有 $m$ 级台阶不能走，分别为 $a_1\ldots a_m$ 级台阶。

现在你要从第 $0$ 级台阶出发，每次可以向上一格或两格，求走到第 $n$ 级台阶的方案数 $\bmod 10^9+7$ 的结果。

$1\le n \le 10^5$，$0\le m\le n-1$，$1\le a_1<a_2<\ldots a_m\le n-1$。

6 1
3

4

10 2
4
5

0

100 5
1
23
45
67
89

608200469

提示

制約

• $1\ \leqq\ N\ \leqq\ 10^5$
• $0\ \leqq\ M\ \leqq\ N-1$
• $1\ \leqq\ a_1\ ...$ $$

Sample Explanation 1

移動方法は以下の $4$ 通りです。 - $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 Explanation 2

壊れている床を踏まないような移動方法がない場合もあります。

Sample Explanation 3

総数を $1,000,000,007$ で割った余りを出力することに注意して下さい。