Maximum and Minimum Sums of at Most Size K Subsequences
You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
nums = [1,2,3], k = 2Output
24The subsequences of nums with at most 2 elements contribute sums 2, 4, 6, 3, 4, and 5, for a final total of 24.
Example 2
Input
nums = [5,0,6], k = 1Output
22For subsequences with exactly 1 element, the minimum and maximum values are the element itself, so the total is 5 + 5 + 0 + 0 + 6 + 6 = 22.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- 1 <= k <= min(70, nums.length)