Палиндромы

Строки, которые одинаково читаются слева направо и справа налево, называются палиндромами (например, radar, madam или racecar).

По заданной строке s необходимо определить, сколько существует различных способов получить из неё палиндром, удаляя символы. При этом можно вообще не удалять символы, если строка уже является палиндромом. Порядок, в котором удаляются символы, не имеет значения.

Входные данные

Во входных данных содержится строка s (1 ≤ |s| ≤ 60), состоящая из прописных латинских букв.

Выходные данные

Программа должна вывести количество различных способов получить палиндром из s.

Примеры

Пояснение

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