Another easy string problem#11545
Sign in

Another easy string problem

2 seconds
256 megabytes
Very hard

Given a string . We call any non-empty string good, if it is a substring of and has 4 non-overlapping occurrences in . Your task is to find the number of different good strings.

Input

Contains one string s~(1 \le \textit{length of s} \le 10^5) — given string. It is guaranteed that all characters are lowercase English letters.

Output

Print one integer — the number of different good strings.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading