Range Sum of Sorted Subarray Sums

You are given an integer array nums of length n. Compute all non-empty subarray sums, sort them in ascending order, and return the sum of elements from index left to right (1-indexed) in this sorted list, modulo 10^9 + 7.

Examples

Example 1:

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

Output: 13

Explanation: All subarray sums sorted: [1,2,3,3,4,5,6,7,9,10]. Sum of first 5 = 1+2+3+3+4 = 13.

Example 2:

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

Output: 6

Explanation: Subarray sums sorted: [1,2,3,3,4,...]. Elements at indices 3 and 4 are both 3, sum = 6.

Example 3:

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

Output: 1

Explanation: The only subarray sum is 1.

Constraints

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