You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

乔治正在玩一个有趣的跳跃游戏。游戏的场地是一条由 $N$ 个格子组成的直线跑道，乔治现在站在起点，也就是第 0 个格子上。

在游戏中，乔治每次可以向前跳 1 个格子 或者 2 个格子。然而，跑道上有一些格子是坏的，踩到这些格子会导致游戏失败。这些坏的格子编号分别是 a₁, a₂, a₃, ..., a_m。

乔治想知道，他有多少种方法可以跳到终点（第 $N$ 个格子），同时避开所有坏的格子？答案需要对 1,000,000,007 取模。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示跑道的总格子数和坏格子的数量。

接下来 $M$ 行，每行一个整数，表示一个坏格子的编号。

输出格式

输出一个整数，表示乔治跳到终点的方法数，答案需要对 1,000,000,007 取模。

6 1
3

4

样例解释

以下是乔治跳跃的四种方法：

• 0 → 1 → 2 → 4 → 5 → 6
• 0 → 1 → 2 → 4 → 6
• 0 → 2 → 4 → 5 → 6
• 0 → 2 → 4 → 6

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$