Ira and Flamenco solution codeforces

Ira loves Spanish flamenco dance very much. She decided to start her own dance studio and found $n$ students, $i$ th of whom has level $a_{i}$ .

Ira can choose several of her students and set a dance with them. So she can set a huge number of dances, but she is only interested in magnificent dances. The dance is called magnificent if the following is true:

exactly $m$ students participate in the dance;
levels of all dancers are pairwise distinct;
levels of any two dancers have an absolute difference strictly less than $m$ .

For example, if $m = 3$ and $a = [4, 2, 2, 3, 6]$ , the following dances are magnificent (students participating in the dance are highlighted in red): $[4, 2, 2, 3, 6]$ , $[4, 2, 2, 3, 6]$ . At the same time dances $[4, 2, 2, 3, 6]$ , $[4, 2, 2, 3, 6]$ , $[4, 2, 2, 3, 6]$ are not magnificent.

In the dance $[4, 2, 2, 3, 6]$ only $2$ students participate, although $m = 3$ .

The dance $[4, 2, 2, 3, 6]$ involves students with levels $2$ and $2$ , although levels of all dancers must be pairwise distinct.

In the dance $[4, 2, 2, 3, 6]$ students with levels $3$ and $6$ participate, but $| 3 - 6 | = 3$ , although $m = 3$ .

Help Ira count the number of magnificent dances that she can set. Since this number can be very large, count it modulo $10^{9} + 7$ . Two dances are considered different if the sets of students participating in them are different.

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 10^{4}$ ) — number of testcases.

The first line of each testcase contains integers $n$ and $m$ ( $1 \leq m \leq n \leq 2 \cdot 10^{5}$ ) — the number of Ira students and the number of dancers in the magnificent dance.

The second line of each testcase contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ) — levels of students.

It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^{5}$ .