Description:
You 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$$$.
Input Format:
The 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$$$.
Output Format:
Print one integer — the total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$
Note:
Description 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$$$;