Rearrange Characters

You are given a string S consisting of only the characters 'a', 'b', and 'c'. Your task is to determine if it is possible to rearrange the characters in S such that no two adjacent characters are the same.

Let n be the length of the string and let m be the maximum frequency among the characters in S. A necessary and sufficient condition for such a rearrangement to be possible is:

\( m \leq \lceil \frac{n}{2} \rceil \)

If the condition holds, output 1; otherwise, output 0.

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the string S. The string S only includes the characters 'a', 'b', and 'c'.

outputFormat

Output via standard output (stdout) a single integer: 1 if it is possible to rearrange the string such that no two adjacent characters are the same, and 0 otherwise.

aab

1