Problem C
Desert Strike

Illustration of sample 1, where $K = 5$ and $W = 12$.

Maru and Byun love playing the real time strategy game Desert Strike, where they first assemble a little army in a confined area, then unleash the troops and watch them battle it out in the open field.

They soon realized that space runs out quickly because each troop takes up $1$ unit of space. Strategically it is important to know the exact size of the confined area in order to come up with an optimal budget and army composition, etc.

The shape of the confined area looks like a rotated square rasterized naively.

Suppose the bottom edge of the square has slope $\frac{2}{K}$, and its length in the x-axis is $W$, the rasterization process is as follows:

1. Starting from $(0, 0)$, draw a line to the right with length $\lceil {K/2}\rceil $, draw a line up with length 1, draw a line to the right with length $\lfloor {K/2}\rfloor $, and finally another line up with length 1. This creates a jagged line starting from $(0, 0)$ and ends at $(K, 2)$ i.e. the slope is $\frac{2}{K}$.

2. Repeat this process starting from $(K, 2)$.

3. Stop immediately when the coordinate $(W, \lfloor W\frac{2}{K}\rfloor )$ is reached! I.e., no part of any line segment should have coordinate $(X, Y)$ s.t. $X > W$ or $Y>\lfloor W\frac{2}{K}\rfloor $.

4. This completes one edge of the rotated square.

5. As with regular squares, duplicate one edge 3 times, rotating by 90 degrees each time and attach them from end to end, this completes the square.

This is one possible way to rasterize a rotated square, and although it’s not a particularly good one, it creates an interesting shape for an area to assemble an army.

Can you help Maru and Byun figure out the area of this shape?

Input

The first line of input contains the integers $2 \le K \le 10^9$, and $1 \le W \le 10^9$.

Output

Output should contain the integer area of the shape. Since this number can be very large, output the number modulo $10^9 + 9$.

5 12

168

5 10

140

5 4

21