The cyclic suffixes#2074

The cyclic suffixes

2 seconds
64 megabytes
Easy

Consider the string \textbf{S = s_1s_2s_3 \ldots s_{n-1}s_n} over the alphabet . The cyclic extension of order of the string is a string s_1s_2s_3 \ldots s_{n-1}s_ns_1s_2 \ldots of length . This means we append the string to itself until we reach the required length, and then take a prefix of length .

The cyclic string \textbf{Š} is the infinite cyclic extension of .

Consider the suffixes of the cyclic string \textbf{Š}. Clearly, there are at most different suffixes: the (n+1)-th suffix matches the first, the (n+2)-th matches the second, and so on. In fact, there can be even fewer distinct suffixes. For example, if \textbf{S} = abab, then the first four suffixes of the cyclic string \textbf{Š} are:

\textbf{Š}_1 = ababababab \ldots

\textbf{Š}_2 = bababababa \ldots

\textbf{Š}_3 = ababababab \ldots

\textbf{Š}_4 = bababababa \ldots

There are only two different suffixes, while |\textbf{S}| = 4.

Sort the first suffixes of \textbf{Š} lexicographically. If two suffixes match, place the one with the lower index first. The question is: what is the position of the string \textbf{Š} itself in this list?

For example, for the string \textbf{S} = cabcab:

(1) \textbf{Š}_2 = abcabcabca \ldots

(2) \textbf{Š}_5 = abcabcabca \ldots

(3) \textbf{Š}_3 = bcabcabcab \ldots

(4) \textbf{Š}_6 = bcabcabcab \ldots

(5) \textbf{Š}_1 = cabcabcabc \ldots

(6) \textbf{Š}_4 = cabcabcabc \ldots

Here, the cyclic string \textbf{Š} = \textbf{Š}_1 takes the fifth place.

You are given a string . Find the position of the cyclic string \textbf{Š} in this list.

Input

The input file contains a single string (1 \leq |S| \leq 1000000), consisting of uppercase Latin letters.

Output

Print a single number — the position of the string \textbf{Š} among the first suffixes in the described order.

Examples

Example 1

Loading
Loading