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.

Public test cases

**Input**

0 1 -1 -1 0 -2 -5 3 2000 2000 0 0

**Output**

1 3 7 9132 6647843

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Onzè Concurs de Programació de la UPC - Semifinal
- Date
- 2013-06-19