Dado un arreglo ~A~ de ~n (3 \leq n \leq 10^5)~ elementos, calcule la suma de, para cada uno de los ~2^n - 1~ subconjuntos no vacíos del mismo, de la diferencia entre el máximo y el mínimo del subconjunto, para más detalle vea la explicación del ejemplo.

Los elementos del arreglo serán enteros entre ~0~ y ~10^9~.

Como la respuesta puede ser muy grande, imprímala módulo ~10^9 + 7 (1000000007)~.

Subtareas:

• Subtarea 1: ~n \leq 1000~, los elementos de ~A~ son ~0~s o ~1~s. ( 15 puntos )

• Subtarea 2: ~n \leq 16~. ( 25 puntos )

• Subtarea 3: ~n \leq 1000~. ( 30 puntos )

• Subtarea 4: ~n \leq 10^5~. ( 30 puntos )

Entrada:

N
A_1 A_2 ... A_N

Salida:

answer

Ejemplo de entrada 1:

3
1 2 3

Ejemplo de salida 1:

6

Explicación del ejemplo 1:

Subconjunto       Diferencia entre máximo y mínimo
{1}                             0
{2}                             0
{3}                             0
{1, 2}                          1
{1, 3}                          2
{2, 3}                          1
{1, 2, 3}                       2

Ejemplo de entrada 2:

5
1 1 0 1 0

Ejemplo de salida 2:

21

Ejemplo de entrada 3:

6
1 3 2 7 8 4

Ejemplo de salida 3:

291