题目描述

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

请你求出满足以下条件的整数三元组 $(i,\ j,\ k)$ 的个数。

• $1 \leq i < j < k \leq |S|$。
• 将 $S_i$、$S_j$、$S_k$ 按顺序连接得到的长度为 $3$ 的字符串是回文串。

其中，$|S|$ 表示字符串 $S$ 的长度，$S_x$ 表示 $S$ 的第 $x$ 个字符。

输入格式

输入为标准输入，格式如下：

$S$

输出格式

输出满足条件的三元组个数。

样例 1

输入

ABCACC

输出

5

样例 2

输入

OOOOOOOO

输出

56

样例 3

输入

XYYXYYXYXXX

输出

75

说明/提示

限制

• $S$ 是一个长度不少于 $1$ 且不超过 $2 \times 10^5$ 的大写英文字母字符串。

样例解释 1

$(i,\ j,\ k) = (1,\ 2,\ 4),\ (1,\ 3,\ 4),\ (3,\ 4,\ 5),\ (3,\ 4,\ 6),\ (3,\ 5,\ 6)$ 满足条件。

由 ChatGPT 4.1 翻译