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

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


-----Input-----

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

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


-----Examples-----

Input
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
Output
2
6
1
20


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Sorting

Combinatorics

Amortized analysis

Implementation

Mathematics
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
MOD = 10 ** 9 + 7
N = 200001
fact = [1]
for i in range(1, N + 1):
	fact.append(fact[-1] * i % MOD)

def nCr(n, r):
	if n <= r:
		return n == r
	a = fact[n]
	b = fact[n - r] * fact[r] % MOD
	b = pow(b, MOD - 2, MOD)
	return a * b % MOD
import math
import bisect
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	ans = 0
	sequence = list(map(int, input().split()))
	if sequence.count(sequence[0]) == len(sequence):
		print(math.comb(len(sequence), m) % MOD)
	else:
		sequence.sort()
		for j in range(n - m + 1):
			last = bisect.bisect_right(sequence, sequence[j] + k)
			ans += nCr(last - j - 1, m - 1)
		print(ans % MOD)


import sys
from bisect import bisect_right
r = sys.stdin.readline
MOD = 10 ** 9 + 7
N = 200001
fact = [1]
for i in range(1, N + 1):
	fact.append(fact[-1] * i % MOD)

def nCr(n, r):
	if n <= r:
		return n == r
	a = fact[n]
	b = fact[n - r] * fact[r] % MOD
	b = pow(b, MOD - 2, MOD)
	return a * b % MOD
for _ in range(int(r())):
	(n, m, k) = map(int, r().split())
	seq = list(map(int, r().split()))
	seq.sort()
	ans = 0
	for i in range(n - m + 1):
		j = bisect_right(seq, seq[i] + k, lo=i + 1)
		idx = j - i - 1
		ans += nCr(idx, m - 1)
		ans %= MOD
	print(ans)


import sys
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
fact = [1]
for i in range(1, 2 * 10 ** 5 + 1):
	fact += [fact[-1] * i % mod]
for _ in range(I()):
	(n, m, k) = neo()
	A = Neo()
	A.sort()
	Ans = 0
	m -= 1
	for i in range(n):
		t = bisect.bisect_right(A, A[i] + k) - i - 1
		if t >= m:
			Ans += fact[t] * pow(fact[t - m] * fact[m] % mod, mod - 2, mod)
			Ans = Ans % mod
	print(Ans)


import sys
input = sys.stdin.readline
mod = MOD = 10 ** 9 + 7
M = 3 * 10 ** 5
fac = [1] * M
for i in range(1, M):
	fac[i] = fac[i - 1] * i % MOD

def printNcR(n, r):
	if n < r:
		return 0
	a = fac[n]
	b = fac[n - r] * fac[r] % MOD
	b = pow(b, MOD - 2, MOD)
	return a * b % MOD
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	lis = sorted(map(int, input().split()))
	i = j = ans = 0
	while i < n:
		if lis[j] - lis[i] <= k:
			j += 1
		else:
			ans = (printNcR(j - i - 1, m - 1) + ans) % mod
			i += 1
		if j == n:
			break
	while i < n:
		ans = (printNcR(j - i - 1, m - 1) + ans) % mod
		i += 1
	print(ans)


t = int(input())
MOD = 10 ** 9 + 7
lazyfac = [1, 1]
inversfac = [1, 1]

def upfac(lazyfac, inversefac, n):
	while len(lazyfac) < n + 1:
		lazyfac.append(lazyfac[-1] * len(lazyfac) % MOD)
		inversfac.append(pow(lazyfac[-1], -1, MOD))

def choose(n, m):
	return lazyfac[n] * inversfac[n - m] * inversfac[m]
for test in range(t):
	(n, m, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	upfac(lazyfac, inversfac, n + 20)
	ans = 0
	j = 0
	if m == 1:
		ans = n
	else:
		for i in range(n - m + 1):
			if j < n:
				while a[j] <= a[i] + k:
					j += 1
					if j == n:
						break
			if j >= i + m:
				ans += choose(j - i - 1, m - 1)
				ans = ans % MOD
	print(ans)


import bisect
import sys
input = sys.stdin.readline
m = 1000000007
ft = [1] * 200006
for i in range(1, 200006):
	ft[i] = i * ft[i - 1] % m

def cb(a, b):
	if b > a:
		return 0
	x = ft[b] * ft[a - b]
	x = pow(x, m - 2, m) % m
	x = ft[a] * x
	x = x % m
	return x
for _ in range(int(input())):
	(n, j, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	for i in range(n):
		y = arr[i] + k
		id = bisect.bisect(arr, y)
		ans += cb(id - i - 1, j - 1)
		ans = ans % m
	print(ans)


import math
T = int(input())
r = 1

def decrease(m, n, pre):
	pre = pre * (m - n)
	pre = pre // m
	return pre

def increase(m, n, pre):
	pre = pre * (m + 1)
	pre = pre // (m - n + 1)
	return pre
while r <= T:
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	arr = sorted(arr)
	temp = 1
	front = -1
	for i in range(n):
		while arr[i] - arr[front + 1] > k:
			if i - 1 - front > m:
				temp = decrease(i - front - 2, m - 1, temp)
			elif i - 1 - front == m:
				temp = 1
			front += 1
		if i - front > m:
			temp = increase(i - front - 2, m - 1, temp)
		if i - front >= m:
			ans += temp % (10 ** 9 + 7)
		ans = ans % (10 ** 9 + 7)
	print(ans)
	r += 1


t = int(input())
for tc in range(t):
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	k = int(l[2])
	v = input().split()
	for i in range(n):
		v[i] = int(v[i])
	v.sort()
	if n < m:
		print(0)
	else:
		comb = []
		for i in range(n):
			comb.append(1)
		for i in range(m, n):
			comb[i] = comb[i - 1] * i // (i - m + 1)
		j = m - 1
		su = 0
		for i in range(0, n - m + 1):
			while j < n and v[j] - v[i] <= k:
				j = j + 1
			if j - i >= m:
				su = (su + comb[j - i - 1]) % 1000000007
		print(su)


import sys
input = sys.stdin.readline
mod_ = 10 ** 9 + 7
factos = [1]
inv_factos = []
for elem in range(1, 2 * 10 ** 5 + 1):
	factos.append(factos[-1] * elem % mod_)
for val in factos:
	inv_factos.append(pow(val, mod_ - 2, mod_))

def solution(n, m, k, arr):
	left = 0
	right = 0
	sol = 0
	arr.sort()

	def c_C_r(c, r):
		if c < r:
			return 0
		return factos[c] * inv_factos[r] * inv_factos[c - r] % mod_
	while left < n:
		while right <= n - 1 and arr[left] + k >= arr[right]:
			right += 1
		sol = (sol + c_C_r(right - left - 1, m - 1)) % mod_
		left += 1
	print(sol)
T = int(input())
for t in range(T):
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	solution(n, m, k, arr)


mod = 1000000007
fact = [1]

def inv(a):
	return pow(a, mod - 2, mod)

def C(n, k):
	if k > n:
		return 0
	return fact[n] * inv(fact[k] * fact[n - k] % mod) % mod

def fac(n, p):
	for i in range(p, n + 1):
		fact.append(fact[i - 1] * i % mod)
		p = p + 1
	return p

def initialize(n, p):
	if n > p:
		return fac(n, p)
	else:
		return p
t = int(input())
p = 1
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = initialize(n, p)
	a.sort()
	l = 0
	s = 0
	for j in range(n):
		while a[j] - a[l] > k and l <= j:
			l = l + 1
		s = (s + C(j - l, m - 1)) % mod
	print(s)


from bisect import bisect
mod = 10 ** 9 + 7

def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] * g2[n - r] % mod
N = 5 * 10 ** 5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, N + 1):
	g1.append(g1[-1] * i % mod)
	inverse.append(-inverse[mod % i] * (mod // i) % mod)
	g2.append(g2[-1] * inverse[-1] % mod)
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for i in range(n):
		b = bisect(a, a[i] + k)
		ans += cmb(b - i - 1, m - 1, mod)
		ans %= mod
	print(ans)


delta = 10 ** 9 + 7
factorial = [1] * 200001
inverse = [1] * 200001
for i in range(1, 200001):
	factorial[i] = factorial[i - 1] * i % delta
	inverse[i] = pow(factorial[i], delta - 2, delta)
t = int(input())
flag = True
for _ in range(t):
	(n, m, k) = tuple(map(int, input().split()))
	if n < m:
		input()
		print(0)
		continue
	if m == 1:
		input()
		print(n)
		continue
	sequence = list(map(int, input().split()))
	sequence.sort()
	j = 1
	ans = 0
	for i in range(n):
		while j < n and sequence[j] - sequence[i] <= k:
			j += 1
		ans += 0 if j - i < m else factorial[j - i - 1] * inverse[m - 1] * inverse[j - i - m] % delta
	print(ans % delta)


mod = pow(10, 9) + 7
fact = [1]
for i in range(1, 200001):
	fact.append(fact[i - 1] * i % mod)

def modinv(a, m):
	return pow(a, m - 2, m)

def c(n, r):
	return fact[n] * modinv(fact[n - r] * fact[r] % mod, mod) % mod

def find(a, low, k, m):
	ele = a[low]
	j = low
	high = len(a) - 1
	(pl, ph) = (low, high)
	while low < high:
		mid = (low + high) // 2
		if a[mid] - ele <= k:
			low = mid
		else:
			high = mid - 1
		if pl == low and ph == high:
			break
		(pl, ph) = (low, high)
	if a[high] - ele <= k:
		low = high
	if low - j >= m - 1:
		return c(low - j, m - 1)
	else:
		return 0
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	for i in range(n - m + 1):
		res += find(a, i, k, m)
		res %= mod
	print(res)


import sys
M = 10 ** 9 + 7
a = [1]
for i in range(1, 8 ** 6):
	a += (a[-1] * i % M,)
R = lambda : map(int, sys.stdin.readline().split())
f = lambda x: x >= m and a[x] * pow(a[x - m], M - 2, M)
(t,) = R()
for _ in [0] * t:
	(n, m, k) = R()
	c = [0] * n
	for x in R():
		c[x - 1] += 1
	for i in range(n - 1):
		c[i + 1] += c[i]
	print(sum((f(z - x) - f(y - x) for (x, y, z) in zip([0] + [0] * k + c, [0] + c, c))) * pow(a[m], M - 2, M) % M)


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
M = 3 * 10 ** 5
fac = [1] * M
for i in range(1, M):
	fac[i] = fac[i - 1] * i % MOD

def nCk(n, k):
	if n < k:
		return 0
	return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD

def solve():
	(n, m, k) = I()
	a = I()
	a.sort()
	ans = 0
	(i, j) = (m - 1, 0)
	while i < n:
		while j < i and a[i] - a[j] > k:
			j += 1
		length = i - j
		ans += nCk(length, m - 1)
		ans %= MOD
		i += 1
	print(ans)
(t,) = I()
while t:
	t -= 1
	solve()


MOD = 10 ** 9 + 7
M = 3 * 10 ** 5
fac = [1] * M
for i in range(1, M):
	fac[i] = fac[i - 1] * i % MOD

def nCk(n, k):
	if n < k:
		return 0
	return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD
t = int(input())
while t:
	t -= 1
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	(i, j) = (m - 1, 0)
	while i < n:
		while j < i and a[i] - a[j] > k:
			j += 1
		length = i - j
		ans += nCk(length, m - 1)
		ans %= MOD
		i += 1
	print(ans)


def modInverse(a, m):
	assert m > 0, 'Error'
	(x, y) = (1, 0)
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		(x, y) = (y, x - q * y)
		(a, m) = (m, a % m)
	return x

def C(n, r, fact, inv, mod):
	if r > n or r < 0:
		return 0
	res = fact[n] * inv[r] % mod
	res = res * inv[n - r] % mod
	return res
M = 10 ** 9 + 7
(fact, inv) = ([1], [1])
for i in range(200007):
	fact.append(fact[-1] * (i + 1) % M)
	inv.append((modInverse(fact[-1], M) + M) % M)
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n < m:
		print(0)
		continue
	a.sort()
	(p1, p2, tot) = (0, m - 1, 0)
	while p1 < n - m + 1:
		while p2 < n and a[p2] - a[p1] <= k:
			p2 += 1
		dif = p2 - p1 - 1
		tot += C(dif, m - 1, fact, inv, M)
		tot %= M
		p1 += 1
	print(tot)


import sys, math, heapq, queue
from collections import deque
from functools import cmp_to_key
fast_input = sys.stdin.readline
MOD = 10 ** 9 + 7
for _ in range(int(fast_input())):
	(n, m, k) = map(int, fast_input().split())
	a = sorted(list(map(int, fast_input().split())))
	high = 0
	ans = 0
	fact = [1] * (n + 1)
	for i in range(1, n + 1):
		fact[i] = i * fact[i - 1] % MOD

	def calc(t, c):
		res = fact[t] * pow(fact[c], MOD - 2, MOD) % MOD
		return res * pow(fact[t - c], MOD - 2, MOD) % MOD
	for i in range(n):
		while high < n and a[high] - a[i] <= k:
			high += 1
		if high - i >= m:
			ans = (ans + calc(high - i - 1, m - 1)) % MOD
	print(ans)


import bisect
n = 200005
MOD = 10 ** 9 + 7
fact = [1] * (n + 1)
for i in range(1, n + 1):
	fact[i] = i * fact[i - 1] % MOD

def calc(t, c):
	res = fact[t] * pow(fact[c], MOD - 2, MOD) % MOD
	return res * pow(fact[t - c], MOD - 2, MOD) % MOD
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for i in range(n):
		now = a[i] + k
		val = bisect.bisect_right(a, now)
		val -= i
		if val >= m:
			ans = (calc(val - 1, m - 1) + ans) % 1000000007
	print(ans)


mod = 1000000007
num = 3 * 10 ** 5
fact = [1] * num
for i in range(1, num):
	fact[i] = fact[i - 1] * i % mod

def choose(n, k):
	if n >= k:
		return fact[n] * pow(fact[n - k], mod - 2, mod) * pow(fact[k], mod - 2, mod) % mod
	return 0
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis = sorted(lis)
	ans = 0
	(i, j) = (m - 1, 0)
	while i < n:
		while j < i and lis[i] - lis[j] > k:
			j += 1
		ans += choose(i - j, m - 1)
		ans %= mod
		i += 1
	print(ans)


def modulo(n, prime, dp1):
	dp1[0] = dp1[1] = 1
	for j in range(2, n + 1):
		dp1[j] = dp1[j - 1] * j % prime
t = int(input())
for i in range(t):
	(n, m, p) = map(int, input().split())
	mod1 = int(1000000000.0 + 7)
	a = list(map(int, input().split()))
	a.sort()
	val = 0
	j = 0
	k = 0
	dp1 = [0] * (n + 1)
	modulo(n, mod1, dp1)
	while j < n:
		while j + k < n and a[j + k] - a[j] <= p:
			k += 1
		if k >= m:
			val = (val + dp1[k - 1] * (pow(dp1[m - 1], mod1 - 2, mod1) * pow(dp1[k - 1 - (m - 1)], mod1 - 2, mod1)) % mod1 % mod1) % mod1
		k -= 1
		j += 1
	print(val)


R = lambda : map(int, input().split())
mod = 10 ** 9 + 7
fac = [1] * (2 * 10 ** 5 + 7)
for i in range(2, len(fac)):
	fac[i] = fac[i - 1] * i % mod

def cnk(nn, kk):
	return fac[nn] * pow(fac[nn - kk], mod - 2, mod) * pow(fac[kk], mod - 2, mod) % mod
for _ in range(int(input())):
	(n, m, k) = R()
	arr = sorted(R())
	i = 0
	nck = [1] * (n + 1)
	for j in range(m, n + 1):
		nck[j] = nck[j - 1] * j // (j - m + 1) % mod
	res = 0
	for j in range(m - 1, n):
		while i < j and arr[j] - arr[i] > k:
			i += 1
		if j - i + 1 >= m:
			res = (res + cnk(j - i, m - 1)) % mod
	print(res)


M = 3 * 10 ** 5
fac = [1] * M
MOD = 1000000007
for i in range(1, M):
	fac[i] = fac[i - 1] * i % MOD

def nCk(n, k):
	if n < k:
		return 0
	return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD
t = int(input())
while t:
	t -= 1
	(n, m, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	c = 0
	j = 0
	i = 0
	while i < n:
		if j < n and arr[i] - arr[j] <= k:
			j += 1
		else:
			if j - i > m - 1:
				c = (c + nCk(j - i - 1, m - 1)) % MOD
			i += 1
	print(c)