子串分值和

题目描述

对于一个字符串 $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$。