Районная олимпиада по информатике 2015 года за 11 класс | Казахстанские олимпиады

Задача F. Четный палиндром

Подстрокой строки называется любая непустая последовательность символов в строке. Палиндромом называется строка, которая читается одинаково слева и справа. У Азизхана есть строка $S.$ Его интересует сколько есть подстрок четной длины у строки $S,$ которые являются палиндромами. Одинаковые подстроки начинающие с разных позиций считаются разными.

Формат входного файла

Единственная строка входного файла содержит одну строку $S$ состоящее из строчных букв английского алфавита ($1 \le$ длина $S \le 10^5$).

Формат выходного файла

Выведите ответ к задаче.

Примеры

Вход

abaabaa

Выход

4

Вход

aaaa

Выход

4