Suffix Array 1

The $i$-th suffix of a string $S$ is the part of $S$ that starts at position $i$ and runs to the end of the string. Positions are numbered from 0. For example, if $S$ = "abcde", the 0th suffix is "abcde" and the 3rd suffix is "de".

The suffix array of $S$ is built by sorting all suffixes of $S$ in lexicographic order and then writing down the starting position of each suffix in that order. For example, if $S$ = "abca", the suffix array is $(3, 0, 1, 2)$.

Given a string $S$, write a program that decides whether a string $T$ exists that has the same suffix array as $S$ and comes before $S$ in lexicographic order. $T$ has the same length as $S$, and $T$ also consists of lowercase letters only.

The first line contains the string $S$. The length of $S$ is between 1 and 50, and $S$ consists of lowercase letters only.

Print 1 if a string exists that comes before $S$ in lexicographic order and has the same suffix array as $S$. Otherwise print 0.