该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述

给定一个只包含大写字母的字符串 $S$，求满足以下条件的三元组 $(i,j,k)$ 的个数：

• $1 \leq i < j < k \leq |S|$
• 由 $S_i$、$S_j$、$S_k$ 按顺序组成的字符串是回文串。

其中，$|S|$ 指的是 $S$ 的长度，$S_x$ 指的是 $S$ 中的第 $x$ 个字符。

数据约束

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

输入格式

一行包括一个字符串 $S$。

输出格式

输出一个整数，表示满足条件的三元组 $(i,j,k)$ 的个数。

样例

ABCACC

5

OOOOOOOO

56

XYYXYYXYXXX

75

样例解释 #1

对于输入字符串 ABCACC，符合条件的三元组 $(i,j,k)$ 为：

• $(1, 2, 4)$ 对应的子串是 ABA（回文）
• $(1, 3, 4)$ 对应的子串是 ACA（回文）
• $(3, 4, 5)$ 对应的子串是 CAC（回文）
• $(3, 4, 6)$ 对应的子串是 CAC（回文）
• $(3, 5, 6)$ 对应的子串是 ACC（回文）

因此，输出为 5。