题目描述

给定一个字符串 $s$。每一对满足 $1 \le l \le r \le |s|$ 的数对 $(l, r)$ 都对应字符串 $s$ 的一个子串：从位置 $l$ 开始、到位置 $r$（含）结束。

定义两个字符串的函数 $F(x, y)$ 如下：找出所有使 $x$ 的对应子串等于字符串 $y$ 的数对 $(l, r)$，把这些数对按第一个数递增排序，则 $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$，求所有属于 $s$ 子串集合的字符串 $x$ 的 $F(s, x)$ 之和。

输入格式

唯一一行包含给定字符串 $s$，只由小写拉丁字母组成（$1 \le |s| \le 10^5$）。

输出格式

输出一个数——所求的和。

aaaa

20

abcdef

21

说明/提示

第一组样例中，$x$ 取 "a"、"aa"、"aaa"、"aaaa" 时函数值分别为 10、6、3、1。

第二组样例中，对每个满足条件的 $x$，函数值都等于 1。