/ 
Time Limit: 2 sec / Memory Limit: 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)=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 で出力してください。
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).