FIICode 2025 Qualifying Round - Studenți | Frumusel

Task

Given an number $n$ and an array $a=[a_1,a_2,...,a_n]$, we define its beauty $f(a)$ as follows:

$f(a)=\sum_{i=1}^{n} \left| a_i-a_{(i \bmod n) +1} \right|=|a_1-a_2|+|a_2-a_3|+\ldots+|a_{n-1}-a_n|+|a_n-a_1|$.

You are given a number $n$ and an array $v=[v_1,v_2,...,v_n]$ consisting of $n$ distinct positive integers.
You must find out the average beauty of all permutations of $a$ modulo $10^9+7$.

Input data

The first line of input contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) - the length of array $v$.

The second line of input contains $n$ integers $v_1,v_2,..,v_n$ ($0 \le v_i \le 10^9$) - the elements of array $v$.

Output data

It is guaranteed that the real answer is of form $\frac {p}{q}$ where $p$, $q$ are nonnegative integers .
You need to print the number $p\cdot q^{-1}\bmod(10^9+7)$.

Example 1

stdin

3
8 6 1

stdout

14

Example 2

stdin

4
10 0 1 7

stdout

24