题目描述

给定一个全部由大写英文字母组成的字符串 $S$。请求出所有满足以下条件的三元组下标 $(i, j, k)$ 的总个数：

• $1 \le i < j < k \le |S|$, 其中 $|S|$ 表示字符串 $S$ 的长度, $S_x$ 表示字符串的第 $x$ 个字符
• 按顺序拼接 $S_i,S_j,S_k$ 后得到的长度为 $3$ 的字符串是回文字符串

也就是统计所有长度为 $3$ 的回文子序列的个数

输入格式

输入一行一个字符串 $S$，全部由大写英文字母组成。

输出格式

输出一个整数，表示满足条件的三元组的总个数。

ABCACC

5

样例 1 解释说明

满足条件的三元组一共有 $5$ 个：$(1,2,4), (1,3,4), (3,4,5), (3,4,6), (3,5,6)$。

OOOOOOOO

56

XYYXYYXYXXX

75

数据规模与约定

对于全部的测试点，保证：

• $1 \le |S| \le 2 \times 10^5$
• $S$ 由大写英文字母组成