시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 2 2 100.000%

문제

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.

입력

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

출력

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

예제 입력 1

abba

예제 출력 1

8

예제 입력 2

abacaba

예제 출력 2

64