研学栈道的位置从 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,2;1,2,1;2,1,1。序列2,2虽然也到达位置4,但连续两步都是2格,不合法。
唯一合法步长序列是1,1,2,1,依次落在位置1、2、4、5,跨过封闭位置3。其他走法会落在位置3,或连续走两步2格。