Перестановка $p$ называется инволюцией тогда и только тогда, когда для каждого $i$ выполняется $p(p(i))=i$.
Для заданного целого положительного числа $k$ вам необходимо для каждого $u\in [0,k]$ найти:
- Количество инволюций длины $n$, у которых количество инверсий равно $u$, по модулю 2.
Входные данные
Одна строка, содержащая два целых числа $n$ и $k$.
Выходные данные
Одна строка, представляющая собой бинарную строку длины $k+1$, где $i$-й символ (индексация с 0) соответствует ответу для $u=i$.
Примеры
Пример 1
3 9
Выходные данные
1001000000
Подзадачи
Для $100\%$ данных выполняется $1 \leq k, n \leq 10^6$.
| Тест | $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$ |