310439: CF1833F. Ira and Flamenco

F. Ira and Flamencotime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 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): $[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$, $[\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]$. At the same time dances $[\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}]$ are not magnificent.

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

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

In the dance $[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{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 \le t \le 10^4$) — number of testcases.

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

It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \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 $10^9 + 7$.

ExampleInput

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

Output

5
2
10
0
5
11
1
2
1

Note

In the first testcase, Ira can set such magnificent dances: $[\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]$.

The second testcase is explained in the statements.

题目大意：
Ira非常喜欢西班牙的弗拉门戈舞。她决定开设自己的舞蹈工作室，并找到了n个学生，其中第i个学生的级别为a_i。Ira可以选择她的几个学生来编排舞蹈，因此她可以编排大量的舞蹈，但她只对壮观的舞蹈感兴趣。如果以下条件为真，则舞蹈被称为壮观：
- 恰好m个学生参加舞蹈；
- 所有舞者的级别两两不同；
- 每两个舞者的级别之间的绝对差严格小于m。

例如，如果m=3且a=[4,2,2,3,6]，则以下舞蹈是壮观的（参加舞蹈的学生突出显示为红色）：[4,2,2,3,6]，[4,2,2,3,6]。同时，舞蹈[4,2,2,3,6]，[4,2,2,3,6]，[4,2,2,3,6]不是壮观的。

在舞蹈[4,2,2,3,6]中，只有2个学生参加，尽管m=3。

在舞蹈[4,2,2,3,6]中，有级别为2和2的学生参加，尽管所有舞者的级别必须是两两不同的。

在舞蹈[4,2,2,3,6]中，有级别为3和6的学生参加，但|3-6|=3，尽管m=3。

帮助Ira计算她可以编排的壮观舞蹈的数量。由于这个数字可能非常大，请将其除以10^9+7取模。如果参加的两个舞蹈的学生集不同，则认为它们是不同的。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含整数n和m（1≤m≤n≤2*10^5）——Ira的学生的数量和在壮观舞蹈中舞者的数量。
- 每个测试用例的第二行包含n个整数a_1，a_2，…，a_n（1≤a_i≤10^9）——学生的级别。

保证所有测试用例的n之和不超过2*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
```题目大意： Ira非常喜欢西班牙的弗拉门戈舞。她决定开设自己的舞蹈工作室，并找到了n个学生，其中第i个学生的级别为a_i。Ira可以选择她的几个学生来编排舞蹈，因此她可以编排大量的舞蹈，但她只对壮观的舞蹈感兴趣。如果以下条件为真，则舞蹈被称为壮观： - 恰好m个学生参加舞蹈； - 所有舞者的级别两两不同； - 每两个舞者的级别之间的绝对差严格小于m。 例如，如果m=3且a=[4,2,2,3,6]，则以下舞蹈是壮观的（参加舞蹈的学生突出显示为红色）：[4,2,2,3,6]，[4,2,2,3,6]。同时，舞蹈[4,2,2,3,6]，[4,2,2,3,6]，[4,2,2,3,6]不是壮观的。 在舞蹈[4,2,2,3,6]中，只有2个学生参加，尽管m=3。 在舞蹈[4,2,2,3,6]中，有级别为2和2的学生参加，尽管所有舞者的级别必须是两两不同的。 在舞蹈[4,2,2,3,6]中，有级别为3和6的学生参加，但|3-6|=3，尽管m=3。 帮助Ira计算她可以编排的壮观舞蹈的数量。由于这个数字可能非常大，请将其除以10^9+7取模。如果参加的两个舞蹈的学生集不同，则认为它们是不同的。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含整数n和m（1≤m≤n≤2*10^5）——Ira的学生的数量和在壮观舞蹈中舞者的数量。 - 每个测试用例的第二行包含n个整数a_1，a_2，…，a_n（1≤a_i≤10^9）——学生的级别。 保证所有测试用例的n之和不超过2*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 ```