Se te da un número impar . Para un arreglo de números [a_1, a_2, \ldots, a_n], definimos su costo como el peso máximo de un emparejamiento perfecto en el grafo de n+1 vértices en el que el peso de la arista para i<j se define como max(a_i, a_{i+1}, \ldots, a_{j-1}).
Por ejemplo, para el arreglo [1, 30, 15] tenemos un grafo de vértices con las siguientes distancias entre ellos:
d(1, 2) = 1
d(1, 3) = d(1, 4) = d(2, 3) = d(2, 4) = 30
d(3, 4) = 15
Aquí el emparejamiento ((1, 2), (3, 4)) tiene peso , mientras que ((1, 3), (2, 4)) y ((1, 4), (2, 3)) tienen peso , por lo que el costo de todo el arreglo es igual a .
Se te da un arreglo de longitud con elementos distintos dos a dos. Encuentra la suma de los costos de todas las permutaciones de este arreglo, módulo 10^9 + 7.
Recuerda que un emparejamiento perfecto en un grafo ponderado de vértices es un conjunto de aristas tal que cada vértice es extremo de exactamente una arista. El peso de un emparejamiento perfecto es la suma de los pesos de las aristas elegidas.
La primera línea contiene un entero (1 \leq n \leq 99\,999, es impar) — la longitud del arreglo.
La segunda línea contiene enteros distintos dos a dos b_1, b_2, \ldots, b_n (1 \leq b_i \leq 10^8) — los elementos del arreglo.
Imprime la suma de los costos de todas las permutaciones de este arreglo, módulo 10^9 + 7.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el ejemplo:
Los costos de los arreglos [1, 30, 15] y [15, 30, 1] son iguales a .
Los costos de los arreglos [1, 15, 30], [30, 15, 1], [15, 1, 30], [30, 1, 15] son iguales a .
La suma sobre todas las permutaciones es igual a 60\cdot 2 + 45\cdot 4 = 300.