Descripción

Dado una cadena $S$ de longitud $2N$ que contiene solo letras minúsculas del alfabeto en inglés.

Hay $2^{2N}$ formas de colorear cada caracter de la cadena $S$ de rojo o azul. De esas posibles formas, ¿Cuántas satisfacen la siguiente condición?

• La cadena obtenida al leer los caracteres pintados de rojo de izquierda a derecha es igual a la cadena obtenida al leer los caracteres pintados de azul de derecha a izquierda.

Entrada

La primera línea de la entrada contiene un entero $N$ ($1\le N\le 18$).

La segunda línea de la entrada contiene una cadena de caracteres de longitud $2N$.

Salida

Imprime una línea con la cantidad de formas, de pintar la cadena, que satisfacen la condición.

Subtareas

• Subtarea 1: $1\le N\le 12$ ($35$ puntos)
• Subtarea 2: Sin restricciones adicionales ($65$ puntos)

Ejemplos

Entrada 1

4
cabaacba

Salida 1

4

Las cuatro formas válidas de colorear la cadena son:

• cabaacba
• cabaacba
• cabaacba
• cabaacba

Entrada 2

11
mippiisssisssiipsspiim

Salida 2

504

Entrada 3

4
abcdefgh

Salida 3

0

Entrada 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Salida 4

9075135300