Number of paths P19587


Statement
 

pdf   zip

html

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 108 + 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++