分数: 300 点
问题陈述
有一个楼梯 N 步骤。高桥现在站在楼梯脚下,也就是楼梯上。 0- 第一步。 他一次可以爬一两级台阶。
然而, a_1-th, a_2-th, a_3-th, \ldots, a_M第级台阶已损坏,因此踏上这些台阶很危险。
有多少个可以爬到最上面的台阶,即 N第一步,没有踏上破碎的台阶? 求计数模数 1\ 000\ 000\ 007.
约束
- 1 \leq N \leq 10^5
- 0 \leq M \leq N-1
- 1 \leq a_1 < a_2 < ... < a_M \leq N-1
输入
输入由标准输入按以下格式给出:
N M a_1 a_2 . . . a_M
输出
打印条件下爬楼梯的次数,取模 1\ 000\ 000\ 007.
示例输入 1
6 1 3
示例输出 1
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
示例输入 2
10 2 4 5
示例输出 2
0
不踏上破损的台阶,可能就无法爬上楼梯。
示例输入 3
100 5 1 23 45 67 89
示例输出 3
608200469
请务必打印模数计数 1\ 000\ 000\ 007.