90032 - 子串分值

通过次数

9

提交次数

10

时间限制 : 1 秒
内存限制 : 128 MB

对于一个字符串S,我们定义S 的分值f(S) 为S 中恰好出现一次的字符个数。 
例如f(“aba”) = 1,f(“abc”) = 3,f(“aaa”) = 0。 
现在给定一个字符串S[0 · · · n−1](长度为n),请你计算对于所有S的非空子串S[i · · · j](0 ≤ i ≤ j < n),f(S[i · · · j]) 的和是多少。

输入

输入一行包含一个由小写字母组成的字符串S。

对于20% 的评测用例,1 \le n \le 10
对于40% 的评测用例,1 \le n \le 100
对于50% 的评测用例,1 \le n \le 1000
对于60% 的评测用例,1 \le n \le 10000
对于所有评测用例,1 \le n \le 100000

输出

输出一个整数表示答案。

样例

输入

ababc

输出

21