描述

对于一个字符串S，如果某个字符在S中只出现了一次，我们就称这个字符是“孤独”的。

我们用f(S)表示S中孤独的字符的数量，称为S的"孤独值"。  

现在给定一个字符串T，请你计算T的所有子串的孤独值之和。  

例如对于T="hih"，T的所有子串一共有6个："h", "i", "h", "hi", "ih", "hih"。 (注：两个"h"因为位置不同，算作不同的子串)

f("h") = 1

f("i") = 1  

f("h") = 1

f("hi") = 2  

f("ih") = 2  

f("hih") = 1

和为8。

输入 一个字符串T，只包含小写字母。 对于30%的数据，1 ≤ |T| ≤ 100 对于70%的数据，1 ≤ |T| ≤ 1000 对于100%的数据，1 ≤ |T| ≤ 100000 输出 一个整数表示答案 样例输入

hih

样例输出

8

来源 张老师和杜老师编程课改编