F. Подпалиндромы

Сколько подстрок данной строки являются палиндромами? Одинаковые подстроки на разных местах считаются разными.

Палиндромов может быть до $\frac{n(n+1)}{2}$ - у строки из одинаковых букв палиндром вообще любая подстрока. Значит, перечислять их нельзя, надо считать.

Наивный способ - для каждого центра расходиться в обе стороны - стоит $O(n^2)$: на строке из $10^5$ одинаковых букв это $2{,}5 \cdot 10^9$ сравнений, и в лимит он не укладывается. Такой тест в наборе есть.

Одна строка длины $n$ ($1 \le n \le 10^5$) из строчных латинских букв.

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