計數問題動不動就取模 $998244353$、$10^9+7$ 什麼的，溫習兩個 FFT，加一個多點求值，大家未免都膩了。

對於模小質數的問題，也有不少先例，比如去年 zx2003 試圖告訴大家的小質數下，小多項式的高階冪的遠處係數。

今天不整別的，就模 $2$，所以，就來看看零和一。

你有一個正整數集合 $S$，現在請你回答對於 $1\le k\le n$，有多少種將編號為 $1\sim k$ 的球放入一些盒子的方案，使得每個盒子裡球的數量都屬於 $S$。你只想知道答案的奇偶性。

注意：球可以區分，盒子不可以區分。

輸入格式

輸入一個長為 $n$ 的 01 串，第 $x$ 位為 $1$ 表示 $x\in S$。

輸出格式

輸出一個長為 $n$ 的 01 串，第 $k$ 位，表示 $a_k \bmod 2$。

範例

範例 1 輸入

10110

範例 1 輸出

11000

說明 1

對於範例 $1$，給出每個 $k$ 對應的方案數：

$k=1$：$\{\{1\}\}$，共 $1$ 種。

$k=2$：$\{\{1\},\{2\}\}$，共 $1$ 種。

$k=3$：$\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$，共 $2$ 種。

$k=4$：

• $\{\{1\},\{2\},\{3\},\{4\}\}$
• $\{\{1,2,3\},\{4\}\}$
• $\{\{1,2,4\},\{3\}\}$
• $\{\{1,3,4\},\{2\}\}$
• $\{\{1\}\{2,3,4\}\}$
• $\{\{1,2,3,4\}\}$
• 共 $6$ 種。

$k=5$：共 $16$ 種，不予一一列舉了。

子任務

對於 $10\%$ 的資料，$n\le 10$。

對於 $40\%$ 的資料，$n\le 2000$。

對於 $70\%$ 的資料，$n\le 3\times 10^5$。

對於 $100\%$ 的資料，$n\le 2\times 10^6$。