310439: CF1833F. Ira and Flamenco
Description
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.
InputThe 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$.
OutputFor each testcase, print a single integer — the number of magnificent dances. Since this number can be very large, print it modulo $10^9 + 7$.
ExampleInput9 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 2Output
5 2 10 0 5 11 1 2 1Note
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.
Input
题意翻译
在长度为 $n$ 的数组 $\{a\}$ 中选择 $m$ 个数,满足下列要求: - 恰好选择 $m$ 个数; - 选中的数互不相同; - 选中的数两两之差都严格小于 $m$。 求有多少种满足要求的选择方法,答案对 $10^9+7$ 取模。Output
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 ```