题目链接

题意

给定一个长度为 $n$ 的序列 $a$。

定义一个函数 $f(l,r)$ 表示下面操作后的结果。

• 创建一个长度为 $r-l+1$ 的序列 $b$ 使得 $b_i=a_{l-1+i}$。

• 对 $b$ 从小到大排序。

• 最后的答案就是 $\sum_{i=1}^{r-l+1} b_i\times i$。

求 $\sum_{l=1}^n \sum_{r=l}^n f(l,r)$。

答案对 $10^9+7$ 取模。

输入格式

一行一个数 $n$，接下来 $n$ 个数，表示该序列。

输出格式

一行一个数，表示答案。

样例

4
5 2 4 7

167

3
123456789 214365879 987654321

582491518

数据范围

$1\le n\le 5\times 10^5$