E - 最大最小和

分值：500分

问题描述

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

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

我们选择其中的$K$个数，并令$S$表示选择出的整数集合。当两个元素的值相同时，我们认为它们是不同的，因此不同位置的相同数值算作不同元素。求出所有选择的$f(S)$的和。

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

约束

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

输入

从标准输入读入数据，格式如下：

$N$ $K$

$A_1$ $...$ $A_N$

输出

输出结果对$(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

对$(10^9+7)$取模后输出结果。