나무 심기

세준이는 가로 W, 세로 H인 직사각형 뒷마당에 T개의 나무를 심으려고 한다. 나무는 직사각형 안의 정수 좌표 격자점에만 심을 수 있으며, 경계 위의 점도 사용할 수 있다.

나무를 심는 방법은 다음 조건을 모두 만족해야 한다.

1. 모든 나무는 서로 다른 정수 좌표에 놓인다.
2. 모든 나무는 하나의 직선 위에 놓인다.
3. 서로 다른 두 나무 사이의 유클리드 거리는 적어도 D이다.

W, H, T, D가 주어졌을 때 가능한 서로 다른 위치 집합의 수를 구한다. 두 방법은 심은 좌표의 집합이 다르면 서로 다르다.

첫째 줄에 네 정수 T, W, H, D가 공백으로 구분되어 주어진다.

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

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