给你一个数组 $$$a_1, a_2, \dots, a_n$$$。所有 $$$a_i$$$ 都是成对不同的。
让我们定义函数 $$$f(l, r)$$$ 如下:
- 让我们定义数组 $$$b_1, b_2, \dots, b_{r - l + 1}$$$,其中 $$$b_i = a_{l - 1 + i}$$$;
- 按升序对数组 $$$b$$$ 进行排序;
- 函数 $$$f(l, r)$$$ 的结果是 $$$\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$$$。
计算 $$$\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$$$,即 $$$a$$$ 模 $$$10^9+7$$$ 的所有子段的 $$$f$$$ 总和。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$) — 数组 $$$a$$$。
输出
打印一个整数 — $$$a$$$ 的所有子段的 $$$f$$$ 的总和以 $$$10^9+7$$$ 为模
示例
输入 #1
4 5 2 4 7
输出 #1
167
输入 #2
3 123456789 214365879 987654321
输出 #2
582491518
注意
第一个示例说明:
- $$$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$$$;