题目描述

众所周知，倒着写和顺着写一模一样的字符串我们称为回文串，例如 $\text{tenet}$ 与 $\text{otto}$ 是回文，但 $\text{qop}$ 不是。

令 $f(s)$ 表示将字符串 $s$ 变成回文串的最小操作次数，每次操作你可以选择任意一个字符将其替换成任意一个小写英文字母。

例如 $f(\text{abc}) = 1$ ，因为只需要将第三个字符改成 $\text{a}$ 就能变成回文 $\text{aba}$ 。

现在，给定一个字符串 $s$ ，求它的所有非空子串的 $f$ 值之和，即

\sum_{i=1}^{|s|} \sum_{j=i}^{|s|} f(s[i;j])

其中 $|s|$ 表示字符串 $s$ 的长度， $s[i;j]$ 表示 $s$ 以第 $i$ 个字符开始第 $j$ 个字符结束（包括开始和结束字符）的子串。

输入格式

从 subpalin.in 文件中读取数据

输入一行字符串 $s$ 。

将数据输出到 subpalin.out 文件中

输出一个整数表示答案。

abbaa

madamineden