C - 典型的楼梯

分数：300分

问题描述

一条楼梯有N个台阶。高桥现在站在楼梯的底部，也就是第0个台阶上。 他每次可以一次爬一步或者两步。

然而，第$a_1$个、$a_2$个、$a_3$个，……，$a_M$个台阶的踏板都坏了，所以踩上这些台阶是危险的。

有多少种方式可以爬到最高的台阶，也就是第N个台阶，同时不踏上坏的台阶？ 结果对$1\ 000\ 000\ 007$取模。

约束

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

输入

输入以以下格式从标准输入中给出：

$N$ $M$

$a_1$

$a_2$

$.$

$.$

$.$

$a_M$

输出

按照条件，输出爬楼梯的方式数量，对$1\ 000\ 000\ 007$取模。

6 1
3

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$取模后输出结果。