SPOJ in Gyumri

   Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Путем вычеркивания из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованные таким образом строки являлись палиндромами. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми. Палиндромы, образованными даже одинаковыми буквами, стоящими на разных позициях исходной строки, считаются различными.

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

   Записано слово S (1 ≤ N ≤ 60).

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

   Одно целое число – число способов получения палиндромов путем вычеркивания.

Пример.