台阶

题目描述

有一段 $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$ 的余数。

样例

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$ 的余数。

数据范围

• $1 \le N \le 10^5$
• $0 \le M \le N-1$
• $1 \le a_1 \lt a_2 \lt ... \lt a_M \le N-1$