Palindromi
Le stringhe che si leggono allo stesso modo da sinistra a destra e da destra a sinistra sono chiamate palindromi (ad esempio: radar, madam o racecar).
Data una stringa
s, è richiesto di determinare il numero di modi diversi in cui si può ottenere un palindromo partendo da s, rimuovendo alcuni caratteri. È anche possibile non rimuovere alcun carattere e ottenere comunque un palindromo. L’ordine con cui vengono rimossi i caratteri non è rilevante.Ingresso
L’input contiene la stringa
s (1 ≤ |s| ≤ 60), composta da lettere maiuscole dell’alfabeto latino.Uscita
Il programma deve stampare il numero di modi diversi per ottenere un palindromo a partire da
s.Esempi
Input | Output |
BAOBAB | 22 |
Spiegazione
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB