Problem L
Theodor the Wizard
Languages
en
sv
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 \leq N, K, S \leq 2 \cdot 10^5$, $0 \leq A \leq 2 \cdot 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 $(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.
|
Group |
Points |
Constraints |
|
$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$ |
No 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
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 5 0 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 2 1 1 |
10 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 20 30 40 |
435462573 |
