### Cursor Distance

There is a string $$s$$ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $$c$$ and a direction (left or right). The cursor is then moved to the closest occurence of $$c$$ in the chosen direction. If there is no letter $$c$$ in that direction, the cursor stays in place. For example, if $$s =$$ abaab with the cursor on the second character (a[b]aab), then:

• moving to the closest letter a to the left places the cursor on the first character ([a]baab);
• moving to the closest letter a to the right places the cursor the third character (ab[a]ab);
• moving to the closest letter b to the right places the cursor on the fifth character (abaa[b]);
• any other operation leaves the cursor in place.
Let $$\mathrm{dist}(i, j)$$ be the smallest number of operations needed to move the cursor from the $$i^{th}$$ character to the $$j^{th}$$ character. Compute $$\displaystyle \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\mathrm{dist}(i, j)}}$$.

### Input format

The only line contains a non-empty string $$s$$ of $$n \leq 10^5$$ lowercase English letters.

### Output format

Print a single integer $$\displaystyle \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\mathrm{dist}(i, j)}}$$.

### Limits

Subtask # Score Constraints
1 6 $$n \leq 200$$
2 12 $$n \leq 2000$$
3 14 $$s$$ contains only letters a and b.
4 18 $$s$$ contains only letters a to e.
5 50 No additional constraints

### Samples

 Sample Input 1 Sample Output 1 abcde 20

$$\mathrm{dist}(i, j) = 0$$ for any pair $$i = j$$, and $$1$$ for all other pairs.

 Sample Input 2 Sample Output 2 abacaba 58

### Compile Errors

Time Limit: 3 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: Codeforces 1246F