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

Назвемо паліндромом рядок довжиною більше одного символу, який однаково читається як справа наліво, так і зліва направо. Суперпаліндромом будемо називати рядок, який можна представити як конкатенацію одного або кількох паліндромів.

Дано рядок $s$. Знайдіть кількість підрядків у $s$, які є суперпаліндромами.

Вхідні дані

Рядок $s$ складається з послідовності від $1$ до $1000$ малих латинських літер без пробілів.

Вихідні дані

Виведіть одне число — кількість підрядків рядка $s$, які є суперпаліндромами.

Приклади