ABA

题目描述

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

求同时满足以下两个条件的整数三元组 $(i, j, k)$ 的个数:

• $1 \le i \lt j \lt k \le |S|$
• 按顺序拼接 $S_i$、$S_j$、$S_k$ 得到的长为 $3$ 的字符串是回文串。

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

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出答案。

样例

ABCACC

5

满足条件的三元组为 $(i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6)$。

OOOOOOOO

56

XYYXYYXYXXX

75

数据范围

• $S$ 是长度在 $1$ 到 $2 \times 10^5$ 之间(含端点)的字符串,由大写英文字母组成。