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