两位回文串

题目描述

我们定义一个字符串是 两位回文串，当且仅当：

• 这个字符串本身是一个回文串。
• 字符串中所有的字符出现的次数不超过 $2$。

现在，Orange有一个字符串，他想让你统计这个字符串中有多少个子串是二位回文串。

子串(substring)：字符串中连续的一段子序列被称为子串。

回文串：满足正序和逆序形式完全一致的字符串成为回文串。

输入格式

输入一行，包含一个仅有小写字母构成的字符串 $s$。

数据范围:

对于 $30\%$ 的数据，$|s| \le 2000$。 对于所有数据，$|s| \le 10^5$。

输出格式

输出一行，包含一个整数表示答案。

样例 #1

样例输入 #1

ababa

样例输出 #1

8