Tree Planting

Sejun wants to plant T trees in a rectangular backyard of width W and height H. A tree may be planted only at an integer lattice point inside the rectangle, including points on the boundary.

A planting method must satisfy all of the following conditions.

1. Every tree is placed at a distinct integer coordinate.
2. All trees lie on one straight line.
3. The Euclidean distance between any two distinct trees is at least D.

Given W, H, T, and D, count the number of different possible sets of tree positions. Two methods are different if the sets of planted coordinates are different.

The first line contains four integers T, W, H, and D, separated by spaces.

Print the number of different methods modulo 1,000,000,000.

• 1 ≤ T, D ≤ 50
• 1 ≤ W, H ≤ 500