Counting Constrained Sequences

Given four integers \(n\), \(s\), \(a\) and \(b\), count the number of integer sequences \(x_1,x_2,\ldots,x_n\) such that:

• The sum \(x_1+x_2+\cdots+x_n = s\).
• For every consecutive pair \(x_i\) and \(x_{i+1}\) (\(1 \le i < n\)), the difference satisfies \[ x_{i+1} - x_i = +a \quad \text{or} \quad x_{i+1} - x_i = -b. \]

Note that when \(n = 1\) the sequence consists of a single number which must equal \(s\).

inputFormat

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

\(n\) is the length of the sequence, \(s\) is the desired sum of all sequence elements, and \(a\) and \(b\) determine the allowed transitions: each step is either an increase by \(a\) or a decrease by \(b\).

outputFormat

Output a single integer, the number of sequences satisfying the conditions.

sample

1 5 2 3

1