Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.
Ограничения: 1 <= N <= 60.
Входные данные
В первой строке записано слово S.
Выходные данные
Вывести одно целое число - количество способов вычёркивания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
A
|
1
|
|
2
|
XYZ
|
3
|