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;
#define MOD 1000000007


const int MAX = 200010;
vector<long long> fac(MAX,1),finv(MAX,1),inv(MAX,1);

void init() {
  for(int i = 2;i < MAX;i++) {
    fac.at(i) = fac.at(i-1) * i % MOD;
    inv.at(i) = MOD - inv.at(MOD%i) * (MOD/i) % MOD;
    finv.at(i) = finv.at(i-1) * inv.at(i) % MOD;
  }
}


long long comb(int n,int k) {
    if(n < k || n < 0 || k < 0) return 0;
    return fac.at(n)*(finv.at(k)*finv.at(n-k)%MOD)%MOD;
}

int main() {

  int N,K;
  cin >> N >> K;

  vector<long long> A(N);
  for(int i = 0;i < N;i++) cin >> A.at(i);

  sort(A.begin(),A.end());
  init();
  
  long long M = 0,m = 0;
  for(int i = 0;i < N;i++) {
    M += (comb(i,K-1)*A.at(i))%MOD;
    m += (comb(N-i-1,K-1)*A.at(i))%MOD;
    M %= MOD;
    m %= MOD;
  }

  

  cout << (M+MOD-m)%MOD << endl;
}
