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
BAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBABBAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB