Plate

Time limit1sMemory limit512 MB

Summary

Assign labels to odd lattice points on a quadrant-by-quadrant recursive spiral, then sum labels of points on x + y = k.

Level: Hard8 of 10
Topics: Math, Simulation, Divide and conquer, Matrix
Solved: No attempts yet

Problem

Marin spends his free time staring at the part of the coordinate plane bounded by an imaginary square whose lower left corner is at $(-2n+1, -2n+1)$ and whose upper right corner is at $(2n-1, 2n-1)$ . In that part of the plane, Marin decided to mark the points whose two coordinates are both odd numbers. He will label the marked points with the natural numbers from $1$ to $4n$ .

First he decided that the labels of all points in the first quadrant must be strictly smaller than the labels of all points in the second quadrant. Furthermore, he wants the labels of all points in the second quadrant to be smaller than the labels of all points in the third quadrant, and the labels of all points in the third quadrant to be smaller than all labels in the fourth quadrant. Then he decided that he will assign labels to the set of points of each quadrant by the same recursive procedure, with the intersection of the horizontal and vertical axes of symmetry of that quadrant's set of points taking the role of the origin.

The labels of the marked points for $n = 2$ .

Marin now wants the sum of the labels of all marked points lying on the line $x + y = k$ .

Input

The first line contains the integers $n$ and $k$ from the problem statement ( $1 \le n \le 60$ ). The number $k$ will be such that at least one marked point lies on the line $x + y = k$ .

Output

Print the sum of the labels of the marked points lying on the line $x + y = k$ , modulo $10^9 + 7$ .

Examples4

Example 1
Input
```
1 0
```
Expected output
```
6
```
Example 2
Input
```
2 0
```
Expected output
```
44
```
Example 3
Input
```
2 6
```
Expected output
```
1
```
Example 4
Input
```
3 -14
```
Expected output
```
43
```