题目描述

对于一个字符串 $S$，我们定义 $S$ 的分值 $f(S)$ 为 $S$ 中恰好出现一次的字符个数。例如 $f(aba)=1，f(abc)=3，f(aaa)=0$。

现在给定一个字符串 $S_{0⋯n−1}$（长度为 $n，1≤n≤10^5$），请你计算对于所有 $S$ 的非空子串 $S_{i⋯j}(0≤i≤j<n)，f(S_{i⋯j})$ 的和是多少。

输入描述

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

输出描述

输出一个整数表示答案。

ababc

21

样例说明

子串  f值
a      1
ab     2
aba    1
abab   0
ababc  1
b      1
ba     2
bab    1
babc   2
a      1
ab     2
abc    3
b      1
bc     2
c      1

评测用例规模与约定：

对于 20% 的评测用例，$1 \leq n \leq 10$。

对于 40% 的评测用例，$1 \leq n \leq 100$。

对于 50% 的评测用例，$1 \leq n \leq 1000$。

对于 60% 的评测用例，$1 \leq n \leq 10000$。

对于所有评测用例，$1 \leq n \leq 100000$。