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

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

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

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

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

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

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

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

Примеры

Вход

abaabaa

Выход

4

Вход

aaaa

Выход

4