루미 알고리즘

#1628실버Theodor the Wizard

PO 2025 학교 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

This problem is based on the problem The Wizard Theodor.

Evil Olle, who is ultimately responsible for all evil, is tired of Theodor always ruining everything. Now, Olle has devised a new malicious plan, and to put it into action, he needs to keep Theodor occupied. At his disposal, he has N monsters, and since he is immensely powerful, he can assign these monsters different amounts of life points. Olle now wants to calculate the number of ways he can assign various amounts of life points to his monsters such that Theodor needs to fire exactly K magical explosions to defeat all the monsters. The only requirement for the number of life points a monster has is that it must be greater than 0.

Just like in the problem The Wizard Theodor, Theodor damages monsters by targeting a specific monster and firing an explosion. The targeted monster loses S life points, and then all monsters (including the one he targeted) lose A life points each. A monster is defeated if it has 0 or fewer life points. Theodor chooses how to target monsters to minimize the number of explosions he needs to fire.

Input

Input consists of a single line with four integers, N, K, S, and A (1 ≤ N, K, S ≤ 2 · 10^5, 0 ≤ A ≤ 2 · 10^5), which are the four values described above.

Output

Print the number of ways Olle can assign life points to his monsters such that Theodor needs to fire exactly K explosions to defeat all of them. Since this number can become very large, output the result modulo (https://en.wikipedia.org/wiki/Modulo) (10^9+7).

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
15A = 0, N, K, S ≤ 5
215A = 0, N, K, S ≤ 50
320N, K, S, A ≤ 50
420N, K, S, A ≤ 300
520N, K, S, A ≤ 2000
620No additional constraints.

Explanation of Samples

In sample 1, there is one monster, and the possible life point values it can have such that Theodor defeats it with exactly one explosion are 1, 2, 3, 4, 5.

In sample 2, there are 10 distributions of life point values such that Theodor defeats both monsters with exactly two explosions. These are:

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

예제

예제 1

입력
1 1 5 0
출력
5

예제 2

입력
2 2 1 1
출력
10

예제 3

입력
10 20 30 40
출력
435462573

출처 표기

출처: Programmeringsolympiaden 2025년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.