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

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

Ограничение по времени Ограничение по памяти
2 секунды 64 мегабайта

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

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

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

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

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

Примеры

Вход

abaabaa

Выход

4

Вход

aaaa

Выход

4