Vasya and Cyclic Shifts

Interview

Time limit0.6sMemory limit1024 MB

Summary

Count how many of a string's cyclic shifts equal its lexicographically smallest shift, for strings up to 10^7 characters long.

Level: Medium5 of 10
Topics: String, String matching
Solved: No attempts yet

Problem

Vasya got hungry and went to the kitchen for a snack. When he opened the fridge, he found no food, only a string. It was a cyclic string, shaped like a bagel. Food thoughts come to Vasya often when he is hungry. Curious and still hungry, he started turning the string in his hands. For example, turning abacaba gives the following strings:

abacaba
bacabaa
acabaab
cabaaba
abaabac
baabaca
aabacab

Vasya thought that if he could count how many times the lexicographically smallest cyclic shift appears while turning the string, food would appear in the fridge. Strange ideas also come to him when he is hungry. Help Vasya, or he will stay hungry.

Formally, you are given a string. A cyclic shift of a string $s$ of length $n$ is the string obtained by removing the first $k$ characters ( $0 \leq k < n$ ) and appending them to the end. Count how many times the lexicographically smallest cyclic shift appears among all cyclic shifts of the string.

Input

The only line of the input file contains the string $S$ that Vasya found. The string is non-empty, consists of lowercase Latin letters, and its length does not exceed 10,000,000.

Output

Print a single number, the number of lexicographically smallest cyclic shifts.

Examples2

Example 1
Input
```
aaaa
```
Expected output
```
4
```
Example 2
Input
```
abacaba
```
Expected output
```
1
```