题目描述

给定一个由大写英文字母组成的字符串 $S$。求满足以下所有条件的 $S$ 的子串(连续子序列)的数量:

• 子串由奇数个字符组成。
• 子串的正中央字符是 C。严格地说,若子串由 $l$ 个字符组成,则其第 $\frac{l+1}{2}$ 个字符是 C。

注意:即使两个子串作为字符串相同,只要它们抽取自不同位置,就分别计数。

输入格式

S

输出格式

输出答案。

数据范围

• $S$ 是由大写英文字母组成的字符串。
• $1 \leq |S| \leq 5 \times 10^5$

样例 1 输入

ABCCA

样例 1 输出

5

满足条件的 $5$ 个子串为:

• 第 $1$ - $5$ 字符:ABCCA(中心 = 第 $3$ 字符 = C)
• 第 $2$ - $4$ 字符:BCC(中心 = 第 $3$ 字符 = C)
• 第 $3$ - $3$ 字符:C
• 第 $3$ - $5$ 字符:CCA(中心 = 第 $3$ 字符 = C)
• 第 $4$ - $4$ 字符:C

样例 2 输入

XYZ

样例 2 输出

0

样例 3 输入

SMBCPROGRAMMINGCONTEST

样例 3 输出

11