Sum of Substring Values

Problem Description

For a string $S$, we define $f(S)$ as the number of distinct characters that appear in $S$. For example $f(aba) = 2$, $f(abc) = 3$, $f(aaa) = 1$.

Now you are given a string $S$ (suppose its length is $len$). Please compute $\sum\limits_{i=0}^{len-1} \sum\limits_{j=i}^{len-1} f(S[i:j])$.

Input Format

One line containing a string $S$ consisting of lowercase letters.

Output Format

Output one integer, the answer.

Sample Input

ababc

Sample Output

28

Constraints

For all data, the string length $len \leq 1\,000\,000$, and string indices run from $0$ to $len-1$.