题目描述

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

样例

10110

11000

对于样例 $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$。