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

问题描述

给定一个由大写英文字母组成的字符串 $S$，计算满足以下条件的三元组 $(i, j, k)$ 的个数：

1. $1 \leq i < j < k \leq |S|$
2. $S_i$, $S_j$, $S_k$ 按顺序组成的字符串是回文串，即 $S_i = S_k$。

输入格式

输入一行字符串 $S$。

• $|S|$ 是字符串 $S$ 的长度，满足 $1 \leq |S| \leq 200,000$。

输出格式

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

样例

ABCACC

5

OOOOOOOO

56

XYYXYYXYXXX

75

解释 满足条件的三元组为：

• $(1, 2, 4)$: "ABA"
• $(1, 3, 4)$: "ACA"
• $(3, 4, 5)$: "CAC"
• $(3, 4, 6)$: "CAC"
• $(3, 5, 6)$: "CAC"