Range Sum of Sorted Subarray Sums

Find the sum of every nonempty contiguous subarray of nums, keeping repeated sums as separate entries. Sort these sums in nondecreasing order.

Return the sum of the entries at positions left through right, inclusive, in that sorted list. Positions are numbered starting from 1. Return the answer modulo 1000000007. The value n equals the length of nums.

Example 1:

Input: nums = [2,1,2]
n = 3
left = 2
right = 5

Output: 10

Explanation: The six subarray sums, sorted, are [1,2,2,3,3,5]. Positions 2 through 5 contain 2, 2, 3, and 3, whose sum is 10.

Example 2:

Input: nums = [3,3]
n = 2
left = 1
right = 3

Output: 12

Explanation: The sorted subarray sums are [3,3,6]. Both occurrences of 3 remain in the list. Summing all three entries gives 12.

Example 3:

Input: nums = [5]
n = 1
left = 1
right = 1

Output: 5

Explanation: There is only one nonempty subarray, [5]. Its sum occupies position 1, so the requested range sums to 5.

Constraints:

• n == nums.length
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100
• 1 <= left <= right <= n * (n + 1) / 2