3428. Maximum and Minimum Sums of at Most Size K Sub sequences
IntuitionThe problem revolves around finding the sum of the minimum and maximum values of all subsequences of size at most ( k ) from the given array. Sorting t
# Intuition
The problem revolves around finding the sum of the minimum and maximum values of all subsequences of size at most \( k \) from the given array. Sorting the array simplifies the process of calculating how often an element appears as the minimum or maximum in these subsequences, enabling efficient computation.

# Approach
1. **Sorting the Array**:  
   Sorting ensures that for any subsequence, smaller elements are always considered as the minimum, and larger elements as the maximum, in a sequential manner.

2. **Frequency Calculation**:  
   For each element in the sorted array:
   - Calculate how many times the element appears as the **minimum** in subsequences using the combination formula:  
     \( \text{nCr}(i, \text{size}-1) \), where \( i \) is the index of the element.
   - Calculate how many times the element appears as the **maximum** using the formula:  
     \( \text{nCr}(\text{n}-i-1, \text{size}-1) \).

3. **Factorials Precomputation**:  
   Since calculating combinations repeatedly is computationally expensive, precompute factorials and modular inverses using Fermat's Little Theorem for efficient \( \text{nCr} \) calculations.

4. **Iterate for Each Subsequence Size**:  
   For every possible subsequence size from 1 to \( k \):
   - Add the contributions of each element being the minimum and maximum to the result.

5. **Modulo Arithmetic**:  
   Use modulo \( 10^9 + 7 \) to ensure no overflow and meet problem constraints.

# Complexity
- **Time complexity**:  
  \( O(n \cdot k + n \log n) \):  
  - Sorting the array takes \( O(n \log n) \).  
  - Iterating through all elements for up to \( k \) subsequence sizes involves \( O(n \cdot k) \) computations.

- **Space complexity**:  
  \( O(n) \): For storing factorials and their inverses.

# Code
```cpp
class Solution {
public:
    const int m = 1e9 + 7;
    
    long long bin_mul(long long a, long long b) {
        long long ans = 0;
        while (b) {
            if (b & 1) {
                ans = (ans + a) % m;
            }
            a = (a + a) % m;
            b >>= 1;
        }
        return ans;
    }
    
    long long bin_expo(long long a, long long b) {
        long long ans = 1;
        while (b) {
            if (b & 1) {
                ans = (ans * a) % m;
            }
            a = (a * a) % m;
            b >>= 1;
        }
        return ans;
    }
    
    vector<long long> fact, invFact;

    void preComputeFactorials(int n) {
        fact.resize(n + 1);
        invFact.resize(n + 1);
        
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            fact[i] = (fact[i - 1] * i) % m;
        }
        invFact[n] = bin_expo(fact[n], m - 2);
        for (int i = n - 1; i >= 0; --i) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % m;
        }
    }
    
    long long nCr(int n, int r) {
        if (r < 0 || r > n) return 0;
        return (fact[n] * invFact[r] % m * invFact[n - r] % m) % m;
    }
    
    int minMaxSums(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int n = nums.size();
        preComputeFactorials(n);
        
        long long result = 0;
        for (int size = 1; size <= k; ++size) {
            for (int i = 0; i < n; ++i) {
                long long min_contrib = (nums[i] * nCr(i, size - 1)) % m;
                long long max_contrib = (nums[i] * nCr(n - i - 1, size - 1)) % m;
                result = (result + min_contrib + max_contrib) % m;
            }
        }
        return (int)result;
    }
};
```

### Summary:
This approach leverages sorting and combination calculations to efficiently compute the result for all subsequences. The use of modular arithmetic ensures performance and correctness within the constraints.
['Combinatorics', 'C++']