Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1146.

Problem Description

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$.

Input Format

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

Output Format

Output one line with one integer representing the answer.

1 1 1 1

1

114 51 4 1

176

114514 191 9 810

384178446

Hint

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