**Choose and Calculate

Choose and Calculate 

Animesh and Mohit are playing a game. They have  balls in front of them. All the balls are numbered, not necessarily in any order. Animesh picks a set of  balls from the lot each time, checks this set, puts it back into the lot, and repeats this process until all possible selections have been made. At each draw, Mohit picks two balls from these  balls -- the one with the maximum number and the one with the minimum number, and notes their difference on a paper. At the end of the game, Animesh has to tell the  of all the numbers on Mohit's paper. As value of this number can be very huge, you have to tell the value mod .

Input Format 
The first line contains two integers  and . 
The next line will contain a list having  numbers.

Output Format 
Print the value of  mod .

Constraints 
 
 

Sample Input

4 2
10 20 30 40

Sample Output

100

Explanation

There are 6 possible selections. 
1. 10 20 
2. 20 30 
3. 30 40 
4. 10 30 
5. 20 40 
6. 10 40 
Summation = 10+10+10+20+20+30 = 100

=====================editorial=================================

There are  selections of  balls from our set of  balls. For each selection, we need to calculate the difference between the maximum and minimum, and get the total for all selections.

Notice that we can add the maximums and minimums separately, and take the difference of the two as the final answer.

For the calculation of the sum of the maximum of each selection, we use simple mathematics. First, sort the given array .

It can be easily checked that  () will be the maximum in  selections, because there are  ways to select the  other numbers in the selection, out of the  items less than it. Therefore, the contribution of  to the total sum of maximums is . So, we can calculate the summation of the maximums as the sum of each  for all indices .

Similarly,  will be the minimum in  selections, because there are  ways to select the  other numbers in the selection, out of the  items greater than it. Therefore, the summation of the minimums is the sum of each  for all indices .

The difference between the summation of the maximums and minimums is the final answer. Written as a formula, it is:

which is the same as

Calculating binomial coefficients modulo 

In the answer, we need to calculate  efficiently.

This can be done using modular arithmetic. You may refer to this link.

Alternatively, you can simply use the factorial formula for the binomial coefficient: 

We need to calculate this modulo . Since in the problem we will only need binomial coefficients with  and , you can simply precalculate the factorials and inverse factorials modulo .

=======================code===============================

#include<bits/stdc++.h>

#define mode 1000000007

typedef long long int lli;

using namespace std;

long long int fs[10000000];

long long int arr[10000000];

long long int  fact[10000000];

long long int ifact[10000000];

lli comb(lli n,lli r)

 {

  //cout<<n<<" "<<r<<endl;

   if(n<r)return 0;

   if(n==0 ||r==0) return 1;

  lli a=fact[n];

  lli b=ifact[r];

  lli c=ifact[n-r];

  // cout<<" return "<<(a*((b*c)%mode))%mode<<endl;

  return (a*((b*c)%mode))%mode;

 }

lli fast_pow(lli base, lli n)

{

       if(n==0)

       return 1;

    if(n==1)

    return base;

    lli halfn=fast_pow(base,n/2);

    lli ret;

    if(n%2==0)

       {

        ret=(1ll*halfn*halfn) % mode;

        while(ret<0) ret+=mode;

  }

    else

        {

        ret=(1ll*halfn*halfn) % mode;

            while(ret<0) ret+=mode;

            ret=(1ll*ret*base)%mode;

            while(ret<0) ret+=mode;

}

return ret;

}

int main()

 {

     int n,k;

     cin>>n>>k;

     fact[0]=1;

     for(int i=1;i<=n;i++)

      {

        fact[i]=(fact[i-1]*i+mode) %mode;

      //  cout<<i<<fact[i]<<endl;

 }

 for(int i=0;i<=n;i++)

  {

  ifact[i]=fast_pow(fact[i],mode-2);

 // cout<<i<<ifact[i]<<endl;

  }

    for(int i=1;i<=n;i++)

         {

         cin>>arr[i];

    }

    

    sort(arr+1,arr+n+1);

    long long int ans=0;

    long long int ad=0;

     long long int sb=0;

    for(int i=1;i<=n;i++)

     {

     

       ad=(ad+(arr[i]*comb(i-1,k-1))%mode)%mode;

       sb=(sb+(arr[i]*comb(n-i,k-1))%mode)%mode;

}

    ans=(ad-sb+mode)%mode;

    while(ans<0) ans+=mode;

    cout<<ans<<endl;

}