Summing Subsequence Extremes with Binomial Coefficients
IntuitionThe problem revolves around calculating the contributions of each element in the array as both the maximum and the minimum for all subsequences of size
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem revolves around calculating the contributions of each element in the array as both the **maximum** and the **minimum** for all subsequences of size at most ```k```. Instead of generating all possible subsequences (which is computationally expensive), use **sorting** and **combinatorics** to efficiently count the relevant subsequences and compute their contributions.

### The Key Insight:
By sorting the array, each element's contribution as the maximum or minimum can be systematically computed using binomial coefficients (n choose r or $$nCr$$), which count the number of ways to form subsequences including the element.

# Approach
<!-- Describe your approach to solving the problem. -->
**1. Sort the Array**
Sorting the array simplifies the process of calculating contributions as the maximum or minimum.

**2. Precompute Factorials and Modular Inverses**
Using precomputed factorials and their modular inverses, we can efficiently compute the binomial coefficient ($$nCr$$) using the formula:
$$nCr=\frac{n!}{r!(n-r)!}\ mod\ (10^9+7)$$

**3. Iterate Through Each Element**
For each element in the sorted array:

1. Compute its contribution as the **maximum** by considering all subsequences where it is the largest element.
2. Compute its contribution as the **minimum** by considering all subsequences where it is the smallest element.

**4. Add Contributions Module $$10^9+7$$**
To handle largre numbers, every operation is performed modulo $$10^9+7$$.

**5. Return the Total Sum**
Combine all contributions to get the final result.

# Complexity
### Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
1. Sorting the array: $$O(nlogn)$$
2. Precomputing factorials and modular inverses: $$O(n)$$
3. Calculating contributions for each element: $$O(n\cdot k)$$
4. **Overall**: $$O(nlogn + n + n\cdot k)$$

### Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1. Storing factorials and modular inverses $$O(n)$$

# Code
```java []
import java.util.Arrays;

class Solution {
    static final int MOD = 1_000_000_007;
    static long[] fact, inv;

    // Precompute factorials and modular inverses
    static void precomputeFactorials(int n) {
        fact = new long[n + 1];
        inv = new long[n + 1];
        fact[0] = 1;

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

        // Compute the modular inverse of n! using Fermat's Little Theorem
        inv[n] = modularExponentiation(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) {
            inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }
    }

    // Efficient modular exponentiation (a^b % MOD)
    static long modularExponentiation(long a, long b) {
        long result = 1;
        a %= MOD;

        while (b > 0) {
            if ((b & 1) == 1) {
                result = (result * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }

        return result;
    }

    // Compute nCr modulo MOD
    static long nCr(int n, int r) {
        if (r < 0 || r > n) return 0;
        return (fact[n] * inv[r] % MOD * inv[n - r]) % MOD;
    }

    // Main function to calculate the sum of minimum and maximum contributions
    public int minMaxSums(int[] nums, int k) {
        int n = nums.length;

        // Step 1: Sort the array
        Arrays.sort(nums);

        // Step 2: Precompute factorials and modular inverses
        precomputeFactorials(n);

        long totalSum = 0;

        // Step 3: Calculate contributions for each number in the array
        for (int i = 0; i < n; i++) {
            int leftCount = i;         // Number of elements before nums[i]
            int rightCount = n - 1 - i; // Number of elements after nums[i]

            // Calculate contributions when nums[i] is the maximum
            long maxContribution = 0;
            for (int j = 0; j < k && j <= leftCount; j++) {
                maxContribution = (maxContribution + nCr(leftCount, j)) % MOD;
            }
            totalSum = (totalSum + (maxContribution * nums[i]) % MOD) % MOD;

            // Calculate contributions when nums[i] is the minimum
            long minContribution = 0;
            for (int j = 0; j < k && j <= rightCount; j++) {
                minContribution = (minContribution + nCr(rightCount, j)) % MOD;
            }
            totalSum = (totalSum + (minContribution * nums[i]) % MOD) % MOD;
        }

        return (int) totalSum;
    }
}

```
['Array', 'Math', 'Combinatorics', 'Java']