Concepts: Number Theory + Combinatorics
IntuitionNumber Theory + CombinatoricsApproachWe need to focus on minimum and maximum elements only. Ask yourself how many times minimum and maximum element wil
# Intuition
Number Theory + Combinatorics

# Approach
We need to focus on minimum and maximum elements only. Ask yourself how many times minimum and maximum element will come in total sum. So, for every [1...k] length subsequence we need to have minimum and maximum element fixed and try to generate all the possible subsequence by choosing k-1 element from respective range.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(NlogN + K*N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(2*N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define all(a)      a.begin(), a.end()
#define MOD         1000000007

class Solution {
public:
    vector<long> fact, invFact;
    long modExpo(long a, long b){
        long res = 1;
        while(b > 0){
            if(b & 1) res = (res * a) % MOD;
            a = (a * a) % MOD;
            b = b >> 1;
        }
        return res;
    }
    void preCompute(int n){
        fact.resize(n + 1);
        invFact.resize(n + 1);

        fact[0] = 1;
        for(long i=1; i<=n; i++){
            fact[i] = (fact[i-1] * i) % MOD;
        }

        invFact[n] = modExpo(fact[n], MOD - 2);
        for(long i=n-1; i >= 0; i--){
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }
    long nCr(int n, int r){
        if(r > n || r < 0) return 0;
        return (((fact[n] * invFact[r]) % MOD) * invFact[n-r]) % MOD;
    } 
    int minMaxSums(vector<int>& a, long k) {
        int n = a.size();
        preCompute(n);
        sort(all(a));
        long sum = 0;
        for(long i=1; i<=k; i++){
            for(long j=i-1; j<n; j++){
                // For maximum element
                // choose k-1 from [1...j-1] * a[j])
                long maxSum = ((nCr(j, i-1) * a[j]) % MOD);
                sum = (sum + maxSum) % MOD;
            }
            for(long j=0; j<(n-i+1); j++){
                // For minimum element
                // choose k-1 from [j+1...n] * a[j])
                long minSum = ((nCr(n-j-1, i-1) * a[j]) % MOD);
                sum = (sum + minSum) % MOD;
            }
        }
        return sum;
    }
};
```
['C++']