Description

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
s result
baabaa 1
cdcd 0

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.

Result Stop
Result of [Run] or [Submit] will be displayed here