Inv

Time limit2sMemory limit512 MB

Summary

Count involutions of n elements with exactly k inversions and report the count modulo 2.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math, Bit manipulation
Solved: No attempts yet

Problem

A permutation $p$ on $n$ elements is an involution if $p(p(i)) = i$ for each $i = 1, 2, \dots, n$ . Your task is to compute the number of involutions on $n$ elements with $k$ inversions. The answer can be large, so print only the parity of this number.

Input

The first line contains two space-separated integers: $n$ ( $1 \le n \le 500$ ), the length of the involution, and $k$ ( $0 \le k \le \frac{n(n-1)}{2}$ ), the number of inversions.

Output

Print a single number ( $0$ or $1$ ): the number of involutions on $n$ elements with exactly $k$ inversions, taken modulo $2$ .

Hint

In the first sample, there are $3$ such involutions.

Examples2

Example 1
Input
```
4 1
```
Expected output
```
1
```
Example 2
Input
```
10 21
```
Expected output
```
0
```