最大最小之和

题目描述

对于由有限个整数组成的集合 $X$,定义 $f(X)=\max X - \min X$。

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

从中选出 $K$ 个,将它们组成的集合记为 $S$。即使值相同,只要下标不同就视为不同的元素,这样的选法共有 ${}_N C_K$ 种,请计算所有这些选法的 $f(S)$ 的总和。

答案可能非常大,请输出对 $10^9+7$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

$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\}$ 这 $6$ 种(两个 $1$ 视为不同元素),对应的 $f(S)$ 分别为 $0,2,3,2,3,1$,总和为 $11$。

6 3
10 10 10 -10 -10 -10

360

$S$ 的选法共有 $20$ 种,其中 $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$ 取模的结果。

数据范围

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