Ограбление банка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мир находится под большой угрозой! Никому не понятно, под какой именно, но чтобы его спасти, Дэдпулу и Росомахе необходимо ограбить банк, а для этого им нужен надежный план.

Известно, что план ограбления банка из $$$n$$$ действий можно представить в виде бинарной строки $$$s$$$ длины $$$n$$$. Далее план реализуется следующим образом: пока в плане есть более одного действия, строится новый план $$$s^*$$$, в котором $$$s^*_i = s_i \oplus s_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$|s| - 1$$$, где $$$|s|$$$ — это длина строки $$$s$$$, а $$$ \oplus$$$ означает операцию «исключающее ИЛИ». Заметьте, что после выполнения очередного шага количество шагов в плане уменьшается на $$$1$$$.

Считается, что план является успешным, если после его выполнения в плане остается единственный шаг, равный $$$1$$$. Помогите Дэдпулу и Росомахе понять, является ли план $$$s$$$ успешным.

Входные данные

В единственной строке задается бинарная строка $$$s$$$ — описание изначального плана ($$$1 \le |s| \le 10^6$$$).

Выходные данные

В единственной строке выведите ответ $$$1$$$, если план является успешным, иначе выведите $$$0$$$.

Примеры

Входные данные
1010
Выходные данные
0
Входные данные
1101
Выходные данные
1

Примечание

В первом примере план будет преобразован следующим образом: $$$1010 \rightarrow 111 \rightarrow 00 \rightarrow 0$$$.

Во втором примере план будет преобразован как $$$1101 \rightarrow 011 \rightarrow 10 \rightarrow 1$$$.