Problem Description

Takahashi's home is at point $0$ on the $x$-axis, and the AtCoder office is at point $D$ on the $x$-axis. There are also $N$ gas stations on the $x$-axis, with coordinates $X_1, X_2, ..., X_N$.

Every day, Takahashi travels from home to the office by car. The car's fuel tank has a capacity of $F$ liters, and it consumes $1$ liter of fuel for every unit of distance traveled. Takahashi starts at home with a full tank of fuel and refuels the car at each gas station as follows:

• If the fuel is $T$ liters or more, he does not refuel.
• Otherwise, he refuels until the tank is full.

The car can only move in the positive $x$-axis direction. If the fuel tank runs out at a location that is neither a gas station nor the office, the trip to the office fails.

You are planning to replace some of the $N$ gas stations (it can be zero) with bookstores. Find the number of sets of gas stations that can be replaced such that Takahashi can still travel from home to the office using the method described above, modulo $10^9 + 7$.

Input Format

The input is given from the standard input in the following format:

$D$ $F$ $T$ $N$ $X_1$ $X_2$ $...$ $X_N$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

10 8 5 2
3 7

Sample Output #1

2

Sample Input #2

8 8 5 5
1 2 3 4 5

Sample Output #2

32

Sample Input #3

100 50 30 1
40

Sample Output #3

0

Sample Input #4

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

Sample Output #4

1002

Notes/Hints

Constraints

• $0 < T \leq F \leq 10^9$
• $1 \leq N \leq 100,000$
• $0 < X_1 < X_2 < ... < X_N < D \leq 10^9$
• All input values are integers.

Sample Explanation 1

When the gas stations at coordinates $X_1 = 3, X_2 = 7$ are numbered $1, 2$ respectively, the sets that satisfy the condition are $\{\}$, $\{1\}$, making a total of $2$ sets.

见题面 Input 部分

见题面 Output 部分