Problem Description

For a string $S$, we define its value $f(S)$ as the number of characters that appear exactly once in $S$. For example, $f\left({ }^{\prime \prime} \mathrm{aba}{ }^{\prime \prime}\right)=1$, $f\left({ }^{\prime \prime} \mathrm{abc}{ }^{\prime \prime}\right)=3$, and $f\left({ }^{\prime \prime} \mathrm{aaa} \mathrm{a}^{\prime \prime}\right)=0$.

Now given a string $S[0..n-1]$ (with length $n$), please compute the sum of $f(S[i..j])$ over all non-empty substrings $S[i..j]$ $(0 \leq i \leq j < n)$.

Input Format

Input one line containing a string $S$ consisting of lowercase letters.

Output Format

Output an integer representing the answer.

ababc

21

Hint

For $20\%$ of the testdata, $1 \leq n \leq 10$.

For $40\%$ of the testdata, $1 \leq n \leq 100$.

For $50\%$ of the testdata, $1 \leq n \leq 1000$.

For $60\%$ of the testdata, $1 \leq n \leq 10000$.

For all testdata, $1 \leq n \leq 100000$.

Lanqiao Cup 2020, second round provincial contest, Group A Problem H (Group B Problem H).

Translated by ChatGPT 5