题目描述

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

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

输入描述

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

其中，$1≤n≤10^5$。

输出描述

输出一个整数表示答案。

ababc

28

样例说明

子串  f值
a      1
ab     2
aba    2
abab   2
ababc  3
b      1
ba     2
bab    2
babc   3
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$。