You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题陈述

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

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

$1 \leq i < j < k \leq |S|$

长度为 $3$ 的字符串 $S_i$, $S_j$, 和 $S_k$ 按此顺序连接而成的字符串是一个回文字符串。

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

输入格式

一个字符串 $S$。

输出格式

一行一个整数表示答案

样例1

input

ABCACC

output

5

样例2

input

OOOOOOOO

output

56

限制与约定

对于 $30\%$ 的数据，$|S| \le$ $100$ 。

对于 $60\%$ 的数据，$|S| \le$ $10^4$ 。

对于 $100\%$ 的数据，$|S| \le$ $10^6$，字符串中均为大写字母。

• 时间限制: $1 s$
• 空间限制: $512 MB$