F. Scalar Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a_1, a_2, \dots, a_n. All a_i are pairwise distinct.Let's define function f(l, r) as follows:   let's define array b_1, b_2, \dots, b_{r - l + 1}, where b_i = a_{l - 1 + i};  sort array b in increasing order;  result of the function f(l, r) is \sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}. Calculate \left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7), i.e. total sum of f for all subsegments of a modulo 10^9+7.InputThe first line contains one integer n (1 \le n \le 5 \cdot 10^5) — the length of array a.The second line contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9, a_i \neq a_j for i \neq j) — array a.OutputPrint one integer — the total sum of f for all subsegments of a modulo 10^9+7ExamplesInput
4
5 2 4 7
Output
167
Input
3
123456789 214365879 987654321
Output
582491518
NoteDescription of the first example:   f(1, 1) = 5 \cdot 1 = 5;  f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12;  f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25;  f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53;  f(2, 2) = 2 \cdot 1 = 2;  f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10;  f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31;  f(3, 3) = 4 \cdot 1 = 4;  f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18;  f(4, 4) = 7 \cdot 1 = 7; 
4
5 2 4 7

167 
['combinatorics', 'data structures', 'math', 'sortings', '*2300']