El robot C-3BA, en su jornada por reparar robots en una isla del Caribe, está interesado en contar subsecuencias de un arreglo con propiedades interesantes, pues esto le ayudará a entender el funcionamiento interno de los robots más complejos.

Dado un arreglo ~a~ de ~n~ enteros, determine el número de subsecuencias tales que:

1. Hay al menos 2 elementos en la subsecuencia.
2. Todos los elementos en posiciones impares de la subsecuencia son iguales.
3. Todos los elementos en posiciones pares de la subsecuencia son iguales.
4. Los primeros dos elementos de la subsecuencia son diferentes.

Por ejemplo, si ~a = [1, 2, 5, 4, 2, 3, 5, 3]~ una de estas subsecuencias podría ser ~b = [2, 5, 2, 5]~ (observe que los elementos en posiciones impares de la subsecuencia son ~2~ y ~2~, y los elementos en posiciones pares de la subsecuencia son ~5~ y ~5~)

Una subsecuencia es una secuencia que se puede obtener de otra secuencia eliminando cero o más elementos sin cambiar el orden de los elementos restantes.

Dado que la respuesta puede ser muy grande, imprima el resto de la división por ~1\,000\,000\,007~ ~(10^9+7)~.

Note el límite de memoria inusual.

Subtareas:

• Subtarea 1 (9 puntos): ~a_i \le 2~ para cada ~1 \le i \le n~.

• Subtarea 2 (11 puntos): ~n \le 16~.

• Subtarea 3 (12 puntos): ~n \le 400~.

• Subtarea 4 (28 puntos): Cada número aparece a lo más dos veces en el arreglo.

• Subtarea 5 (40 puntos): Sin restricciones adicionales.

Entrada

La primera línea contiene un entero ~n~ (~2 \leq n \leq 5\,000~) --- el número de elementos en el arreglo ~a~.

La segunda línea consta de ~n~ enteros ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq n~), donde ~a_i~ es el valor del ~i~-ésimo elemento.

Salida

Imprima un único entero en una línea --- el número de subsecuencias de al menos dos elementos en las que todos los elementos en posiciones impares de la subsecuencia son iguales, todos los elementos en posiciones pares de la subsecuencia son iguales, y los dos primeros elementos son diferentes. Dado que puede ser un entero muy grande, imprímalo módulo ~1\,000\,000\,007~.

Ejemplo de entrada 1

4
1 2 1 2

Ejemplo de salida 1

7

Ejemplo de entrada 2

5
1 2 1 1 1

Ejemplo de salida 2

7

Nota

En el primer ejemplo, las subsecuencias que satisfacen todos los requerimientos son:

• ~[\underline{\textbf{1}}, \underline{\textbf{2}}, 1, 2]~
• ~[\underline{\textbf{1}}, \underline{\textbf{2}}, \underline{\textbf{1}}, 2]~
• ~[\underline{\textbf{1}}, \underline{\textbf{2}}, \underline{\textbf{1}}, \underline{\textbf{2}}]~
• ~[\underline{\textbf{1}}, 2, 1, \underline{\textbf{2}}]~
• ~[1, \underline{\textbf{2}}, \underline{\textbf{1}}, 2]~
• ~[1, \underline{\textbf{2}}, \underline{\textbf{1}}, \underline{\textbf{2}}]~
• ~[1, 2, \underline{\textbf{1}}, \underline{\textbf{2}}]~