Migrated from Lutece 2644 友好回文串

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

若一个字符串翻转后等于自身，则称之为回文串。

两个回文串的友好值为 $x$，是指存在一个长度为 $x$ 的回文串，是这两个回文串的公共前缀。且不存在长度大于 $x$ 的回文串，是这两个回文串的公共前缀。

给出一个字符串 $S$。求 $S$ 的所有回文子串（出现位置不同但相等的回文串视为同一个回文子串）两两友好值之和。

Input

仅一行，字符串 $S$。$S$ 仅包含小写字母。

Output

仅一行，表示友好值之和。

Samples

aba

1

aabaa

7

Constraints

$1 \le |S| \le 5\times 10^5$

Note

对于样例 2，$S$ 的所有回文子串为 $\{\texttt a,\texttt{aa},\texttt b,\texttt{aba},\texttt{aabaa}\}$。

$$\begin{aligned} (\texttt a,\texttt{aa})=1\\ (\texttt a,\texttt b)=0\\ (\texttt a,\texttt{aba})=1\\ (\texttt a,\texttt{aabaa})=1\\ (\texttt{aa},\texttt b)=0\\ (\texttt{aa},\texttt{aba})=1\\ (\texttt{aa},\texttt{aabaa})=2\\ (\texttt b,\texttt{aba})=0\\ (\texttt b,\texttt{aabaa})=0\\ (\texttt{aba},\texttt{aabaa})=1 \end{aligned} $$

总和为 $7$。

Resources

2021 UESTC ICPC Training for String and Search Algorithm