[AHOI2013]差异

题号：NC19894
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的字符串 SS，令 T_i 表示它从第 i 个字符开始的后缀。求

$\sum_{1\leq i<j\leq n}^{}{len(T_i)+len(T_j)-2 \times lcp(T_i,T_j)}$

其中，len(a) 表示字符串 a 的长度，lcp(a,b) 表示字符串 a 和字符串 b 的最长公共前缀。

一行，一个字符串S

一行，一个整数，表示所求值

示例1

复制

cacao

复制

对于100%的数据，保证，且中均为小写字母。