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 ;
const int maxn = 1e5 + 5 ;
const ll mod = 1e9 + 7 ;
int n , k ;
ll a[maxn] ;
ll f[maxn] ;
void init()
{
	f[0] = 1 ;
	for(int i = 1 ; i <= 1e5 ; i ++)
	  f[i] = f[i - 1] * ll(i) % mod ;
}
ll qpow(ll a , ll b)
{
    ll ans = 1 ; 
    while(b)
    {
        if(b & 1)
          ans = (ans * a) % mod ;
        b >>= 1 ;
        a = (a * a) % mod ;
    }
    return ans % mod ;
}
ll solve(ll x)
{
	return qpow(x , mod - 2) % mod ; //qpow�ǿ����ݡ�
}
ll C(ll x , ll y)
{
	if(x < y)  return 0 ;
	if(x == y)  return 1 ;
	return f[x] * solve(f[y] * f[x - y] % mod) % mod ;
}
int main()
{
	init() ;
	scanf("%d%d" , &n , &k) ;
	for(int i = 1 ; i <= n ; i ++)
	  scanf("%lld" , &a[i]) ;
	sort(a + 1 , a + n + 1) ;
	ll ans = 0 ;
	for(int i = 1 ; i <= n ; i ++)
	  ans += (C(i - 1 , k - 1) - C(n - i , k - 1)) * a[i] % mod , ans %= mod ;
	printf("%lld\n" , ans) ;
	return 0 ;
}
