順列 $p$ が対合（involution）であるとは、すべての $i$ に対して $p(p(i))=i$ が成り立つことをいう。
正の整数 $k$ が与えられる。各 $u \in [0, k]$ について、以下の値を求めて出力せよ。
- 長さ $n$ のすべての対合順列のうち、転倒数（逆序対の数）が $u$ であるものの個数 mod 2
入力
一行に二つの整数 $n, k$ が与えられる。
出力
長さ $k+1$ の01文字列を一行で出力せよ。ここで、$u$ 番目の文字（$0$ 始まり）は、転倒数が $u$ である対合順列の個数を $2$ で割った余りを表す。
小課題
すべてのデータにおいて $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$ |
入出力例
入力 1
3 9
出力 1
1001000000