Ira非常喜欢西班牙弗拉明戈舞。她决定创办自己的舞蹈工作室,并找到了 $$$n$$$ 名学生,其中 $$$i$$$ 级别为 $$$a_i$$$。
Ira 可以选择她的几个学生并与他们一起跳舞。所以她可以设定数量庞大的舞蹈,但她只对华丽的舞蹈感兴趣。如果满足以下条件,则该舞蹈被称为华丽:
- 恰好 $$$m$$$ 学生参加舞蹈;
- 所有舞者的等级都是成对不同的;
- 每两个舞者的水平绝对差异严格小于$$$m$$$。
例如,如果 $$$m = 3$$$ 且 $$$a = [4, 2, 2, 3, 6]$$$,则以下舞蹈非常精彩(参与舞蹈的学生以红色突出显示): $$$[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\颜色{红色}{4},\颜色{红色}{2},2,\颜色{红色}{3},6]$$$。同时跳舞$$$[\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}]$$$并不华丽。
在舞蹈$$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$中,只有$$$2$$$学生参加,尽管$$$m = 3$$$。
舞蹈 $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$ 涉及级别为 $$$2$$$ 和 $$$2$$$ 的学生,尽管所有舞者的级别必须成对不同。
舞蹈中$$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$级别为$$$3$$$和$$$6$$$的学生参加,但$$$|3 - 6| = 3$$$,尽管 $$$m = 3$$$。
帮助艾拉数一下她可以设置的华丽舞蹈的数量。由于这个数字可能非常大,因此对 $$$10^9 + 7$$$ 进行模数计算。如果参加两个舞蹈的学生组不同,则认为两个舞蹈是不同的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — Ira 学生的数量和华丽舞蹈中舞者的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 学生的级别。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数——华丽舞蹈的数量。由于这个数字可能非常大,因此打印它对 $$$10^9 + 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
注意
在第一个测试用例中,Ira 可以设置如此华丽的舞蹈: $$$[\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]$$$、$$$[\颜色{红色}{8}、\颜色{红色}{10}、10、\颜色{红色}{9}、6、\颜色{红色}{11}、7]$$$。
第二个测试用例在语句中进行了解释。