Easy to understand
IntuitionTo solve this problem, the key idea is to calculate the sum of contributions of each element in the array to the minimum and maximum sums of all subseq
# Intuition
To solve this problem, the key idea is to calculate the sum of contributions of each element in the array to the minimum and maximum sums of all subsequences. Each element's contribution is determined by the number of subsequences it can appear in, which depends on its position in the sorted array. By leveraging combinatorics, we calculate these contributions efficiently.

# Approach
1. **Sort the Array**:  
   Sorting the array ensures that smaller elements contribute to the minimum sum first and larger elements contribute to the maximum sum when reversed.

2. **Precompute nCr**:  
   Use combinatorics to precompute the number of subsequences of size `r` for given `n`. This is done using modular arithmetic and Fermat's Little Theorem for efficiency.

3. **Calculate Minimum Sum Contribution**:  
   Iterate through the sorted array, and for each element, calculate the total number of subsequences it contributes to as the smallest element in those subsequences.

4. **Reverse for Maximum Sum Contribution**:  
   Reverse the array and repeat the process to calculate contributions when each element is the largest in its subsequences.

5. **Combine Results Modulo 10^9+7**:  
   Add both contributions and return the result modulo \(10^9 + 7\).

# Complexity
- **Time Complexity**:  
  The time complexity is \(O(n \cdot k)\), where \(n\) is the size of the array and \(k\) is the maximum size of subsequences considered, due to the nested loop for precomputing and calculating contributions.

- **Space Complexity**:  
  The space complexity is \(O(n \cdot k)\) for storing precomputed combinations.

# Code
```cpp
class Solution {
public:
    const int MOD = 1e9 + 7;

    long long modExp(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1)
                result = (result * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }

    long long modInverse(long long a, long long mod) {
        return modExp(a, mod - 2, mod); // Using Fermat's Little Theorem
    }

    long long nCr(int n, int r) {
        if (r > n)
            return 0;
        if (r == 0 || r == n)
            return 1;

        long long numerator = 1, denominator = 1;
        for (int i = 1; i <= r; i++) {
            numerator = (numerator * (n - i + 1)) % MOD;
            denominator = (denominator * i) % MOD;
        }
        return (numerator * modInverse(denominator, MOD)) % MOD;
    }

    int minMaxSums(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long sum = 0;
        
        // Precompute nCr values
        vector<vector<long long>> calNcr(n, vector<long long>(k + 1, 0));
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                calNcr[i][j] = nCr(i, j);
            }
        }

        // Calculate minimum sum contribution
        for (int i = 0; i < n; i++) {
            int c = min(k - 1, n - i - 1);
            long long totalSubsequence = 0;
            for (int j = 1; j <= c; j++) {
                totalSubsequence = (totalSubsequence + calNcr[n - i - 1][j]) % MOD;
            }
            sum = (sum + (totalSubsequence + 1) * nums[i]) % MOD;
        }

        reverse(nums.begin(), nums.end());

        // Calculate maximum sum contribution
        for (int i = 0; i < n; i++) {
            int c = min(k - 1, n - i - 1);
            long long totalSubsequence = 0;
            for (int j = 1; j <= c; j++) {
                totalSubsequence = (totalSubsequence + calNcr[n - i - 1][j]) % MOD;
            }
            sum = (sum + (totalSubsequence + 1) * nums[i]) % MOD;
        }

        return sum % MOD;
    }
};

['C++']