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

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

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

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

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

입력 형식

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

출력 형식

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

예제 입력 1

2 4 4 1

예제 출력 1

300

예제 입력 2

13 36 48 5

예제 출력 2

2

예제 입력 3

5 5 5 1

예제 출력 3

88

예제 입력 4

50 49 49 1

예제 출력 4

102

예제 입력 5

6 5 5 2

예제 출력 5

0

예제 입력 6

10 55 75 5

예제 출력 6

490260662