AT_abc468_d.Pre-Palindrome

A string consisting of lowercase English letters is called a good string if it satisfies the following condition.

• It can be turned into a palindrome by rewriting at most one character.

For example, a, iwai, and abcdcza are good strings, but abcd and atcoder are not good strings. Note that, in particular, a palindrome is also a good string.

You are given a string $S$ consisting of lowercase English letters.

Find the number of non-empty substrings (contiguous subsequences) of $S$ that are good strings.

Two substrings taken from different positions of $S$ are counted separately even if they are equal as strings.

What is a substring?

A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, ab is a substring of abc, but ac is not a substring of abc.

仅由小写英文字母组成的字符串被称为好字符串，当且仅当它满足以下条件：

• 最多修改一个字符，即可将其变为回文串。

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

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

请计算 $S$ 的非空子串（连续子序列）中，有多少个是好字符串。

即使两个子串作为字符串内容相同，只要它们在 $S$ 中起始或结束位置不同，就视为不同的子串，需分别计数。

什么是子串？

字符串 $S$ 的一个子串是指：从 $S$ 的开头删除零个或多个字符，再从 $S$ 的末尾删除零个或多个字符后所得到的字符串。
例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

The input is given from Standard Input in the following format:

$S$

输入从标准输入中以如下格式给出：

$S$

Output the answer.

输出答案。

Sample 1 Explanation:
The substring ba from the $2$nd through $3$rd characters of $S$ and the substring ababa from the $1$st through $5$th characters are some good strings.

Among the $15$ substrings, the good strings are the $13$ substrings other than abab from the $1$st through $4$th characters and baba from the $2$nd through $5$th characters.

Constraints

• $S$ is a string of length between $1$ and $10^4$, inclusive, consisting of lowercase English letters.

样例 1 解释：
字符串 $S$ 中第 $2$ 至第 $3$ 个字符构成的子串 ba，以及第 $1$ 至第 $5$ 个字符构成的子串 ababa 均为“好字符串”。

在全部 $15$ 个子串中，“好字符串”共有 $13$ 个，即除去以下两个子串：第 $1$ 至第 $4$ 个字符构成的 abab，以及第 $2$ 至第 $5$ 个字符构成的 baba。

约束条件

• $S$ 是一个长度在 $1$ 到 $10^4$（含）之间的字符串，仅由小写英文字母组成。