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 <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll n, k;
ll a[100009], fact[100009],inv[100009], mod = (ll)1e9+7;
ll fp(ll b, ll p)
{
	if (p == 0)
		return 1;
	ll ans = fp(b, p / 2);
	ans = (ans * ans) % mod;
	if (p % 2)
		ans = (ans * (b % mod)) % mod;
	return ans;
}
void pre()
{
	ll e = 100005;
	fact[0] = inv[0] = 1;
	for (ll i = 1; i <= e; i++)
	{
		fact[i] = (i * fact[i - 1]) % mod;
		inv[i] = fp(fact[i], mod - 2);
	}
}
ll ncr(ll n, ll r)
{
	return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
ll mx[100009], mn[100009];
int main()
{
	pre();
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		if (i >= k - 1)
			mx[i] = (a[i] * ncr(i, k - 1)) % mod;
		if (n - i - 1 >= k - 1 && n - i > 0)
			mn[i] = (a[i] * ncr(n - i - 1, k - 1)) % mod;
	}
	for (ll i = 0; i < n; i++)
		sum += mx[i] - mn[i];
	cout << sum % mod;
}