对于一个字符串 $S$ ,我们定义 $f(S)$ 为 $S$ 中出现的不同的字符个数。 例如 $f(aba) = 2, f (abc) = 3, f (aaa) = 1$。
现在给定一个字符串 $S$ (假设长度为 $len$),请你计算 $\sum\limits_{i=0}^{len-1} \sum\limits_{j=i}^{len-1} f(S[i:j])$ 。
输入格式
输入一行包含一个由小写字母组成的字符串 $S$ 。
输出格式
输出一个整数表示答案。
样例输入
ababc
样例输出
28
数据规模
所有数据保证字符串长度 $len \leq 1000000$,字符串下标从 $0$ 到 $len-1$。