1554번 - 나무 심기

세준이는 황무지에 호화로운 저택을 지어서 살고 있다. 황무지에 집을 지었기 때문에, 세준이의 뒷마당에는 나무가 하나도 없었다. 따라서 세준이는 뒷마당에 나무를 심기로 했다.

세준이의 뒷마당은 W×H(가로×세로)의 직사각형 모양이다. 세준이는 T개의 나무를 심으려고 한다. 세준이는 전직 미술가이기 때문에, 미적 감각을 살려 다음과 같은 모양으로 나무를 심으려고 한다.

1. 모든 나무는 정수 좌표에 있어야 한다.
2. 모든 나무는 한 직선 위에 있어야 한다.
3. 모든 나무는 위치의 차이는 적어도 D만큼 차이가 나야 한다. 

위의 그림은 10×10 크기의 뒷마당에 나무 4개를 나무들 사이의 거리 차이가 최소 2가 되게 채운 두 가지 방법이다.

W와 H와 T와 D가 주어졌을 때, 서로 다른 몇 가지 방법으로 나무를 심을 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 T, W, H, D가 주어진다.

첫째 줄에 서로 다른 방법의 수를 1,000,000,000으로 나눈 나머지를 출력한다.

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