e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Палиндромы

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево.

Имеется слово s, состоящее из n прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить палиндром. Найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

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

Одно слово s длины n (1n60).

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

Вывести одно целое число - количество способов вычёркивания.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
BAOBAB
Выходные данные #1
22