241994 - 研学栈道通行

题目描述

研学栈道的位置从 0 到 n 编号。小明从位置 0 出发,只能向前走,每一步可以前进1格或2格,最终必须恰好停在位置 n,不能走过终点。

为了保持安全,不能连续两步都前进2格。例如步长序列 2,1,2 符合要求,1,2,2 不符合要求。

栈道上有 m 个位置暂时封闭,不能落脚,但允许一步跨过。例如位置1封闭时,可以从0直接走到2。位置0始终可以出发,终点n也可能被封闭。

如果两个走法的步长序列不同,就视为不同走法。请计算合法走法数量,输出它除以1000000007的余数。如果没有合法走法,输出0。

输入

第一行包含两个整数 n,m。

当 m>0 时,第二行包含 m 个互不相同的整数,表示封闭位置,顺序任意。m=0 时没有第二行。

【数据范围】

对全部数据,1\le n\le100000,0\le m\le n,每个封闭位置都在1到n之间且互不相同。

输出

输出一个整数,表示合法走法数量对1000000007取余后的结果。

样例

输入

4 0

输出

4

输入

5 1
3

输出

1
说明

【样例解释1】

合法步长序列为1,1,1,1;1,1,2;1,2,1;2,1,1。序列2,2虽然也到达位置4,但连续两步都是2格,不合法。

【样例解释2】

唯一合法步长序列是1,1,2,1,依次落在位置1、2、4、5,跨过封闭位置3。其他走法会落在位置3,或连续走两步2格。

标签
题目参数
时间限制 2 秒
内存限制 256 MB
提交次数 2
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题