|This problem statement contains images that may not display properly if viewed outside of the applet.
Your backyard is a rectangular grid that measures width x height square meters. You would like to plant treeCount trees using the following rules:
- All trees must be planted at integer coordinates on the grid.
- All trees must lie on the same straight line.
- Each pair of trees must be at least distance meters away from each other.
For example, two (of many) ways in which four trees could be planted on a 10x10 grid if distance is 2 are depicted below:
Return the number of distinct ways in which the trees could be planted, modulo 1,000,000,000. Two layouts are considered distinct if there exists a point (x, y) such that one layout contains a tree at (x, y) and the other layout does not.