Дано непарне число $n$. Для масиву з $n$ чисел $[a_1, a_2, \ldots, a_n]$, будемо визначати його \textbf{вартість}, як максимальну вагу досконалого парування в графі на $n+1$ вершинах, в якому вага ребра $(i, j)$ для $i<j$ визначається як $max(a_i, a_{i+1}, \ldots, a_{j-1})$. Наприклад, для масиву $[1, 30, 15]$, ми маємо граф на $4$ вершинах з наступними відстанями між ними: \begin{itemize} \item $d(1, 2) = 1$ \item $d(1, 3) = d(1, 4) = d(2, 3) = d(2, 4) = 30$ \item $d(3, 4) = 15$ \end{itemize} Тут парування $((1, 2), (3, 4))$ має 16, а $((1, 3), (2, 4))$ і $((1, 4), (2, 3))$ мають ваги $60$, тому вартість всього масиву рівна $60$. Вам дано масив $b$ довжини $n$ з \textbf{попарно різних} елементів. Знайдіть суму вартостей всіх перестановок цього масиву, за модулем $10^9 + 7$. Нагадаємо, що досконале парування в зваженому графі на $2k$ вершинах --- це набір з $k$ ребер такий, що кожна вершина є кінцем рівно одного ребра. Вагою досконалого парування вважається сума ваг всіх вибраних $k$ ребер. \InputFile Перший рядок містить єдине ціле число $n$ ($1 \leq n \leq 99\,999$, $n$ \textbf{непарне}) --- довжину масиву. Другий рядок містить $n$ \textbf{попарно різних} цілих чисел $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^8$) --- елементи масиву. \OutputFile Виведіть суму вартостей всіх перестановок цього масиву, за модулем $10^9 + 7$. \Note В прикладі: \begin{itemize} \item Вартості масивів $[1, 30, 15]$ та $[15, 30, 1]$ рівні $60$. \item Вартості масивів $[1, 15, 30]$, $[30, 15, 1]$, $[15, 1, 30]$, $[30, 1, 15]$ рівні $45$. \end{itemize} Сума по всім перестановкам рівна $60\cdot 2 + 45\cdot 4 = 300$.