← 返回题目列表

AtCoder · code_festival_2018_quala_d

D. 通勤

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

配点 : 700 点

問題文

高桥君的家是 x 轴上的点 在 0 ,AtCoder 的办公室是 它位于 x 轴上的点 在 D 。 另外,x 在轴上 有 N 个加油站,其坐标是 X_1, X_2, ..., X_N 。

高桥君每天从家开车到办公室。 这辆车的油箱容量是 F 升和距离 1 每次移动时加油 1 消耗升。 高桥带着满油的油离开家,每次经过加油站时都会按如下方式给汽车加油。

  • 燃料 T 如果剩余量超过升,请勿加油。
  • 如果没有,请加油直至油箱加满。

前往办公室时,汽车 x 您只能沿轴的正方向移动。如果您的油箱在既不是加油站也不是您办公室的地方耗尽,您的办公室之旅将失败。

你 一些 N 加油站 (0 (我不在乎它是不是书店))我正在尝试将其重建为书店。 计算将重建为书店的加油站数量,并且即使在重建之后,高桥也可以使用上述方法从他的家开车到办公室。 除以 10^9 + 7 后求余数。

制約

  • 0 < T \leq F \leq 10^9
  • 1 \leq N \leq 100,000
  • 0 < X_1 < X_2 < ... < X_N < D \leq 10^9
  • 所有输入值都是整数。

入力

输入将以以下格式从标准输入给出。

D F T N
X_1 X_2 ... X_N

出力

打印答案。 每个加油站的


入力例 1

10 8 5 2
3 7

出力例 1

2

座標 X_1 = 3, X_2 = 7 。 当编号为 1, 2 时,满足条件的集合为 \{\}, \{1\} 的 2 件。


入力例 2

8 8 5 5
1 2 3 4 5

出力例 2

32

入力例 3

100 50 30 1
40

出力例 3

0

入力例 4

1000 752 687 10
94 186 299 395 406 430 772 782 807 999

出力例 4

1002