计数什么的，动不动就取模 $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$。