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...z.

Output

Print one integer: the number of special substrings.

Constraints

• $1 \le n \le 2 \cdot 10^5$

Example

Input:

abccabab

Output:

5

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