Incomparable Pairs

Time limit3sMemory limit512 MB

Summary

Count unordered pairs of substrings of a string s where neither substring is contained in the other.

Level: Hard8 of 10
Topics: String, Tree, String matching
Solved: No attempts yet

Problem

You are given a string $s = s_1 s_2 ... s_n$ . Consider an unordered pair of its substrings $\{a, b\}$ . Call such a pair incomparable if neither $a$ is a substring of $b$ nor $b$ is a substring of $a$ . Compute the number of incomparable pairs of substrings of $s$ .

Input

The first line contains a single string $s$ consisting of lowercase English letters ( $1 \le |s| \le 10^5$ ).

Output

Output a single integer, the answer to the problem.

Examples2

Example 1
Input
```
abba
```
Expected output
```
8
```
Example 2
Input
```
abacaba
```
Expected output
```
64
```