Python Combinatorics ✅ | Optimal Time-Complexity - O(n log n)
IntuitionTo solve this problem, we need to calculate the sum of the minimum and maximum elements across all subsequences of the array with at most ( k ) element
# Intuition
To solve this problem, we need to calculate the sum of the minimum and maximum elements across all subsequences of the array with at most \( k \) elements. Key observations:
1. Sorting the array helps us efficiently determine contributions of each element as a minimum or maximum.
2. We can use combinatorics to calculate how many subsequences each element contributes to as either the minimum or maximum.

# Approach
1. **Sorting the array**:
   - Sort the input array `nums` in ascending order. This helps us easily identify the contributions of elements as minimum and maximum in subsequences.

2. **Combinatorics setup**:
   - Use a precomputed combination table to quickly calculate the number of ways an element contributes as the minimum or maximum in subsequences of different lengths.

3. **Iterating through elements**:
   - For each element in the array:
     - Calculate how many subsequences it contributes to as the **minimum**.
     - Calculate how many subsequences it contributes to as the **maximum**.
     - Add the respective contributions to the total.

4. **Modular arithmetic**:
   - Since the result can grow very large, perform all calculations modulo \( 10^9 + 7 \).

5. **Return the result**:
   - Return the total sum modulo 10^9 + 7

# Complexity
- **Time complexity**:
  - Sorting the array:  O(n * log n)
  - Precomputing combinations: O(nk)
  - Iterating over the array and calculating contributions: O(nk)
  - Overall: O(nk + nlogn)

- **Space complexity**:
  - Storing the combination table: O(nk)
  - Overall: O(nk)

# Code
```python
from typing import List

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # Precompute combination values
        comb = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            comb[i][0] = 1
            for j in range(1, min(i, k) + 1):
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD
        
        # Sort the array
        nums.sort()
        total = 0
        
        # Calculate contributions of each element as min and max
        for i in range(n):
            for r in range(1, k + 1):
                if r > n:
                    break
                
                # Contribution as the minimum
                min_contribution = comb[n - 1 - i][r - 1]
                total = (total + (nums[i] * min_contribution) % MOD) % MOD
                
                # Contribution as the maximum
                max_contribution = comb[i][r - 1]
                total = (total + (nums[i] * max_contribution) % MOD) % MOD

        return total

['Python3']