Close Tuples (hard version)

题意翻译

给定 $t$ 个长为 $n$ 的数组 $a$，取元素个数为 $m$ 的 $a$ 的子序列 $b$ 满足 $\max(b_i) - \min(b_i) \leqslant k$ ，问最多能找出多少组，并取模 ${10}^9 + 7$。

题目描述

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 < i_2 < \ldots < 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. $ $ </p><p>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.</p><p><span class="tex-font-style-bf">As the result can be very large, you should print the value modulo $ 10^9 + 7 $ (the remainder when divided by $ 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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #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