[AHOI2013] 差异

题目描述

给定一个长度为 $n$ 的字符串 $S$,令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求 $$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$ 其中,$\text{len}(a)$ 表示字符串 $a$ 的长度,$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

输入输出格式

输入格式


一行,一个字符串 $S$。

输出格式


一行,一个整数,表示所求值。

输入输出样例

输入样例 #1

cacao

输出样例 #1

54

说明

#### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $2\le n\le 500000$,且 $S$ 中均为小写字母。