Analyze Product Code (Valid Substrings)

The string contains only a..g. Count the non-empty contiguous substrings in which the highest character frequency does not exceed the number of distinct characters.

输入格式

A single line containing a string over a..g, of length 1..100000.

输出格式

Output a single integer answer.

样例 1

输入：

abaa

输出：

8

样例 2

输入：

a

输出：

1

样例 3

输入：

abc

输出：

6

样例说明

Example 1: the four single characters, the two length-2 substrings ab and ba, and the two length-3 substrings aba and baa are valid, 8 in total; aa and abaa are not valid. Example 2: a single character has frequency 1 and 1 distinct character, so it is valid. Example 3: all six non-empty substrings are valid.