题目描述

对于一个有限整数集合$X$，定义$f(X)=\max\ X\ -\ \min\ X$ 。

给定$N$个整数$A_1,…,A_N$。

我们选择其中的$K$个数，并令$S$表示选择出的整数集合。

当两个元素的值相同时，我们认为它们是不同的，因此不同位置的相同数值算作不同元素。

求出所有选择的$f(S)$的和。

由于答案可能很大，输出结果需要对$(10^9+ 7)$取模。

输入

第一行两个整数$N,K$

第二行一共$N$个整数，表示序列$A$

输出

结果对$(10^9+ 7)$取模

4 2
1 1 3 4

11

样例解释

有六种选择$S$的方式 $\{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\},\{3,4\}$ 我们注意到两个$1$是不同的）。这些选择下，$f(S)$的值分别是 $0,2,3,2,3,1$ 总和 $11$ 。

6 3
10 10 10 -10 -10 -10

360

样例解释

有20种选择$S$的方式。其中18种情况下，$f(S)=20$，另外2种情况下，$f(S)=0$.

3 1
1 1 1

0

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

999998537

提示

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