A. Acoustic String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A few people know this but binary strings can be acoustic. It's quite easy to check if a binary string is acoustic: you just have to make it resonate with itself.

In the process of resonance a binary string $$$s$$$ of length $$$n$$$ is changed as follows: while $$$n \gt 1$$$, a new string $$$s^*$$$ of length $$$n - 1$$$ is constructed, where $$$s^*_i = s_i \oplus s_{i+1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n - 1$$$, where $$$\oplus$$$ denotes the "exclusive OR" operation. In other words, each bit of a new string is a sum of two consecutive bits of $$$s$$$ modulo $$$2$$$.

The string is considered acoustic if after $$$n - 1$$$ iterations of resonance, when its length becomes $$$1$$$, the only remaining bit is equal to $$$1$$$. Find out if a given string is acoustic or not.

Input

A single line contains a binary string $$$s$$$ consisting of characters '0' and '1' ($$$1 \le |s| \le 10^6$$$).

Output

Output a single line with the answer $$$1$$$ if the string is acoustic; otherwise, output $$$0$$$.

Examples
Input
1010
Output
0
Input
1101
Output
1
Note

In the first example, the string changes as follows: $$$1010 \rightarrow 111 \rightarrow 00 \rightarrow 0$$$.

In the second example, the string changes as follows: $$$1101 \rightarrow 011 \rightarrow 10 \rightarrow 1$$$.