配点 : $300$ 点

問題文

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

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

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

制約

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

入力

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

$N$ $M$

$a_1$

$a_2$

$.$

$.$

$.$

$a_M$

出力

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

6 1
3

4

移動方法は以下の $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$

10 2
4
5

0

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

100 5
1
23
45
67
89

608200469

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