Python O(nlogn), works on any large k
IntuitionFor each number, count how many times it contributes as a max or min number, just multiply the times by the value.ApproachIntuitively, first sort it. F
# Intuition

For each number, count how many times it **contributes** as a max or min number, just multiply the times by the value.

# Approach

Intuitively, first sort it. For each number `nums[i]`, we can pick at most `k-1` numbers in `nums[:i]` to construct the sequences in which `nums[i]` is the largest one.

The count of such sequences can be calculated as follows:

$$ \sum_{t = 0}^{k-1} {i \choose t} =  {i \choose 0} + {i \choose 1} + \cdots + {i \choose k-1} $$

where ${i \choose t}$ means the number of ways to pick `t` numbers from `i` numbers, we'll use `comb(i, t)` to represent it in our code.

To calculate the maximum value `nums[i]` contributes, the only thing we need is to multiply this count $\sum_{t = 0}^{k-1} {i \choose t}$ by `nums[i]`. Therefore, the sum of maximum values in all qualified sequences can be obtained by enumerating and summing up all $\sum_{t = 0}^{k-1} {i \choose t} \times nums[i]$. For the sum of minimum values, it is similar. In the following part, we'll only show how to calculate the sum of maximum values.

The most tricky part is about how to get the sum of ${i \choose t}$ quickly. If we insist on calculating it directly, it will be very slow with the time complexity of $O(nk)$ to sum up all maximum values. However, we can find a **recursive formula** to calculate ${i \choose t}$ quickly, which is,

$$ \sum_{t = 0}^{k-1} {i+1 \choose t} = 2 \times \sum_{t = 0}^{k-1} {i \choose t} - {i \choose k-1} $$

*(To prove or reduce it as a practice, you can ask chatgpt for the details. Hint: try staggered subtraction)*

Thus, we can maintain $\sum_{t = 0}^{k-1} {i+1 \choose t}$ during the iteration, and update it by the formula above, which costs only $O(1)$ time in each loop.

If you have difficulty with handling the combination number under modulo, you can refer to [my personal blog](https://lctemplates.readthedocs.io/en/latest/tips.html#modulo-10-9-7).



# Complexity
- Time complexity:

$$O(n \log n)$$

where `n` is the length of `nums`, bottlenecked by the sorting.

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

$$O(n)$$

# Code
```python3
from itertools import accumulate

M = 10 ** 9 + 7

frac = list(accumulate(range(1, 10**5 + 1), lambda x, y: x * y % M, initial=1))


def comb(n, k):
    if n < k:
        return 0
    return frac[n] * pow(frac[k], -1, M) * pow(frac[n - k], -1, M) % M


class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        res = 0
        s = 1  # sum_{t = 0}^{k - 1} comb(m, t) => S_m
        # S_m = 2 * S_{m - 1} - comb(m-1, k-1)
        for i in range(n):
            res += (nums[i] + nums[n - i - 1]) * s
            res %= M
            s = (2 * s - comb(i, k-1)) % M
        return res

```
['Math', 'Python3']