F. Ира и фламенко
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ира очень любит испанский танец фламенко. Она решила основать собственную танцевальную студию и нашла $$$n$$$ учеников, $$$i$$$-й из которых имеет уровень $$$a_i$$$.

Ира может выбрать несколько своих учеников и поставить с ними танец. Таким образом она может поставить огромное количество танцев, но её интересуют только великолепные танцы. Танец называется великолепным, если выполнено следующее:

  • в танце участвуют ровно $$$m$$$ учеников;
  • уровни всех танцоров попарно различны;
  • уровни любых двух танцоров отличаются строго меньше чем на $$$m$$$.

Например, если $$$m = 3$$$ и $$$a = [4, 2, 2, 3, 6]$$$, следующие танцы являются великолепными (красным цветом выделены ученики, участвующие в танце): $$$[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]$$$. В то же время танцы $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$, $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ не являются великолепными.

В танце $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$ участвуют $$$2$$$ ученика, хотя $$$m = 3$$$.

В танце $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$ участвуют ученики с уровнями $$$2$$$ и $$$2$$$, хотя уровни всех танцоров должны быть попарно различны.

В танце $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ участвуют ученики с уровнями $$$3$$$ и $$$6$$$, но $$$|3 - 6| = 3$$$, хотя $$$m = 3$$$.

Помогите Ире посчитать количество великолепных танцев, которые она может поставить. Так как это число может быть очень большим, посчитайте его по модулю $$$10^9 + 7$$$. Два танца считаются различными, если различны наборы учеников, участвующих в них.

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

В первой строке дано единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — количество учеников Иры и количество танцоров в великолепном танце.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — уровни учеников.

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

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

Для каждого набора входных данных выведите единственное число — количество великолепных танцев по модулю $$$10^9 + 7$$$.

Пример
Входные данные
9
7 4
8 10 10 9 6 11 7
5 3
4 2 2 3 6
8 2
1 5 2 2 3 1 3 3
3 3
3 3 3
5 1
3 4 3 10 7
12 3
5 2 1 1 4 3 5 5 5 2 7 5
1 1
1
3 2
1 2 3
2 2
1 2
Выходные данные
5
2
10
0
5
11
1
2
1
Примечание

В первом наборе входных данных Ира может поставить только такие великолепные танцы: $$$[\color{red}{8}, 10, 10, \color{red}{9}, \color{red}{6}, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, \color{red}{11}, 7]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, \color{red}{11}, 7]$$$.

Второй набор входных данных разобран в условии.