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;

ll mod=1e9+7;
vector<ll> tfact(1e7+1,-1);
ll n,k;
ll mpow(ll x, ll n){
   ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % mod;
        x = x*x % mod;
        n = n >> 1;
    }
    return ans;
}

ll fact(ll n) {
  if(tfact[n]<0) {
    if(n==0) {
      tfact[n]=1;
    }
    else {
      tfact[n]=fact(n-1)*n%mod;
    }
  }
  return tfact[n];
}

ll comb(ll n, ll k) {
  return fact(n)*mpow(fact(k),mod-2)%mod*mpow(fact(n-k),mod-2)%mod;
}


int main() {
  cin >> n >> k;
  vector<ll> x(n);
  for(int i=0;i<n;i++) {
    cin >> x.at(i);
  }
  sort(x.rbegin(),x.rend());
  
  ll pans=0;
  ll mans=0;
  for(int i=0;i<=n-k;i++) {
    pans = (pans + x.at(i)*comb(n-1-i,k-1)%mod)%mod;
    mans = (mod+mans - x.at(n-1-i)*comb(n-1-i,k-1)%mod)%mod;
  }
  ll ans =(mod+pans+mans)%mod;
  cout << ans << endl;
}