시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 117 26 23 31.944%

문제

사탕을 배달하다 지친 윤제는 집에 돌아와 잠자리에 들었다.

사탕처럼 달콤한 꿈속에서 윤제는 가상의 친구 ‘폰친구’들을 사귀었다. 폰친구들은 사탕을 좋아하지만, 사탕 배달을 요구하는 일은 없다. 대신 윤제가 있는 곳으로 직접 와주기 때문에 가만히 서서 사탕을 나누어 주기만 하면 된다!

꿈속에서 윤제는 같은 종류의 사탕 $K$개를 $N$명의 폰친구들에게 남김없이 나누어 주려고 한다. 폰친구들은 사탕을 어떻게 나누어 주어도 윤제를 떠나지 않지만, 각자 최소 $m$개 이상의 사탕을 받기를 원한다. 또한, 자신을 제외한 누군가가 $M$개보다 많은 사탕을 받는 것을 원하지 않는다.

윤제는 사탕을 $Nm$개 이상, $NM$개 이하로 갖고 있다. 윤제가 모든 폰친구들을 만족시키면서 사탕을 나누어 줄 수 있는 경우의 수를 구해보자.

입력

첫째 줄에 정수 $N$, $m$, $M$, $K$이 주어진다. ($2 \leq N \leq 1\ 000$, $0 \leq m \leq M \leq 1\ 000$, $Nm \leq K \leq NM$)

$N$은 폰친구의 수, $K$는 윤제가 가진 사탕의 개수이다. $m$은 각 친구가 받아야 할 최소 사탕의 개수, $M$은 각 친구가 받을 수 있는 최대 사탕의 개수이다.

출력

윤제가 폰친구들에게 조건에 맞게 사탕을 나누어 줄 수 있는 경우의 수를 출력한다. 너무 많은 경우가 있을 수 있으므로 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

예제 입력 1

2 0 4 4

예제 출력 1

5

예제 입력 2

2 1 4 4

예제 출력 2

3

출처

University > 서강대학교 > 2020 Sogang Programming Contest (Champion) F번