fateice 喜欢串串，尤其喜欢双回文串。

如果你不知道啥是双回文串，一个串 $s$ 是双回文串当且仅当存在非空的回文串 $a$ 和 $b$ 满足 $s$ 由 $a$ 和 $b$ 拼接而成。例如，$aabcb$ 为双回文串，而 $aba$ 不是双回文串。

一天 fateice 看到了一个新鲜的字符串 $s$，他把 $s$ 的所有本质不同的子串列举了出来，并且数出了其中的双回文串个数。两个字符串本质不同当且仅当它们的长度不同或存在一个下标它们对应位置的字符不同。

fateice 当然飞快地报出了答案，但是他想考考你。

输入格式

从标准输入读入数据。

一行一个非空字符串 $s$。保证由小写字母组成。

输出格式

输出到标准输出中。

输出一行一个整数表示 $s$ 中本质不同的双回文串子串个数。

样例一

input

abbbab

output

11

explanation

$s$ 中本质不同的双回文子串有：ab,abb,abbb,abbbab,ba,bb,bba,bbab,bbb,bbba,bbbab，共11个。

样例二

input

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

output

233

explanation

稍有常识的人...

样例三

input

abbbbaaabbbabbabbbabaababbaaababbcbbbbbaabbcbbaabbaabbbbabaabbbabbbbbaaaaabbbbbcbbbbababcaabbabcabbabaaababbbaaaabbcbcbaabbbbbabbbbbaababaababaaaabbbabaabbabaacaabaaaababbaaaaababbbbbabbaabbaabbaaabbbabaabbabaaabbabaabbbbbbababcaabbabababbbbbabbaaaaacbbaabbbaabbacbbbaacabbbabcaacbbbabaaaabbbaaababbb

output

614

explanation

我有一个绝妙的解释，可是这里空间太小写不下。

限制与约定

对于所有数据，满足 $1 \leq |s| \leq 5 \times 10^5$。

共有6个子任务，每个子任务的特殊限制和分值如下：

1. (10分) $|s| \leq 300$。
2. (20分) $|s| \leq 5000$。
3. (20分) $|s| \leq 40000$。
4. (20分) $|s| \leq 1.5 \times 10^5$。
5. (10分) $s$ 仅由 $\{a,b\}$ 组成并且每个字符在 $\{a,b\}$ 中等概率随机。
6. (20分) 没有附加限制。

时间限制： $\texttt{5s}$

空间限制： $\texttt{2048MB}$

下载

样例数据下载