CF1833F.Ira and Flamenco
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ai .
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): [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 109+7 . Two dances are considered different if the sets of students participating in them are different.
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — number of testcases.
The first line of each testcase contains integers n and m ( 1≤m≤n≤2⋅105 ) — the number of Ira students and the number of dancers in the magnificent dance.
The second line of each testcase contains n integers a1,a2,…,an ( 1≤ai≤109 ) — levels of students.
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105 .
输出格式
For each testcase, print a single integer — the number of magnificent dances. Since this number can be very large, print it modulo 109+7 .
输入输出样例
输入#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
输出#1
5 2 10 0 5 11 1 2 1
说明/提示
In the first testcase, Ira can set such magnificent dances: [8,10,10,9,6,11,7] , [8,10,10,9,6,11,7] , [8,10,10,9,6,11,7] , [8,10,10,9,6,11,7] , [8,10,10,9,6,11,7] .
The second testcase is explained in the statements.