A substring is called special if every character that appears in the string appears the same number of times in the substring.

Your task is to count the number of special substrings in a given string.

Input

• The only input line has a string of length \(n\). Every character is between a\(\dots\)z.

Output

• Print one integer: the number of special substrings.

Constraints

• \(1 \leq n \leq 2\cdot10^5\)

Example

Sample input

abccabab

Sample output

5

Note

The special substrings are abc, cab, abccab, bccaba and ccabab.