Game Operation Sequence Count

You are given four positive integers \(n, a, b, c\). You want to play a simple game with these numbers.

The game is played as follows: In each move, if \(n > c\), you may choose one of the following two operations:

• Subtract \(a\) from \(n\).
• Subtract \(b\) from \(n\).

The game stops once \(n \le c\). Note that even if \(a = b\), subtracting \(a\) and subtracting \(b\) are considered different operations.

Your task is to count the number of different operation sequences that can occur by the time the game ends. Two sequences are considered different if they differ in the number of moves, or if there is at least one move where the chosen operation (subtracting \(a\) vs subtracting \(b\)) differs.

Since the answer can be very large, output the result modulo \(10^9+7\).

Hint: Let \(F(x)\) denote the number of sequences starting with the value \(x\) (with \(x > c\)). Then, for \(x > c\), you can use the recurrence:

\(F(x) = (\text{if } x-a \le c \text{ then } 1 \text{ else } F(x-a)) + (\text{if } x-b \le c \text{ then } 1 \text{ else } F(x-b)) \mod (10^9+7)\).

inputFormat

The input consists of a single line with four space-separated integers: \(n\), \(a\), \(b\), and \(c\).

outputFormat

Output a single integer: the number of different game operation sequences modulo \(10^9+7\).

sample

10 3 2 3

9