Permutację $p$ nazywamy inwolucją wtedy i tylko wtedy, gdy dla każdego $i$ zachodzi $p(p(i))=i$.
Dla danej liczby całkowitej dodatniej $k$, dla każdego $u\in [0,k]$ należy wyznaczyć:
- Liczbę inwolucji długości $n$, które mają dokładnie $u$ inwersji, modulo 2.
Wejście
W jednym wierszu znajdują się dwie liczby całkowite $n, k$.
Wyjście
W jednym wierszu należy wypisać ciąg binarny długości $k+1$, reprezentujący wyniki dla każdego $u\in [0,k]$.
Przykład
Przykład 1
3 9
Wyjście 1
1001000000
Podzadania
Dla $100\%$ danych wejściowych $1 \leq k, n \leq 10^6$.
| Test | $n \leq$ | $k \leq $ |
|---|---|---|
| $1 \sim 2$ | $10$ | $50$ |
| $3 \sim 4$ | $20$ | $200$ |
| $5 \sim 7$ | $2\,000$ | $2 \times 10^5$ |
| $8$ | $5 \times 10^5$ | |
| $9\sim 10$ | $10^6$ | |
| $11 \sim 14$ | $10^6$ | $5 \times 10^4$ |
| $15 \sim 20$ | $10^6$ |