Problem Description

You have four positive integers \( n, a, b, c \), and you are going to play a simple game with them.

In each round of the game, you can choose to subtract \( a \) from \( n \) or subtract \( b \) from \( n \). The game will continue for multiple rounds until \( n \leq c \).

You want to know how many different sequences of game operations can lead to the end of the game. Two sequences of operations are considered different if they have a different number of rounds or if, in any round, one sequence chooses to subtract \( a \) while the other chooses to subtract \( b \). If \( a = b \), subtracting \( a \) and subtracting \( b \) are still considered different operations.

Since the answer may be very large, you only need to find the result modulo \( 10^9 + 7 \).

Input Format

A single line containing four integers \( n, a, b, c \).

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

1 1 1 1

Sample Output #1

1

Sample Input #2

114 51 4 1

Sample Output #2

176

Sample Input #3

114514 191 9 810

Sample Output #3

384178446

Notes

Data Size and Constraints

• For 20% of the data, \( a = b = c = 1 \) and \( n \leq 30 \).
• For 40% of the data, \( c = 1 \) and \( n \leq 10^3 \).
• For all test data, it is guaranteed that \( 1 \leq a, b, c \leq n \leq 2 \times 10^5 \).

见题面 Input 部分

见题面 Output 部分