← 返回题目列表

AtCoder · awc0095_c

C. 爬楼梯的方法

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

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