配点 : 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