题目描述
给一个正整数集合 $S$，设 $f_n$ 为节点重量之和为 $n$ 的无标号有根二叉树的数量，其中每个节点的重量均 $\in S$。
注意这里如果一颗树 $T$ 能够经过若干次「给一个节点交换左右子树」的操作变成 $T'$，那么 $T$ 和 $T'$ 视为一颗树。
今天我们只关心 $f_n \bmod 2$ 的值，你只需对 $1\le n\le N$，输出 $f_n \bmod 2$ 即可。
输入格式
输入一个 01 串，其长度即为 $n$。第 $i$ 个数为 $1$ 当且仅当 $i\in S$。
输出格式
输出一个长为 $n$ 的 01 串。第 $i$ 个数为 $f_i \bmod 2$。
样例 1
输入
1101010110输出
1000010110解释
$f_{1,\dots,10} = [1, 2, 4, 10, 24, 63, 166, 455, 1265, 3580]$。
样例 2
见下发文件 ex_modtwo2.in/out。这是一组 $n=10^4$ 的数据。
数据范围
对于 $100\%$ 的数据，保证 $1\leq n\leq 10^5$。
