B'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}) <= 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 ). The first line contains a single integer t ( 1 <= t <= 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 <= n <= 2 cdot 10^5 , 1 <= m <= 100 , 1 <= k <= 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 <= a_i <= 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 .'...