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;
const int M = 1e9+7;

long long pwr( long long a , long long b , long long m = M ){
	
	long long ret = 1;
	a %= m , b %= m;

	while( b>0 ){
		if(b&1)	ret = ret*a % m;
		a = a*a % m;
		b >>= 1;
	}

	return ret;
}

int main(){

	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

 	int n,k;
 	cin>>n>>k;

 	vector<int> a(n);
 	for(int i=0 ; i<n ; ++i)
 		cin>>a[i];

 	sort(a.begin(),a.end());
 	long long cur=1 , mx=0 , mn=0;

 	for(auto &i : a)
 		i = (i+M)%M;

 	for(int i=k-1 ; i<a.size() ; ++i){
 		mx = ( mx + cur*a[i] ) % M;
 		cur = cur * (i+1) % M;
 		cur = cur * pwr(i-k+2,M-2) % M;
 	}
 	// cout<<mx<<endl;

 	cur = 1;
 	for(int i=n-k ; i>=0 ; --i){
 		mn = ( mn + cur*a[i] ) % M;
 		cur = cur * (n-i) % M;
 		cur = cur * pwr(n-i-k+1,M-2) % M;
 	}

	// cout<<mn<<endl;
 	mx = ( mx - mn ) % M;
 	cout<< ( mx + M ) % M ;
 }



