AT_abc129_c [ABC129C] Typical Stairs

[problemUrl]: https://atcoder.jp/contests/abc129/tasks/abc129_c $ N $ 段の階段があります。高橋君は現在、上り口($ 0 $ 段目)にいます。 高橋君は一歩で $ 1 $ 段か $ 2 $ 段上ることができます。 ただし、$ a_1,a_2,a_3,....a_M $ 段目の床は壊れており、その段に足を踏み入れることは危険です。 壊れている床を踏まないようにしながら、最上段($ N $ 段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 総数を $ 1,000,000,007 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ 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 $ で割った余りを出力することに注意して下さい。