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⁸ + 9.