Мир находится под большой угрозой! Никому не понятно, под какой именно, но чтобы его спасти, Дэдпулу и Росомахе необходимо ограбить банк, а для этого им нужен надежный план.
Известно, что план ограбления банка из $$$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$$$.