For a sequence of integers [a1,a2,…an], define the function f(i) as follows: Take the first i elements of a (a1,a2,…ai) and sort them in non-decreasing order. Call this new sequence si. Let f(i) = 1 * s1 + 2 * s2 + …i * si.

Given a sequence of n integers, sort them in non-decreasing order then compute f(1) + f(2) + …+ f(n). As result may be very large, return it modulo(1e9+7).

Constraints : 1 <= n <= 10^6, 1<=a[i] <= 10^6.

Example :

Input:

n=3, a = [9, 5, 8]

Output: 80

Explanation :

s1 = [9]; f(1) = 1 * 9=9.

s2 = [5, 9]; f(2) = 1 * 5 + 2 * 9 = 23.

s3 = [5,8,9]; f(3) = 1 * 5 + 2 * 8 + 3 * 9 = 48.

f(1)+f(2)+…+f(n) = f(1)+f(2)+f(3) = 9+23+48=80.

My Logic :

```
long long solve(vector a)
{
long long count=0, n=a.size(), sum=0;
for(long long i=0; i<n; i++)
{
sort(a.begin(), a.begin()+count+1);
count++;
for(long long j=0; j<count; j++)
sum+=a[j]*(j+1);
}
return sum;
}
```