#P7174. [PA 2021]Zbalansowane słowa

    ID: 7005 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-全子集枚举一维前缀和状态编码

[PA 2021]Zbalansowane słowa

Description

定义一个字符串是好的,当且仅当它包含的所有字符出现次数相同。
好的字符串的例子有 mama\textbf{mama},aabbcbcccbaa\textbf{aabbcbcccbaa},不好的字符串的例子有 ovo\textbf{ovo}。
给定一个长度为 nn 的字符串 ss,求出 ss 有多少个连续子序列是好的。

Format

Input

一行一个长度为 nn 的字符串 ss,保证出现的字符都是 a\texttt{a}、b\texttt{b}、c\texttt{c}。

Output

一行一个整数 ans\textbf{ans},表示答案。

Samples

aabbabcccba
28

hint

n≤300000n \leq 300000