시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

Vasya was at a meeting during his working day at Yandex. Suddenly he thought about a string $s$ consisting of lowercase English letters.

Then he decided that a string $t = t_{1} t_{2} \dots t_{m}$ ($m > 0$) is called a good string with respect to $s$ if $t$ is a substring of $s$ and the left circular shift $t' = t_{2} \dots t_{m} t_{1}$ of string $t$ is also a substring of $s$.

Vasya was going to calculate the number of different good strings $t$ with respect to the given string $s$...~but suddenly a colleague asked him a question, so he had to return back to reality. Find that number for Vasya while he is busy with the meeting.

입력

The only input line contains a string $s$ consisting of $n$ ($1 \leq n \leq 300\,000$) lowercase English letters.

출력

Output a single integer: the number of different good strings $t$ with respect to the given string $s$.

예제 입력 1

abaac

예제 출력 1

7

예제 입력 2

aaa

예제 출력 2

3

힌트

In the first sample case, the good strings are exactly the following strings: a, b, c, aa, ab, ba, aba.

In the second sample case, the good strings are exactly the following strings: a, aa, aaa.