题目描述

满足以下条件的由英文小写字母组成的字符串称为好字符串。

• 通过改写不超过 1 个字符可以使其变为回文。

例如 a、iwai、abcdcza 是好字符串，但 abcd、atcoder 不是好字符串。特别地，回文本身也是好字符串。

给定一个由英文小写字母组成的字符串 $S$。

求 $S$ 的非空子串（连续子序列）中是好字符串的个数。

注意：两个子串如果在 $S$ 中取出的位置不同，即使作为字符串相同也视为不同，需要分别计数。

子串是什么：$S$ 的子串是指从 $S$ 的开头删除 $0$ 个以上字符、从末尾删除 $0$ 个以上字符后得到的字符串。
例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

输入按以下格式从标准输入给出。

$S$

输出格式

输出答案。

输入输出样例 #1

输入 #1

ababa

输出 #1

13

输入输出样例 #2

输入 #2

atcoder

输出 #2

18

输入输出样例 #3

输入 #3

abccbacbacb

输出 #3

40

说明/提示

样例解释 1

$S$ 中从第 $2$ 个字符到第 $3$ 个字符的 ba、从第 $1$ 个字符到第 $5$ 个字符的 ababa 等都是好字符串。

好字符串共有 $13$ 个，在总共 $15$ 个子串中，除了从第 $1$ 个字符到第 $4$ 个字符的 abab 和从第 $2$ 个字符到第 $5$ 个字符的 baba 以外的 $13$ 个都是。

约束条件

• $S$ 是由英文小写字母组成的长度在 $1$ 以上 $10^4$ 以下的字符串。