Incomparable Pairs

문자열 s의 부분 문자열 쌍 중에서 어느 쪽도 다른 쪽을 포함하지 않는 쌍의 개수를 센다.

어려움9문자열정렬문자열 매칭조합론아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제2

문제

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.