H. Array Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdelaleem (aka Yousef) has an array $$$a$$$ consisting of $$$n$$$ integers, which he will give to Yousef (aka Abdelaleem). Yousef's task is to select a subsequence $$$S$$$ of exactly $$$k$$$ elements from this array.

Define the function $$$f(S)$$$ as the difference between the maximum and minimum elements in the subsequence $$$S$$$: $$$f(S) = \text{max}(S) - \text{min}(S)$$$.

What is the expected value of $$$f(S)$$$ over all possible subsequences $$$S$$$ of size $$$k$$$ that Yousef may select?

A subsequence of a sequence $$$a$$$ is a sequence that can be derived from $$$a$$$ by deleting some (or none) of the elements without changing the order of the remaining elements. Formally, given a sequence $$$a$$$ of length $$$n$$$, a subsequence of $$$a$$$ can be represented as $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$, where $$$1 \leq i_1 \lt i_2 \lt ... \lt i_k \leq n$$$.

Input

The first line contains an integer $$$T$$$ – the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ $$$( 1 \leq k \leq n \leq 5 * 10^5 )$$$, the size of the array, and the size of subsequences to select, respectively.

The second line contains $$$n$$$ integers $$$ a_1, a_2, \dots, a_n $$$ $$$( -10^9 \leq a_i \leq 10^9 )$$$, the elements of array $$$a$$$.

Output

For each test case, output one line containing the expected value of $$$f(S)$$$ over all possible subsequences $$$S$$$ of size $$$k$$$ that Yousef may select – module $$$(10^9+7)$$$.

Formally, let $$$M = 10^9 +7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0(mod M)$$$. Output the integer equal to $$$p$$$ $$$*$$$ $$$q^{-1} (mod M)$$$ . In other words, output such an integer $$$x$$$ that $$$0 \leq x \lt M$$$ and $$$x*q \equiv p(modM)$$$.

Example
Input
5
4 2
4 1 3 1
3 1
1 1 1
6 3
-10 -10 10 10 10 -10
4 4
4 2 1 3
3 2
-1 0 1
Output
833333341
0
18
3
333333337