P10376 [GESP202403 Level 6] Game

Related multiple-choice and true/false problems: .

You have four positive integers $n, a, b, c$, and you plan to use them to play a simple game. In one move of the game, you may choose to subtract $a$ from $n$, or subtract $b$ from $n$. The game consists of multiple moves and ends when $n \leq c$. You want to know how many different sequences of moves there are when the game ends. Two move sequences are different if and only if the number of moves is different, or in some move one sequence chooses to subtract $a$ from $n$ while the other chooses to subtract $b$ from $n$. If $a = b$, subtracting $a$ and subtracting $b$ are still considered different moves. Since the answer may be very large, you only need to output the result modulo $10^9 + 7$.

One line containing four integers $n, a, b, c$.

Output one line with one integer representing the answer.

### Constraints - For $20\%$ of the testdata, $a = b = c = 1$, and $n \leq 30$. - For $40\%$ of the testdata, $c = 1$, and $n \leq 10^3$. - For all testdata, it is guaranteed that $1 \leq a, b, c \leq n \leq 2 \times 10^5$. Translated by ChatGPT 5