这是这个问题的困难版本。简单版本和困难版本之间的唯一区别是对 $$$k$$$ 和 $$$m$$$ 的约束。在这个版本的问题中,您需要以 $$$10^9+7$$$ 为模输出答案。
给定一个序列 $$$a$$$,长度为 $$$n$$$,由从 $$$1$$$ 到 $$$n$$$ 的整数组成。该序列可能包含重复项(即某些元素可以相等)。
查找 $$$m$$$ 元素的元组数量,使得元组中的最大数量与最小数量相差不超过 $$$k$$$。形式上,您需要找到 $$$m$$$ 索引 $$$i_1 < i_2 < \ldots < i_m$$$ 的元组数量,这样
$$$$$$\max(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) - \min(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) \le k.$$$$$$
例如,如果 $$$n=4$$$、$$$m=3$$$、$$$k=2$$$、$$$a=[1,2,4,3]$$$,则有两个这样的三元组($$$i=1, j=2, z=4$$$ 和 $$$i=2, j=3, z=4$$$)。如果$$$n=4$$$、$$$m=2$$$、$$$k=1$$$、$$$a=[1,1,1,1]$$$,则所有六个可能的对都是合适的。
由于结果可能非常大,因此您应该打印对 $$$10^9 + 7$$$ 取模的值(除以 $$$10^9 + 7$$$ 后的余数)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 100$$$, $$$1 \le k \le n$$$) - 序列 $$$a$$$ 的长度,元组中的元素和元组中元素的最大差值。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 序列 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出给定测试用例的 $$$t$$$ 答案。每个答案都是所需的 $$$m$$$ 元素元组数以 $$$10^9 + 7$$$ 为模,这样元组中的最大值与最小值的差异不超过 $$$k$$$。
示例
输入 #1
4 4 3 2 1 2 4 3 4 2 1 1 1 1 1 1 1 1 1 10 4 3 5 6 1 3 2 9 8 1 2 4
输出 #1
2 6 1 20