分数: 366 分
问题陈述
高桥正站在楼梯前, N 步骤。高桥目前正在迈出步伐 0 (地面)并旨在达到步骤 N (顶部)。
高桥一招可以从当前步骤移动到当前步骤 1 上面的步骤, 2 上述步骤,或 3 步骤同上。也就是说,当他当前踏上台阶时 i,他可以直接移动到步骤 i+1,步骤 i+2,或步骤 i+3。不过,他只落在目标台阶上,并没有落在任何中间台阶上。
楼梯的一些台阶已损坏且破损。有 M 破碎的步骤,这是步骤 B_1, B_2, \ldots, B_M (全部 B_i 是不同的)。不可能在破损的台阶上着陆。然而,可以跳过破损的台阶(通过它而不落地)。例如,即使步骤 i+1 已损坏,高桥可以从步骤中移动 i 到步骤 i+2 或步骤 i+3。保证了这一步 0 (地面)和台阶 N (上)没有坏。
求高桥从台阶向上爬的方式数 0 到步骤 N。如果没有有效的爬升方式,输出 0。由于答案可能非常大,因此输出除以的余数 10^9 + 7.
约束
- 1 \leq N \leq 10^5
- 0 \leq M \leq N - 1
- 1 \leq B_i \leq N - 1 (1 \leq i \leq M)
- 全部 B_i 是不同的
- B_1, B_2, \ldots, B_M 不一定按升序排列
- 所有输入均为整数
输入
N M B_1 B_2 \ldots B_M
- 第一行包含一个整数 N 代表步数和一个整数 M 代表中断的步骤数,以空格分隔。
- 第二行包含 M 整数 B_1, B_2, \ldots, B_M 代表断步数,以空格分隔。顺序是任意的。如果 M = 0,未给出第二行。
输出
在一行中输出高桥从台阶可以爬升的方式数 0 到步骤 N,模数 10^9 + 7.
示例输入 1
5 1 3
示例输出 1
5
示例输入 2
4 3 1 2 3
示例输出 2
0
示例输入 3
20 3 5 10 15
示例输出 3
6728
示例输入 4
1000 5 100 200 300 400 500
示例输出 4
935523008
示例输入 5
1 0
示例输出 5
1