E2. Близкие наборы (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Единственное различие между простой и сложной версиями заключается в ограничениях на $$$k$$$ и $$$m$$$. В этой версии задачи нужно выводить ответ по модулю $$$10^9+7$$$.

Вам задана последовательность $$$a$$$ длины $$$n$$$, состоящая из целых чисел от $$$1$$$ до $$$n$$$. Среди чисел могут быть одинаковые.

Найдите количество наборов из $$$m$$$ элементов, таких что максимальное число в наборе отличается от минимального не больше, чем на $$$k$$$. Формально, вам нужно найти количество наборов из $$$m$$$ индексов $$$i_1 < i_2 < \ldots < i_m$$$, таких что

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

Например, если $$$n=4$$$, $$$m=3$$$, $$$k=2$$$, $$$a=[1,2,4,3]$$$, то существуют две такие тройки ($$$i=1, j=2, z=4$$$ и $$$i=2, j=3, z=4$$$). Если же $$$n=4$$$, $$$m=2$$$, $$$k=1$$$, $$$a=[1,1,1,1]$$$, то все шесть возможных пар подходят.

Поскольку ответ может быть достаточно большим, вам нужно посчитать его по модулю $$$10^9 + 7$$$ (остаток при делении на число $$$10^9 + 7$$$).

Входные данные

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных находится три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 100$$$, $$$1 \le k \le n$$$) — длина последовательности $$$a$$$, количество элементов в искомых наборах и максимальная разница элементов в наборе.

В следующей строке находятся $$$n$$$ целых чисел $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — последовательность $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ ответов на наборы входных данных. Каждый ответ — это количество наборов из $$$m$$$ элементов по модулю $$$10^9 + 7$$$, таких что максимальное число в наборе отличается от минимального не больше, чем на $$$k$$$.

Пример
Входные данные
4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4
Выходные данные
2
6
1
20