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).

Examples

Input

4 2
1 1 3 4


Output

11


Input

6 3
10 10 10 -10 -10 -10


Output

360


Input

3 1
1 1 1


Output

0


Input

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


Output

999998537
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int nMax=1e5, MOD=1e9+7;
LL inv[nMax], Fact[nMax], invF[nMax];
LL Comb(int n, int r){ return (((Fact[n]*invF[r])%MOD)*invF[n-r])%MOD; }

int main(){
inv[1]=Fact[0]=Fact[1]=invF[0]=invF[1]=1;
for(int i=2; i<nMax; i++){ 
  inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
  Fact[i]=(Fact[i-1]*i)%MOD; invF[i]=(invF[i-1]*inv[i])%MOD;
}
int N, K; LL M=0, m=0; cin >> N >> K; vector<LL> A(N);
for(int i=0; i<N; i++){ cin >> A[i]; } sort(A.begin(), A.end());
  
for(int i=0; i<N; i++){
if(K<=i+1){ M=(M+(Comb(i, K-1)*((A[i]+MOD)%MOD))%MOD)%MOD; }
if(K<=N-i){ m=(m+(Comb(N-i-1, K-1)*((A[i]+MOD)%MOD))%MOD)%MOD; }
}
cout << ((M-m)+MOD)%MOD << "\n"; 
}