Opis problemu
Dany jest zbiór dodatnich liczb całkowitych $S$. Niech $f_n$ oznacza liczbę nieoznakowanych ukorzenionych drzew binarnych, w których suma wag węzłów wynosi $n$, przy czym waga każdego węzła należy do zbioru $S$.
Zauważ, że jeśli drzewo $T$ można przekształcić w $T'$ poprzez wykonanie dowolnej liczby operacji „zamiany lewego i prawego poddrzewa węzła”, to $T$ oraz $T'$ są uważane za to samo drzewo.
Interesuje nas jedynie wartość $f_n \bmod 2$. Dla każdego $1\le n\le N$ należy wypisać $f_n \bmod 2$.
Wejście
Wejście zawiera ciąg znaków 01 o długości $n$. $i$-ta cyfra jest równa $1$ wtedy i tylko wtedy, gdy $i\in S$.
Wyjście
Wypisz ciąg znaków 01 o długości $n$. $i$-ta cyfra powinna być równa $f_i \bmod 2$.
Przykład 1
Wejście 1
1101010110
Wyjście 1
1000010110
Uwagi
$f_{1,\dots,10} = [1, 2, 4, 10, 24, 63, 166, 455, 1265, 3580]$.
Przykład 2
Wejście 2
Patrz pliki ex_modtwo2.in/out. Jest to zestaw danych dla $n=10^4$.
Ograniczenia
| Numer testu | $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$ |
Dla $100\%$ danych wejściowych gwarantuje się, że $1\leq n\leq 10^5$.