Number of paths P19587

You are located on the point $(0, 0)$ of an infinite integer grid, and you need to go to $(x, y)$. You have two follow two conditions when moving:

• At every step, you can only go to any of the eight points horizontally, vertically or diagonally adjacent to the point where you currently are.

• Every movement must strictly reduce the geometric distance to $(x, y)$.

In how many ways can you reach $(x, y)$?

Input

Input consists of several cases with two integers $x$ and $y$, each between $-2000$ and $2000$. A case with $x = y = 0$ ends the input.

Output

For every case, print the number of ways to go from $(0, 0)$ to $(x, y)$. Since this number can be huge, compute it modulo $10^8 + 9$.