问题描述

高桥君的家位于$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