AT_abc151_e [ABC151E] Max-Min Sums

题目描述

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

给定 $N$ 个整数 $A_1, \ldots, A_N$。

从中选择 $K$ 个数，组成集合 $S$。即使数值相同，只要下标不同也视为不同元素。这样的选择方式共有 $\binom{N}{K}$ 种。请计算所有可能的 $S$ 的 $f(S)$ 之和。

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

输入格式

输入以如下格式从标准输入给出。

$N$ $K$ $A_1$ $...$ $A_N$

输出格式

请输出答案对 $10^9+7$ 取模后的结果。

样例 1

输入

4 2
1 1 3 4

输出

11

样例 2

输入

6 3
10 10 10 -10 -10 -10

输出

360

样例 3

输入

3 1
1 1 1

输出

0

样例 4

输入

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\}$ 共 $6$ 种（两个 $1$ 视为不同），每种 $f(S)$ 分别为 $0,2,3,2,3,1$，所以总和为 $11$。

样例解释 2

$S$ 的选法有 $20$ 种，其中 $18$ 种 $f(S)=20$，$2$ 种 $f(S)=0$。

样例解释 4

请输出答案对 $10^9+7$ 取模后的结果。

由 ChatGPT 4.1 翻译