Чергове розчарування: задача на парування#10774

Чергове розчарування: задача на парування

1 second

256 megabytes

Very hard

Дано непарне число $n$ . Для масиву з $n$ чисел $[a_{1}, a_{2}, \dots, a_{n}]$ [a_1, a_2, \ldots, a_n], будемо визначати його вартість, як максимальну вагу досконалого парування в графі на $n + 1$ n+1 вершинах, в якому вага ребра $(i, j)$ для $i < j$ i<j визначається як $ma x (a_{i}, a_{i + 1}, \dots, a_{j - 1})$ max(a_i, a_{i+1}, \ldots, a_{j-1}).

Наприклад, для масиву $[1, 30, 15]$ [1, 30, 15], ми маємо граф на $4$ вершинах з наступними відстанями між ними:

$d (1, 2) = 1$ d(1, 2) = 1
$d (1, 3) = d (1, 4) = d (2, 3) = d (2, 4) = 30$ d(1, 3) = d(1, 4) = d(2, 3) = d(2, 4) = 30
$d (3, 4) = 15$ d(3, 4) = 15

Тут парування $((1, 2), (3, 4))$ ((1, 2), (3, 4)) має вагу $16$ , а $((1, 3), (2, 4))$ ((1, 3), (2, 4)) і $((1, 4), (2, 3))$ ((1, 4), (2, 3)) мають ваги $60$ , тому вартість всього масиву рівна $60$ .

Вам дано масив $b$ довжини $n$ з попарно різних елементів. Знайдіть суму вартостей всіх перестановок цього масиву, за модулем $1 0^{9} + 7$ 10^9 + 7.

Нагадаємо, що досконале парування в зваженому графі на $2 k$ вершинах — це набір з $k$ ребер такий, що кожна вершина є кінцем рівно одного ребра. Вагою досконалого парування вважається сума ваг всіх вибраних $k$ ребер.

Input

Перший рядок містить єдине ціле число $n$ ( $1 \leq n \leq 99999$ 1 \leq n \leq 99\,999, $n$ непарне) — довжину масиву.

Другий рядок містить $n$ попарно різних цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n ( $1 \leq b_{i} \leq 1 0^{8}$ 1 \leq b_i \leq 10^8) — елементи масиву.

Output

Виведіть суму вартостей всіх перестановок цього масиву, за модулем $1 0^{9} + 7$ 10^9 + 7.

Examples

Example 1

Example 2

Example 3

Note

В прикладі:

Вартості масивів $[1, 30, 15]$ [1, 30, 15] та $[15, 30, 1]$ [15, 30, 1] рівні $60$ .
Вартості масивів $[1, 15, 30]$ [1, 15, 30], $[30, 15, 1]$ [30, 15, 1], $[15, 1, 30]$ [15, 1, 30], $[30, 1, 15]$ [30, 1, 15] рівні $45$ .

Сума по всім перестановкам рівна $60 \cdot 2 + 45 \cdot 4 = 300$ 60\cdot 2 + 45\cdot 4 = 300.