시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB277626.087%

문제

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

세준이의 뒷마당은 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

예제 입력 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

출처