eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Палиндромы

Палиндромы

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, "abba" - палиндром, а "omax" - нет. Для строки α будем обозначать α[i..j] ее подстроку длины j - i + 1 с i-ой по j-ую позицию включительно (позиции нумеруются с 1).

Для заданной строки α длины n вычислите количество q пар (i, j), 1i < jn, таких что α[i..j] является палиндромом.

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

Строка α длины n (1n10^5), состоящая из маленьких латинских букв.

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

Количество искомых пар q.

Пример

Входные данные #1
aaa
Выходные данные #1
3
Входные данные #2
abba
Выходные данные #2
2
Входные данные #3
omax
Выходные данные #3
0