Problems
Палиндромы 2
Палиндромы 2
Строка называется \textit{палиндромом}, если она одинаково читается как слева направо, так и справа налево. Например, "\textbf{abba}" - палиндром, а "\textbf{omax}" - нет. Для строки \textbf{α} будем обозначать \textbf{α\[i..j\]} ее подстроку длины\textbf{ j - i + 1} с \textbf{i}-й по \textbf{j}-ю позицию включительно (позиции нумеруются с \textbf{1}).
Для заданной строки \textbf{α} длины \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{5000000}) требуется подсчитать количество \textbf{q} пар \textbf{(i, j)}, \textbf{1} ≤ \textbf{i} < \textbf{j} ≤ \textbf{n}, таких что \textbf{α\[i..j\]} является палиндромом.
\InputFile
Строка \textbf{α} длины \textbf{n}, состоящая из маленьких латинских букв.
\OutputFile
Количество искомых пар \textbf{q}.
Input example #1
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacaba
Output example #1
769
Input example #0
ab
Output example #0
2