Start

2017-04-15 19:00 CEST

NAIPC 2017

End

2017-04-16 00:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -239 days 18:03:40

Time elapsed

5:00:00

Time remaining

0:00:00

Problem J
Yin and Yang Stones

A mysterious circular arrangement of black stones and white stones has appeared. Ming has been tasked with balancing the stones so that only one black and one white stone remain.

Ming has two operations for balancing the stones:

  1. Take some consecutive sequence of stones where there is exactly one more black stone than a white stone and replace the stones with a single black stone

  2. Take some consecutive sequence of stones where there is exactly one more white stone than black stone and replace the stones with a single white stone

Given a circular arrangement, determine if it is possible for Ming to balance the stones.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input will consist of a single string $s$ ($1 \le |s| \le 10^5$), with only the characters capital ‘B’ and ‘W’. The stones are arranged in a circle, so the first stone and the last stone are adjacent.

Output

Output $1$ if it is possible for Ming to balance the stones with his rules. Otherwise, output $0$.

Sample Input 1 Sample Output 1
WWBWBB
1
Sample Input 2 Sample Output 2
WWWWBBW
0
Sample Input 3 Sample Output 3
WBBBBBWWBW
0