Palíndromos
Las cadenas (strings) que se leen igual de izquierda a derecha y de derecha a izquierda se llaman palíndromos (radar, madam o racecar).
Dada una cadena s, se solicita determinar cuántas maneras distintas existen de obtener un palíndromo a partir de s eliminando caracteres. Es posible no eliminar ningún carácter y aun así obtener un palíndromo. El orden en el que se eliminan los caracteres no afecta el resultado.
Entrada
La entrada contiene la cadena s (1 ≤ |s| ≤ 60), compuesta por letras mayúsculas del alfabeto latino.
Salida
El programa debe imprimir la cantidad de formas distintas de obtener un palíndromo a partir de s.
Ejemplos
Entrada | Salida |
|---|---|
BAOBAB | 22 |
Explicación
BAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB