问题描述

给你一个由大写英文字母组成的字符串 $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$ 和 $2×10^5$ （含）之间的字符串，由大写英文字母组成。

输入

输入来自标准输入，格式如下:

$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