You have a string S, but you like only special strings. So, you have to calculate the total number of special substrings in S.

A string T, of length L, is called special string, if either of the following property holds:

1. All characters of the string T are same. for example, $aaa$
2. The string has an odd length (i.e, L is odd) and all characters of T are same except the middle character, for example, $aabaa$.

Count the total number of special substrings in S.

Input constraints:

• String S contains only lower-case English alphabets.
• $1 \le|S| \le10^{6}$, where |S| is the length of string S.