题目描述

若一个由小写英文字母组成的字符串满足下面的条件，就称它是好串：

• 最多改写其中 $1$ 个字符，就能把它变成回文串。

例如 a、iwai、abcdcza 都是好串，而 abcd、atcoder 不是。特别注意：回文串本身也是好串（改写 $0$ 个字符即可）。

给定一个由小写英文字母组成的字符串 $S$，请求出 $S$ 的非空子串（连续的一段）中，有多少个是好串。

两个子串只要在 $S$ 中的位置不同，即使内容相同也要分别计数。

什么是子串？

$S$ 的子串是指从 $S$ 的开头删去 $0$ 个或多个字符、从结尾删去 $0$ 个或多个字符后得到的字符串。例如 ab 是 abc 的子串，而 ac 不是。

输入格式

S

输出格式

输出好串的个数。

输入示例 1

ababa

输出示例 1

13

示例 1 说明

$S$ 长度为 $5$，一共有 $\dfrac{5 \times 6}{2} = 15$ 个非空子串。

其中不是好串的只有两个：第 $1 \sim 4$ 位的 abab 和第 $2 \sim 5$ 位的 baba（它们都需要改写 $2$ 个字符才能变成回文）。

所以答案是 $15 - 2 = 13$。

输入示例 2

atcoder

输出示例 2

18

示例 2 说明

长度为 $1$ 的子串（$7$ 个）全是回文；长度为 $2$ 的子串（$6$ 个）最多改一个字符就能变回文，也全是好串。再加上若干更长的好串，合计 $18$ 个。

这提示我们：长度 $\le 2$ 的子串一定是好串。

输入示例 3

abccbacbacb

输出示例 3

40

示例 3 说明

$S =$ abccbacbacb 长度为 $11$，非空子串共 $\dfrac{11 \times 12}{2} = 66$ 个，其中好串有 $40$ 个。

例如第 $1 \sim 5$ 位的 abccb 只要把最后一位改成 a 就成了回文 abcba，是好串；而第 $1 \sim 7$ 位的 abccbac 有两对对称位置不匹配，改一个字符不够，不是好串。

约束条件

• $S$ 是由小写英文字母组成的字符串，长度在 $1$ 到 $10^4$ 之间