Problem Description

A string $s$ is defined to be good if and only if all characters contained in it appear the same number of times.

Examples of good strings: mama, aabbcbcccbaa.

Examples of bad strings: ovo.

Given a string $s$, find the number of good substrings of $s$.

Input Format

One line containing a string $s$.

Output Format

One line containing an integer, representing the required value.

aabbabcccba

28

Hint

For $100\%$ of the testdata, $1 \leq |s| \leq 3 \times 10^5$, and $s$ contains only the three lowercase letters a, b, c.

Translated by ChatGPT 5