题目描述

有限個の整数からなる集合 $X$ に対し $f(X)=\max\ X\ -\ \min\ X$ と定義します。

$N$ 個の整数 $A_1,...,A_N$ が与えられます。

このうち $K$ 個を選び、それらからなる集合を $S$ とします。同じ値であっても添字が異なる要素を区別すると、そのような選び方は ${}_N\ C_K$ 通りありますが、その全てについての $f(S)$ の合計を求めてください。

答えは非常に大きくなる可能性があるので、$\bmod\ 10^9+7$ で出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを $\bmod\ 10^9+7$ で出力せよ。

题目大意

给你一个整数集合 $A$ , $|A|=n$ 和一个数 $k$

求 $\sum\limits_{S\in A}[|S|=k]f(S)$ ，取模 $1000000007$

其中$f(S)=\max\limits_{x\in S}x-\min\limits_{x\in S}x$

$1\le k\le n\le100000,\forall x\in A,|x|\le1000000000$

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$

Sample Explanation 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$ です。

Sample Explanation 2

$S$ の選び方は $20$ 通りあり、そのうち $18$ 通りで $f(S)=20$、$2$ 通りで $f(S)=0$ となります。

Sample Explanation 4

合計は $\bmod\ 10^9+7$ で出力してください。