正整数の集合 $S$ が与えられます。各ノードの重みが $S$ に属するような、ノードの重みの総和が $n$ であるラベルなし根付き二分木の個数を $f_n$ とします。
ここで、ある木 $T$ に対して「あるノードの左右の子供を入れ替える」操作を繰り返すことで $T'$ に変形できる場合、$T$ と $T'$ は同一の木とみなします。
今回は $f_n \bmod 2$ の値のみに関心があります。$1\le n\le N$ について、$f_n \bmod 2$ を出力してください。
入力
長さ $N$ の 01 文字列が与えられます。$i$ 番目の文字が 1 であることは、$i \in S$ であることと同値です。
出力
長さ $N$ の 01 文字列を出力してください。$i$ 番目の文字は $f_i \bmod 2$ です。
入出力例
入力 1
1101010110
出力 1
1000010110
注記 1
$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$ |
すべてのデータにおいて、$1\leq N\leq 10^5$ を満たします。