Score : $500$ points

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$

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $...$ $A_N$

Output

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

4 2
1 1 3 4

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

6 3
10 10 10 -10 -10 -10

360

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

3 1
1 1 1

0

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

999998537

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