← Home
write a go solution for Description:
Ira loves Spanish flamenco dance very much. She decided to start her own dance studio and found n students, ith 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 every 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): [colorred4,2,colorred2,colorred3,6], [colorred4,colorred2,2,colorred3,6]. At the same time dances [colorred4,2,2,colorred3,6], [4,colorred2,colorred2,colorred3,6], [colorred4,2,2,colorred3,colorred6] are not magnificent.

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

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

In the dance [colorred4,2,2,colorred3,colorred6] 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 Format:
The first line contains a single integer t (1<=t<=10^4) — number of testcases.

The first line of each testcase contains integers n and m (1<=m<=n<=2*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,ldots,a_n (1<=a_i<=10^9) — levels of students.

It is guaranteed that the sum of n over all testcases does not exceed 2*10^5.

Output Format:
For each testcase, print a single integer — the number of magnificent dances. Since this number can be very large, print it modulo 10^9+7.

Note:
In the first testcase, Ira can set such magnificent dances: [colorred8,10,10,colorred9,colorred6,11,colorred7], [colorred8,colorred10,10,colorred9,6,11,colorred7], [colorred8,10,colorred10,colorred9,6,11,colorred7], [colorred8,10,colorred10,colorred9,6,colorred11,7], [colorred8,colorred10,10,colorred9,6,colorred11,7].

The second testcase is explained in the statements.. Output only the code with no comments, explanation, or additional text.