给你一个字符串 s。满足条件 1 ≤ l ≤ r ≤ |s| 的每对数字 l 和 r 对应于字符串 s 的一个子串,从位置 l 开始,到位置 r 结束(含)。
让我们像这样定义两个字符串 F(x, y) 的函数。我们将找到这样的数字对的列表,其中字符串 x 的相应子字符串等于字符串 y。让我们根据对的第一个数字的递增对这个对列表进行排序。函数 F(x, y) 的值等于列表中非空连续序列的数量。
例如:F(babbabbababbab, babb) = 6。配对列表如下:
(1, 4), (4, 7), (9, 12)
其连续序列为:
- (1, 4)
- (4, 7)
- (9, 12)
- (1, 4), (4, 7)
- (4, 7), (9, 12)
- (1, 4), (4, 7), (9, 12)
你的任务是计算给定字符串 s 的所有 x 的总和 F(s, x),即 x 属于字符串 s 的所有子字符串的集合。
输入
唯一一行包含给定的字符串 s,仅由小拉丁字母组成 (1 ≤ |s| ≤ 105)。
输出
打印单个数字 — 求和。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。
示例
输入 #1
aaaa
输出 #1
20
输入 #2
abcdef
输出 #2
21
输入 #3
abacabadabacaba
输出 #3
188
注意
在第一个样本中,x 处的函数值等于“a”、“aa”、“aaa”和“aaaa”,相应地等于 10、6、3 和 1。
在第二个样本中,对于任何满足 x 的函数值为 1。