시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 6 5 22.727%

문제

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

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

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

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

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

입력

첫째 줄에 T W H D가 주어진다. (1<=T,D<=50, 1<=W,H<=500)

출력

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

예제 입력

2 4 4 1

예제 출력

300

힌트

출처