Home

Problem Statement

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

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $|A_i| \leq 10^9$

Sample Input 1

4 2
1 1 3 4

Sample Output 1

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

6 3
10 10 10 -10 -10 -10

Sample Output 2

360

There are $20$ ways to choose $S$. In $18$ of them, $f(S)=20$, and in $2$ of them, $f(S)=0$.

Sample Input 3

3 1
1 1 1

Sample Output 3

0

Sample Input 4

10 6
1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0

Sample Output 4

999998537

Print the sum $\bmod (10^9+7)$.