题目描述

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

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

我们将从中选择 $K$ 个数，并令 $S$ 为所选择的整数集合。求所有的 $f(S)$ 之和。

由于答案可能非常大，请输出结果对 $10^9+7$ 取模后的值。

输入格式

第一行输入 $N$ $K$

第二行输入 $A_1$ $...$ $A_N$

输出格式

输出一个整数代表答案

4 2
1 1 3 4

11

6 3
10 10 10 -10 -10 -10

360

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$

样例 1 解释

有六种方法可以选择 $S$ ： $\{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\}$ 。这些选择的 $f(S)$ 值分别为 $0,2,3,2,3,1$ ，合计为 $11$ 。