CF1462E2.Close Tuples (hard version)

This is the hard version of this problem. The only difference between the easy and hard versions is the constraints on $k$ and $m$. In this version of the problem, you need to output the answer by modulo $10^9+7$.

You are given a sequence $a$ of length $n$ consisting of integers from $1$ to $n$. The sequence may contain duplicates (i.e. some elements can be equal).

Find the number of tuples of $m$ elements such that the maximum number in the tuple differs from the minimum by no more than $k$. Formally, you need to find the number of tuples of $m$ indices $i_1 \lt i_2 \lt \ldots \lt i_m$, such that

$$\\max(a\_{i\_1}, a\_{i\_2}, \\ldots, a\_{i\_m}) - \\min(a\_{i\_1}, a\_{i\_2}, \\ldots, a\_{i\_m}) \\le k.$$

For example, if $n=4$, $m=3$, $k=2$, $a=[1,2,4,3]$, then there are two such triples ($i=1, j=2, z=4$ and $i=2, j=3, z=4$). If $n=4$, $m=2$, $k=1$, $a=[1,1,1,1]$, then all six possible pairs are suitable.

As the result can be very large, you should print the value modulo $10^9 + 7$ (the remainder when divided by $10^9 + 7$).

这是本题的困难版本。简单版本与困难版本的唯一区别在于对 $k$ 和 $m$ 的约束条件不同。在本版本中，你需要将答案对 $10^9+7$ 取模后输出。

给定一个长度为 $n$ 的整数序列 $a$，其中每个元素均为 $1$ 到 $n$ 之间的整数（序列中可能包含重复元素，即某些元素可能相等）。

请你计算满足以下条件的 $m$ 元组的个数：该元组中最大值与最小值之差不超过 $k$。形式化地说，你需要计算满足如下条件的 $m$ 个下标 $i_1 \lt i_2 \lt \ldots \lt 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$ 后的余数）。

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains three integers $n$, $m$, $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 100$, $1 \le k \le n$) — the length of the sequence $a$, number of elements in the tuples and the maximum difference of elements in the tuple.

The next line contains $n$ integers $a_1, a_2,\ldots, a_n$ ($1 \le a_i \le n$) — the sequence $a$.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Output $t$ answers to the given test cases. Each answer is the required number of tuples of $m$ elements modulo $10^9 + 7$, such that the maximum value in the tuple differs from the minimum by no more than $k$.

输出 $t$ 个测试用例的答案。每个答案为满足条件的、由 $m$ 个元素组成的元组的个数（对 $10^9 + 7$ 取模），其中元组中最大值与最小值之差不超过 $k$。