Score : $400$ points

问题陈述

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

找出满足以下两个条件的整数三元组 $(i, j, k)$ 的数量：

• $1 \leq i < j < k \leq |S|$
• 按照 $S_i$、$S_j$ 和 $S_k$ 的顺序连接形成的三字符长度字符串是一个回文。

这里，$|S|$ 表示 $S$ 的长度，$S_x$ 表示 $S$ 的第 $x$ 个字符。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

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

Find the number of integer triples $(i, j, k)$ satisfying both of the following conditions:

• $1 \leq i < j < k \leq |S|$
• The length-$3$ string formed by concatenating $S_i$, $S_j$, and $S_k$ in this order is a palindrome.

Here, $|S|$ denotes the length of $S$, and $S_x$ denotes the $x$-th character of $S$.

Constraints

• $S$ is a string of length between $1$ and $2 \times 10^5$, inclusive, consisting of uppercase English letters.

Input

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

$S$

Output

Print the answer.

Sample Input 1

ABCACC

Sample Output 1

5

The triples satisfying the conditions are $(i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6)$.

Sample Input 2

OOOOOOOO

Sample Output 2

56

Sample Input 3

XYYXYYXYXXX

Sample Output 3

75