题目描述
给一个正整数集合 $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$ 的数据。
数据范围
| 测试点编号 | $n \leq $ |
|---|---|
| $1$ | $10$ |
| $2$ | $20$ |
| $3$ | $100$ |
| $4$ | $300$ |
| $5 \sim 6$ | $5\,000$ |
| $7$ | $30\,000$ |
| $8$ | $50\,000$ |
| $9$ | $70\,000$ |
| $10$ | $100\,000$ |
对于 $100\%$ 的数据，保证 $1\leq n\leq 10^5$。