You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 109 + 7.

&nbsp;
Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 


Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.


Example 3:

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


&nbsp;
Constraints:


	n == nums.length
	1 &lt;= nums.length &lt;= 1000
	1 &lt;= nums[i] &lt;= 100
	1 &lt;= left &lt;= right &lt;= n * (n + 1) / 2


from itertools import accumulate

class Solution:
    def rangeSum(self, nums, n, left, right):
        acc = []

        for i in range(n):
            acc.extend(accumulate(nums[i:]))

        acc.sort()

        return sum(acc[left - 1:right]) % (10**9 + 7)
class Solution {
    private static int mod=(int)1e9+7;
    public int rangeSum(int[] nums, int n, int left, int right) {
        
        PriorityQueue<int[]> pq=new PriorityQueue<>((n1,n2)->n1[1]-n2[1]);
        
        for(int i=0;i<n;i++) pq.add(new int[]{i,nums[i]});
        
        int ans=0;
        for(int i=1;i<=right;i++){
            int[] k=pq.remove();
            if(i>=left){
                ans=(ans+k[1])%mod;
            }
            if(k[0]+1<n){
                pq.add(new int[]{k[0]+1,k[1]+nums[k[0]+1]});
            }
        }
        return ans;
    }
}
class Solution 
{
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) 
    {
        const int m= 1e9+7; // To return ans % m
        int ans=0;  // Final Answer
        int k=1;  // For 1 based indexing
        int size= (n*(n+1))/2;  // We can form n(n+1)/2 subarrays for an array of size n
        vector<int> subsum(size+1); 
        for(int i=0;i<n;i++)
        {
            int sum=0;
            for(int j=i;j<n;j++)
            {
                sum+=nums[j];     // Sum of the subarray
                subsum[k++]=sum;   // Inserting the prefix sum at the index
            }
        }
        sort(subsum.begin(),subsum.end()); // Sorting the array
        for(int i=left; i<=right; i++)
        {
            ans=(ans+subsum[i])%m;   // ans modulo 10^9 +7
        }
        return ans;
    }
};
var rangeSum = function(nums, n, left, right) {
    const sums = [];
    
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            sums.push(sum);
        }
    }
    
    sums.sort((a, b) => a - b);
    
    let ans = 0;
    
    for (let i = left - 1; i < right; i++) {
        ans += sums[i];
    }
    
    return ans % 1000000007;
};
Range Sum of Sorted Subarray Sums