← 返回题目列表

AtCoder · abc129_c

C. 典型楼梯

中文机器翻译题面 查看原题

分数: 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.