Дан набор положительных целых чисел $S$. Пусть $f_n$ — количество непомеченных корневых бинарных деревьев, сумма весов узлов которых равна $n$, при условии, что вес каждого узла принадлежит $S$.
Заметим, что если дерево $T$ можно превратить в дерево $T'$ путем конечного числа операций «поменять местами левое и правое поддеревья у некоторого узла», то $T$ и $T'$ считаются одним и тем же деревом.
Нас интересует только значение $f_n \bmod 2$. Вам необходимо вывести $f_n \bmod 2$ для всех $1\le n\le N$.
Входные данные
На вход подается строка из 01, длина которой равна $n$. $i$-й символ равен $1$ тогда и только тогда, когда $i\in S$.
Выходные данные
Выведите строку из 01 длиной $n$. $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$.