I. Incomparable Pairs
time limit per test
3 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given a string s = s1s2... sn. Consider an unordered pair of its substrings {a, b}. Let us call such pair incomparable if neither a is a substring of b nor b is a substring of a. You have to compute the number of incomparable pairs of substrings of s.

Input

The first line of input contains a single string s consisting of lowercase English letters (1 ≤ |s| ≤ 105).

Output

Output a single integer which is the answer to the problem.

Examples
Input
abba
Output
8
Input
abacaba
Output
64