Вам задан массив \(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)\). Другими словами — сумму функций \(f\) для всех подотрезков массива \(a\) по модулю \(10^9+7\).
Выходные данные
Выведите единственное число — сумму функций \(f\) для всех подотрезков массива \(a\) по модулю \(10^9+7\).
Примечание
Описание первого примера:
- \(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\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2 4 7
|
167
|
|
2
|
3
123456789 214365879 987654321
|
582491518
|