Yin and Yang Stones

Interview

Time limit2sMemory limit512 MB

Summary

Given a circular string of black and white stones, decide whether repeated merges can reduce it to one black and one white stone.

Level: Medium4 of 10
Topics: String, Greedy, Math
Solved: No attempts yet

Problem

A mysterious circular arrangement of black and white stones has appeared. Ming must balance the stones so that only one black stone and one white stone remain.

Ming has two operations:

Take a consecutive sequence of stones that contains exactly one more black stone than white stones, and replace the whole sequence with a single black stone.
Take a consecutive sequence of stones that contains exactly one more white stone than black stones, and replace the whole sequence with a single white stone.

Given the circular arrangement, determine whether Ming can balance the stones.

Input

The input is a single line containing a string $s$ ( $1 \le |s| \le 10^5$ ) made of the uppercase letters B and W only. B is a black stone and W is a white stone. The stones are arranged in a circle, so the first stone and the last stone are adjacent.

Output

Print 1 if Ming can balance the stones using his operations. Otherwise, print 0.

Examples3

Example 1
Input
```
WWBWBB
```
Expected output
```
1
```
Example 2
Input
```
WWWWBBW
```
Expected output
```
0
```
Example 3
Input
```
WBBBBBWWBW
```
Expected output
```
0
```