Problem G
Reversibly Cyclic Strings

A string $t$ is a Cyclic Substring of a string $s$ if there is some rotation of $s$ such that $t$ is a substring of that rotation of $s$.

For example, if $s$ is fatcat, then atc and atf are both Cyclic Substrings of $s$. However, act is not a Cyclic Substring of $s$.

A string $s$ is Internally Reversibly Cyclic if, for every proper substring $t$ of $s$, the reverse of $t$ is a Cyclic Substring of $s$.

Given a string, determine if it is Internally Reversibly Cyclic.

Input

The single line of input contains a string $s$ ($1 \le |s| \le 1{,}000$, $s \in \{ \texttt{a}-\texttt{z}\} ^*$)

Output

Output a single integer, which is $1$ if $s$ is Internally Reversibly Cyclic, $0$ otherwise.

ccca

1

eeaafbddfaa

0