Palindrome

Zeichenketten, die man sowohl von links nach rechts als auch von rechts nach links lesen kann und dabei unverändert bleiben, nennt man Palindrome (z. B. radar, madam oder racecar).

Gegeben ist eine Zeichenkette s. Man soll bestimmen, auf wie viele verschiedene Arten man aus s ein Palindrom erhalten kann, indem man Zeichen entfernt. Es ist auch möglich, keine Zeichen zu entfernen, wenn s bereits ein Palindrom ist. Die Reihenfolge, in der Zeichen entfernt werden, spielt dabei keine Rolle.

Eingabe

Die Eingabe enthält den String s (1 ≤ |s| ≤ 60), der aus Großbuchstaben des lateinischen Alphabets besteht.

Ausgabe

Das Programm soll die Anzahl verschiedener Möglichkeiten ausgeben, wie man aus s ein Palindrom erhalten kann.

Beispiele

Erklärung

1. BAOBAB

2. BAOBAB

3. BAOBAB

4. BAOBAB

5. BAOBAB

6. BAOBAB

7. BAOBAB

8. BAOBAB

9. BAOBAB

10. BAOBAB

11. BAOBAB

12. BAOBAB

13. BAOBAB

14. BAOBAB

15. BAOBAB

16. BAOBAB

17. BAOBAB

18. BAOBAB

19. BAOBAB

20. BAOBAB

21. BAOBAB

22. BAOBAB