Elimination by grouping starts with a string consisting of lower-case letters. First, find a pair of two identical letters placed consecutively. Eliminate the pair, then concatenate the split strings. Elimination by grouping ends when all strings are eliminated by repeatedly doing this procedure. Given a string "S", write a function solution to return whether elimination by grouping can be successfully done or not. Return 1 for success and 0 otherwise.

For example, when string "S" = baabaa, return 1 because all strings can be eliminated as follows:

b aa baa → bb aa → aa →

Constraints

• Length of string : natural number less than 1,000,000.
• String consists of lower-case letters only.

Examples

Example #1
It is the same as the example in the problem statement.
Example #2
Return 0 because a string remains but no string can be eliminated by grouping.