#P1833F. Ira and Flamenco

    ID: 8467 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>combinatoricsconstructive algorithmsdata structuresimplementationmathsortingstwo pointers*1700

Ira and Flamenco

No submission language available for this problem.

Description

Ira loves Spanish flamenco dance very much. She decided to start her own dance studio and found nn students, iith of whom has level aia_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 mm students participate in the dance;
  • levels of all dancers are pairwise distinct;
  • levels of every two dancers have an absolute difference strictly less than mm.

For example, if m=3m = 3 and a=[4,2,2,3,6]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][\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6], [4,2,2,3,6][\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]. At the same time dances [4,2,2,3,6][\color{red}{4}, 2, 2, \color{red}{3}, 6], [4,2,2,3,6][4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6], [4,2,2,3,6][\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}] are not magnificent.

In the dance [4,2,2,3,6][\color{red}{4}, 2, 2, \color{red}{3}, 6] only 22 students participate, although m=3m = 3.

The dance [4,2,2,3,6][4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6] involves students with levels 22 and 22, although levels of all dancers must be pairwise distinct.

In the dance [4,2,2,3,6][\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}] students with levels 33 and 66 participate, but 36=3|3 - 6| = 3, although m=3m = 3.

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

The first line contains a single integer tt (1t1041 \le t \le 10^4) — number of testcases.

The first line of each testcase contains integers nn and mm (1mn21051 \le m \le n \le 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 nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9) — levels of students.

It is guaranteed that the sum of nn over all testcases does not exceed 21052 \cdot 10^5.

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

Input

The first line contains a single integer tt (1t1041 \le t \le 10^4) — number of testcases.

The first line of each testcase contains integers nn and mm (1mn21051 \le m \le n \le 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 nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9) — levels of students.

It is guaranteed that the sum of nn over all testcases does not exceed 21052 \cdot 10^5.

Output

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

Sample Input 1

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

Sample Output 1

5
2
10
0
5
11
1
2
1

Note

In the first testcase, Ira can set such magnificent dances: [8,10,10,9,6,11,7][\color{red}{8}, 10, 10, \color{red}{9}, \color{red}{6}, 11, \color{red}{7}], [8,10,10,9,6,11,7][\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, 11, \color{red}{7}], [8,10,10,9,6,11,7][\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, 11, \color{red}{7}], [8,10,10,9,6,11,7][\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, \color{red}{11}, 7], [8,10,10,9,6,11,7][\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, \color{red}{11}, 7].

The second testcase is explained in the statements.