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$$$.
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$$$.
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)$$$.
54 24 1 3 13 11 1 16 3-10 -10 10 10 10 -104 44 2 1 33 2-1 0 1
833333341 0 18 3 333333337
