This is the hard version of this problem. The only difference between the easy and hard versions is the constraints on $k$ and $m$. In this version of the problem, you need to output the answer by modulo $10^9+7$.

You are given a sequence $a$ of length $n$ consisting of integers from $1$ to $n$. The sequence may contain duplicates (i.e. some elements can be equal).

Find the number of tuples of $m$ elements such that the maximum number in the tuple differs from the minimum by no more than $k$. Formally, you need to find the number of tuples of $m$ indices $i_1 < i_2 < \ldots < i_m$, such that

$$\max(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) - \min(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) \le k.$$

For example, if $n=4$, $m=3$, $k=2$, $a=[1,2,4,3]$, then there are two such triples ($i=1, j=2, z=4$ and $i=2, j=3, z=4$). If $n=4$, $m=2$, $k=1$, $a=[1,1,1,1]$, then all six possible pairs are suitable.

As the result can be very large, you should print the value modulo $10^9 + 7$ (the remainder when divided by $10^9 + 7$).

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains three integers $n$, $m$, $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 100$, $1 \le k \le n$) — the length of the sequence $a$, number of elements in the tuples and the maximum difference of elements in the tuple.

The next line contains $n$ integers $a_1, a_2,\ldots, a_n$ ($1 \le a_i \le n$) — the sequence $a$.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output $t$ answers to the given test cases. Each answer is the required number of tuples of $m$ elements modulo $10^9 + 7$, such that the maximum value in the tuple differs from the minimum by no more than $k$.