Count Special Substrings in a DNA Sequence

For length 2, the two characters must be equal; for length greater than 2, the first and last characters must be equal and the middle must contain exactly one kind of character. Count all qualifying substrings by index.

输入格式

One line with a lowercase string of length 1..300000.

输出格式

Output a single integer answer.

样例 1

输入：

xyyx

输出：

2

样例 2

输入：

aaaa

输出：

6

样例 3

输入：

aabaa

输出：

3

样例说明

Example 1: yy and xyyx are valid, 2 in total. Example 2: 3 of length 2, 2 of length 3 and 1 of length 4, 6 in total. Example 3: one aa on each side plus aba in the middle, 3 in total.