CF123D.String

You are given a string s. Each pair of numbers l and r that fulfill the condition 1 ≤ l ≤ r ≤ |s|, correspond to a substring of the string s, starting in the position l and ending in the position r (inclusive).

Let's define the function of two strings F(x, y) like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string x are equal to string y. Let's sort this list of pairs according to the pair's first number's increasing. The value of function F(x, y) equals the number of non-empty continuous sequences in the list.

For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

• (1, 4)
• (4, 7)
• (9, 12)
• (1, 4), (4, 7)
• (4, 7), (9, 12)
• (1, 4), (4, 7), (9, 12)

Your task is to calculate for the given string s the sum F(s, x) for all x, that x belongs to the set of all substrings of a string s.

给你一个字符串 $s$。每一对满足条件 $1 ≤ l ≤ r ≤ |s|$ 的数 $l$ 和 $r$，对应字符串 $s$ 的一个子串，该子串起始于位置 $l$、终止于位置 $r$（包含端点）。

我们定义关于两个字符串的函数 $F(x, y)$ 如下：我们找出所有满足“字符串 $x$ 中对应位置的子串等于字符串 $y$”的数对 $(l, r)$ 构成的列表；然后将该列表中的数对按第一个数 $l$ 升序排序。函数 $F(x, y)$ 的值即为该有序列表中非空连续子序列的个数。

例如：$F(\text{babbabbababbab}, \text{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$（其中 $x$ 取遍 $s$ 的所有子串）对应的 $F(s, x)$ 之和。

The only line contains the given string s, consisting only of small Latin letters (1 ≤ |s| ≤ 105).

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

Print the single number — the sought sum.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

输出单个数字——所求的和。

在 C++ 中，请勿使用 %lld 格式说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

In the first sample the function values at x equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying x the function value is 1.

在第一个样例中，函数在 $x$ 分别等于 “a”、“aa”、“aaa” 和 “aaaa” 处的取值依次为 10、6、3 和 1。

在第二个样例中，对任意满足条件的 $x$，函数值均为 1。