10831: ABC151 - E - Max-Min Sums
[Creator : ]
Description
For a finite set of integers $X$, let $f(X)=\max X - \min X$.
Given are $N$ integers $A_1,...,A_N$.
We will choose $K$ of them and let $S$ be the set of the integers chosen. If we distinguish elements with different indices even when their values are the same, there are ${}_N C_K$ ways to make this choice. Find the sum of $f(S)$ over all those ways.
Since the answer can be enormous, print it $\bmod (10^9+7)$.
Given are $N$ integers $A_1,...,A_N$.
We will choose $K$ of them and let $S$ be the set of the integers chosen. If we distinguish elements with different indices even when their values are the same, there are ${}_N C_K$ ways to make this choice. Find the sum of $f(S)$ over all those ways.
Since the answer can be enormous, print it $\bmod (10^9+7)$.
Input
Input is given from Standard Input in the following format:
```
$N$ $K$
$A_1$ $...$ $A_N$
```
```
$N$ $K$
$A_1$ $...$ $A_N$
```
Output
Print the answer $\bmod (10^9+7)$.
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq K \leq N$
- $|A_i| \leq 10^9$
- $1 \leq K \leq N$
- $|A_i| \leq 10^9$
Sample 1 Input
4 2
1 1 3 4
Sample 1 Output
11
There are six ways to choose $S$: $\{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\}$ (we distinguish the two $1$s). The value of $f(S)$ for these choices are $0,2,3,2,3,1$, respectively, for the total of $11$.
Sample 2 Input
6 3
10 10 10 -10 -10 -10
Sample 2 Output
360
There are $20$ ways to choose $S$. In $18$ of them, $f(S)=20$, and in $2$ of them, $f(S)=0$.
Sample 3 Input
3 1
1 1 1
Sample 3 Output
0
10 6
1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0
999998537
Print the sum $\bmod (10^9+7)$.