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

Дано непарне число $n$. Для масиву з $n$ чисел $[a_1,a_2,\dots ,a_n]$, будемо визначати його вартість, як максимальну вагу досконалого парування в графі на $n+1$ вершинах, в якому вага ребра $(i,j)$ для $i<j$ визначається як $max(a_i,a_{i+1},\dots ,a_{j-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$ з попарно різних елементів. Знайдіть суму вартостей всіх перестановок цього масиву, за модулем $10^9+7$.

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

Input

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

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

Output

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

Examples

Note

В прикладі:

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

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

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