Otra decepción más: un problema de emparejamiento#12858

Otra decepción más: un problema de emparejamiento

1 segundo
256 megabytes
Muy difícil

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:

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.

Entrada

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.

Salida

Imprime la suma de los costos de todas las permutaciones de este arreglo, módulo 10^9 + 7.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

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.