← 返回题目列表

AtCoder · abc151_e

E. 最大-最小总和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

对于有限整数集 X,让 f(X)=\max X - \min X.

给出的是 N 整数 A_1,...,A_N.

我们会选择 K 其中并让 S 是所选整数的集合。如果我们区分具有不同索引的元素,即使它们的值相同,也有 {}_N C_K 做出这种选择的方法。求总和 f(S) 超越所有这些方式。

由于答案可能很大,请将其打印出来 \bmod (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

输出

打印答案 \bmod (10^9+7).


示例输入 1

4 2
1 1 3 4

示例输出 1

11

有六种方式可供选择 S: \{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\} (我们区分两者 1s)。的价值 f(S) 这些选择是 0,2,3,2,3,1分别为总计 11.


示例输入 2

6 3
10 10 10 -10 -10 -10

示例输出 2

360

有 20 选择方式 S。在 18 其中, f(S)=20,并在 2 其中, f(S)=0.


示例输入 3

3 1
1 1 1

示例输出 3

0

示例输入 4

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

示例输出 4

999998537

打印总和 \bmod (10^9+7).