Subșiruri importante

Gomory and Hu found an array of natural numbers in the basement of their house. While wondering what the meaning of this array might be, they started playing with several subsequences of it, eventually reaching contradictory opinions.

Gomory is firmly convinced that a subsequence which could reveal important information is one in which the absolute difference between the values of any two elements is less than or equal to a number $K$. At the same time, Hu completely disagrees with this statement, considering that a subsequence would be important if the absolute difference between the positions of any two elements is less than or equal to a number $D$.

After a long argument, they ask for your help in finding the number of subsequences that are important to both of them.

Task

Formally, you are given an array $V$ of natural numbers, of length $N$. You must compute the number of subsequences of this array in which the absolute difference between the values of any two elements is less than or equal to $K$ and the absolute difference between the positions of any two elements is less than or equal to $D$.

Input Data

On the first line, the natural numbers $N$, $K$ and $D$ are read, with the meaning given in the statement.

On the second line, the $N$ natural numbers that form the array $V$ are read, separated by spaces.

Output Data

You must output a single natural number representing the number of subsequences of the array $V$ in which the absolute difference between any two values is less than or equal to $K$ and the absolute difference between the positions of any two elements is less than or equal to $D$, modulo $10^9+7$.

Constraints

• $1 \le D \le N \le 200\,000$
• $1 \le K,\ V_i \le 10^9$
• A subsequence is obtained from the original array by removing elements at arbitrary positions.

Example

stdin

5 10 3
20 10 30 40 10

stdout

9

Explanation

In the given example, the good subsequences are: $(20)$, $(20,10)$, $(20,30)$, $(10)$, $(10,10)$, $(30)$, $(30,40)$, $(40)$, $(10)$.