题目背景

梦云觉得一场比赛不能没有披萨于是披萨又回来啦！ :)

题目描述

梦云有一串披萨，用一个字符串 $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$ 和 $2 \cdot 10^5$之间。

输出格式

一个整数, 表示答案。

样例

ABCACC

5

所有满足条件的回文披萨为$(i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6)$

OOOOOOOO

56

XYYXYYXYXXX

75