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>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define ll long long
#define mid(a,b) (a+b)/2
#define pii pair<ll,ll>

using namespace std;

ll mod = 1e9+7;
ll n,k;
ll fc[N],a[N],sum;

ll big(ll a,ll b){
	if(b == 0) return 1;
	ll x = big(a,b / 2);
	if(b % 2) return (((x * x) % mod) * a) % mod;
	return (x * x) % mod;
}

ll norm(ll x){
	if(x < 0) x += mod;
	else if(x >= mod) x -= mod;
	
	return x;
}

ll C(ll n,ll k){
	return (fc[n] * big((fc[n - k] * fc[k]) % mod,mod - 2)) % mod;
}

int main()
{
	scanf("%lld%lld",&n,&k);
	fc[0] = 1;
	for(int i = 1;i <= n;i++)
		fc[i] = (fc[i - 1] * i) % mod;
	for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
	sort(a + 1,a + n + 1);
	
	for(int i = n;i >= k;i--){
		sum += ((a[i] * C(i - 1,k - 1)) % mod);
		sum %= mod;
	}
	for(int i = 1;i <= n - k + 1;i++){
		sum -= ((a[i] * C(n - i,k - 1)) % mod);
		sum = norm(sum);
	}
	printf("%lld",sum);
}