Tree Planting

Time limit2sMemory limit128 MB

Summary

Count sets of T collinear lattice points inside a W by H rectangle where every pair of points is at least distance D apart, modulo 1e9.

Level: Hard8 of 10
Topics: Combinatorics, Geometry, Number theory, Math
Solved: No attempts yet

Problem

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.

Every tree is placed at a distinct integer coordinate.
All trees lie on one straight line.
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.

Input

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

Output

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

Constraints

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

Examples6

Example 1
Input
```
2 4 4 1
```
Expected output
```
300
```
Example 2
Input
```
13 36 48 5
```
Expected output
```
2
```
Example 3
Input
```
5 5 5 1
```
Expected output
```
88
```
Example 4
Input
```
50 49 49 1
```
Expected output
```
102
```
Example 5
Input
```
6 5 5 2
```
Expected output
```
0
```
Example 6
Input
```
10 55 75 5
```
Expected output
```
490260662
```