Дано непарне число n. Для масиву з n чисел [a1,a2,…,an], будемо визначати його вартість, як максимальну вагу досконалого парування в графі на n+1 вершинах, в якому вага ребра (i,j) для i<j визначається як max(ai,ai+1,…,aj−1).
Наприклад, для масиву [1,30,15], ми маємо граф на 4 вершинах з наступними відстанями між ними:
d(1,2)=1
d(1,3)=d(1,4)=d(2,3)=d(2,4)=30
d(3,4)=15
Тут парування ((1,2),(3,4)) має 16, а ((1,3),(2,4)) і ((1,4),(2,3)) мають ваги 60, тому вартість всього масиву рівна 60.
Вам дано масив b довжини n з попарно різних елементів. Знайдіть суму вартостей всіх перестановок цього масиву, за модулем 109+7.
Нагадаємо, що досконале парування в зваженому графі на 2k вершинах — це набір з k ребер такий, що кожна вершина є кінцем рівно одного ребра. Вагою досконалого парування вважається сума ваг всіх вибраних k ребер.
Перший рядок містить єдине ціле число n (1≤n≤99999, n непарне) — довжину масиву.
Другий рядок містить n попарно різних цілих чисел b1,b2,…,bn (1≤bi≤108) — елементи масиву.
Виведіть суму вартостей всіх перестановок цього масиву, за модулем 109+7.
В прикладі:
Вартості масивів [1,30,15] та [15,30,1] рівні 60.
Вартості масивів [1,15,30], [30,15,1], [15,1,30], [30,1,15] рівні 45.
Сума по всім перестановкам рівна 60⋅2+45⋅4=300.