Algoritmos e Estruturas de Dados

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

  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue