Typical Stairs

题目描述

有一个有 $N$ 级台阶的楼梯。Takahashi 现在站在楼梯脚下，也就是第 $0$ 级台阶上。 他每次可以向上爬一阶或两阶。 然而，第 $a_1$ 级、第 $a_2$ 级、第 $a_3$ 级、$\ldots$、第 $a_M$ 级台阶的踏板已经坏了，所以踩到那些台阶是危险的。 有多少种方法可以爬到顶层，也就是第 $N$ 级台阶，而不踩到坏掉的台阶？ 请对 $1\ 000\ 000\ 007$ 取模后输出方法数。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $a_1$ $a_2$ $.$ $.$ $.$ $a_M$

输出格式

输出在该条件下爬上楼梯的方法数，对 $1\ 000\ 000\ 007$ 取模。

6 1
3

4

10 2
4
5

0

100 5
1
23
45
67
89

608200469

提示

$1 \leq N \leq 10^5$ $0 \leq M \leq N-1$ 1 \leq a_1 < a_2 < $...$ < a_M \leq N-1有四种爬上楼梯的方法，如下：

$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$
也可能没有不踩到坏掉台阶的爬法。
请务必对 $1\ 000\ 000\ 007$ 取模并输出。

标签: AtCoder|abc129C

来源

AtCoder|abc129C