A permutation $p$ is called an involution if and only if $p(p(i)) = i$ for every $i$.
For a given positive integer $k$, you need to find the following for each $u \in [0, k]$:
- The number of involutions of length $n$ with exactly $u$ inversions, modulo 2.
Input
A single line containing two integers $n$ and $k$.
Output
A single line containing a binary string of length $k+1$, representing the output for each $u \in [0, k]$.
Examples
Input 1
3 9
Output 1
1001000000
Subtasks
For $100\%$ of the data, $1 \leq k, n \leq 10^6$.
| Test Case | $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$ |