Balance is the most important thing everywhere. It is especially important when organizing programming contests, and we hope that the jury of this year's Potyczki Algorytmiczne is well aware of this.
We say that a word is balanced if every letter that appears in it appears the same number of times. For example, the words w, mama, potyczki, and aabbcbcccbaa are balanced, while the words oko, algorytmistrz, and abcba are not. Given a long word consisting only of the characters a, b, and c, count how many of its non-empty substrings (i.e., contiguous segments of letters) are balanced.
Note: Two identical words appearing as substrings at different positions are counted multiple times. For example, in the word oko, the balanced substrings are o, k, o, ok, and ko.
Input
The first line of input contains a non-empty word with a length not exceeding 300,000, consisting only of the characters a, b, and c.
Output
The output should contain a single integer representing the number of balanced substrings of the input word.
Examples
Input 1
aabbabcccba
Output 1
28
Note 1
The balanced substrings are: a, aa, aabb, aabbab, aabbabccc, ab, abba, abc, b, ba, bb, bc, c, cb, cba, cc, ccc. Note that some of them appear multiple times.
Subtasks
- In some test groups, the length of the input word does not exceed 100.
- In other test groups, the length of the input word does not exceed 3000.
In both of the above cases, there is at least one such group.