E - Max-Min Sums 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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\}6 通りあり (ふたつの 1 は区別します)、f(S) はそれぞれ 0,2,3,2,3,1 となるので、合計は 11 です。


入力例 2

6 3
10 10 10 -10 -10 -10

出力例 2

360

S の選び方は 20 通りあり、そのうち 18 通りで f(S)=202 通りで 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 で出力してください。

Score : 500 points

Problem Statement

For a finite set of integers X, let f(X)=\max X - \min X.

Given are N integers A_1,...,A_N.

We will choose K of them and let S be the set of the integers chosen. If we distinguish elements with different indices even when their values are the same, there are {}_N C_K ways to make this choice. Find the sum of f(S) over all those ways.

Since the answer can be enormous, print it \bmod (10^9+7).

Constraints

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

Input

Input is given from Standard Input in the following format:

N K
A_1 ... A_N

Output

Print the answer \bmod (10^9+7).


Sample Input 1

4 2
1 1 3 4

Sample Output 1

11

There are six ways to choose S: \{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\} (we distinguish the two 1s). The value of f(S) for these choices are 0,2,3,2,3,1, respectively, for the total of 11.


Sample Input 2

6 3
10 10 10 -10 -10 -10

Sample Output 2

360

There are 20 ways to choose S. In 18 of them, f(S)=20, and in 2 of them, f(S)=0.


Sample Input 3

3 1
1 1 1

Sample Output 3

0

Sample Input 4

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

Sample Output 4

999998537

Print the sum \bmod (10^9+7).