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

Суперпалиндромы

Суперпалиндромы

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

Назовём палиндромом строку длиной более одного символа, которая одинаково читается как справа налево, так и слева направо. Назовём суперпалиндромом строку, которая может быть представлена как конкатенация одного или более палиндромов. Дана строка S. Необходимо найти количество подстрок в S, которые являются суперпалиндромами.

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

Строка S содержит последовательность от 1 до 1000 строчных латинских букв без пробелов.

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

Выведите одно число - количество подстрок S, являющихся суперпалиндромами.

Пример

Входные данные #1
abc
Выходные данные #1
0
Входные данные #2
abacdc
Выходные данные #2
3