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

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

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

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

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

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