Palíndromos
Strings que se leem da mesma forma da esquerda para a direita e da direita para a esquerda são chamadas de palíndromos (radar, madam, ou racecar).
Dada uma string s, pretende-se descobrir quantas formas distintas se podem obter um palíndromo a partir de s removendo caracteres. É possível não remover nenhum caractere e, ainda assim, formar um palíndromo. A ordem em que os caracteres são removidos não influencia o resultado final.
Entrada
A entrada contém a string s (1 ≤ |s| ≤ 60), composta por letras maiúsculas do alfabeto latino.
Saída
O programa deve mostrar o número de formas diferentes de obter um palíndromo a partir de s.
Exemplos
Input | Output |
|---|---|
BAOBAB | 22 |
Explicação
BAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB