G. 字符串的 Porder 之和
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个由小写字母组成的字符串 $$$s$$$。对于该字符串，我们记其长度为 $$$|s|$$$，记其反串为 $$$s^R$$$（即将 $$$s$$$ 左右颠倒后得到的字符串）。同时，我们用 $$$\operatorname{prefix}(s, i)$$$ 表示由 $$$s$$$ 的前 $$$i$$$ 个字符组成的子串，用 $$$\operatorname{suffix}(s, i)$$$ 表示由 $$$s$$$ 的后 $$$i$$$ 个字符组成的子串。

在此基础上，我们定义字符串 $$$s$$$ 的 $$$\operatorname{Porder}$$$ 值为满足以下条件的最大整数 $$$i$$$： $$$$$$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$$$$$其中 $$$0 \le i \le |s|$$$。特别地，若不存在正整数满足上述条件，则 $$$\operatorname{Porder}$$$ 值为 $$$0$$$。

字符串 $$$s$$$ 的子串定义为其从第 $$$l$$$ 个字符到第 $$$r$$$ 个字符的连续一段字符序列，其中下标从 $$$1$$$ 开始，满足 $$$1 \le l \le r \le |s|$$$。

现在，请你求出字符串 $$$s$$$ 的所有子串的 $$$\operatorname{Porder}$$$ 值之和。

Input

输入仅一行，包含一个字符串 $$$s$$$ $$$(1 \le |s| \le 10^5)$$$，保证字符串中仅包含小写字母。

Output

输出一行一个整数，表示 $$$s$$$ 的所有子串的 $$$\operatorname{Porder}$$$ 值之和。

Examples
Input
aa
Output
4
Input
abcdba
Output
9
Note

以样例 2 为例：

  • $$$\operatorname{Porder}$$$ 值为 $$$2$$$ 的子串有：$$$\texttt{abcdba}$$$（共 $$$1$$$ 个）。
  • $$$\operatorname{Porder}$$$ 值为 $$$1$$$ 的子串有：$$$\texttt{bcdb}$$$，以及所有长度为 $$$1$$$ 的子串（共 $$$7$$$ 个）。
  • 其余子串的 $$$\operatorname{Porder}$$$ 值均为 $$$0$$$。

因此，所有子串的 $$$\operatorname{Porder}$$$ 值之和为 $$$1 \times 2 + 7 \times 1 + 0 = 9$$$。