시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.