마법사 Theodor

이 문제는 마법사 Theodor 문제를 바탕으로 한다.

모든 악의 궁극적인 원흉인 Evil Olle은 Theodor가 늘 모든 일을 망치는 데 지쳤다. 이제 Olle는 새로운 사악한 계획을 세웠으며, 이를 실행하기 위해 Theodor가 다른 일에 매달리게 해야 한다. 그에게는 $N$마리의 몬스터가 있으며, 그는 엄청나게 강력하므로 이 몬스터들에게 여러 가지 생명력 수치를 부여할 수 있다. 이제 Olle는 Theodor가 모든 몬스터를 물리치기 위해 정확히 $K$번의 마법 폭발을 발사해야 하도록 몬스터들에게 다양한 생명력 수치를 부여하는 방법의 수를 계산하려 한다. 몬스터의 생명력 수치에 대한 유일한 조건은 $0$보다 커야 한다는 것이다.

마법사 Theodor 문제에서와 마찬가지로, Theodor는 특정 몬스터를 겨냥해 폭발을 발사하여 몬스터에게 피해를 준다. 겨냥한 몬스터는 생명력을 $S$만큼 잃고, 이어서 모든 몬스터는 (겨냥한 몬스터를 포함하여) 각각 생명력을 $A$만큼 잃는다. 몬스터의 생명력이 $0$ 이하이면 그 몬스터는 쓰러진다. Theodor는 발사해야 하는 폭발의 수를 최소화하도록 겨냥할 몬스터를 선택한다.

채점

제출한 풀이는 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹에는 여러 테스트 케이스가 포함된다. 테스트 그룹의 점수를 받으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$5$| $A = 0$, $N, K, S \leq 5$

$2$ |$15$| $A = 0$, $N, K, S \leq 50$

$3$ |$20$| $N, K, S, A \leq 50$

$4$ |$20$| $N, K, S, A \leq 300$

$5$ |$20$| $N, K, S, A \leq 2000$

$6$ |$20$| 추가 제한 조건 없음.

입력은 위에서 설명한 네 값인 네 정수 $N$, $K$, $S$, $A$ ($1 \leq N, K, S \leq 2 \cdot 10^5$, $0 \leq A \leq 2 \cdot 10^5$)가 한 줄에 주어진다.

Theodor가 모든 몬스터를 물리치기 위해 정확히 $K$번의 폭발을 발사해야 하도록 Olle가 몬스터들에게 생명력 수치를 부여하는 방법의 수를 출력한다. 이 수는 매우 커질 수 있으므로, 결과를 나머지 연산 $(10^9+7)$로 출력한다.

예제 1에는 몬스터가 하나 있으며, Theodor가 정확히 한 번의 폭발로 이 몬스터를 물리치게 하는 가능한 생명력 수치는 1, 2, 3, 4, 5이다.

예제 2에는 Theodor가 정확히 두 번의 폭발로 두 몬스터를 모두 물리치게 하는 생명력 수치의 분배가 10가지 있다. 그 분배는 다음과 같다.

  1 3
  1 4
  2 2
  2 3
  2 4
  3 1
  3 2
  3 3
  4 1
  4 2