Районная олимпиада по информатике. 2014-2015 учебный год. 10-11 классы

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

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

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

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

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

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

Примеры:

Вход

abaabaa

Ответ

4

Вход

aaaa

Ответ

4

Замечание

abaabaa, abaabaa, abaabaa, abaabaa
aaaa, aaaa, aaaa, aaaa