Problem Description

Observe the sequence:

$1,3,0,2,-1,1,-2, \cdots$.

In this sequence, each next term is always either increased by $2$ from the previous term, or decreased by $3$.

Dongdong is very curious about this kind of sequence. He wants to know: how many integer sequences are there with length $n$ and sum $s$, such that each next term is always either increased by $a$ from the previous term, or decreased by $b$?

Input Format

The first line contains four integers $n, s, a, b$, with the meanings described above.

Output Format

Output one line containing one integer, the number of valid sequences. Since this number is very large, output the remainder of the answer modulo $100000007$.

4 10 2 3

2

Hint

【Sample Explanation】

The two sequences are $2\ 4\ 1\ 3$ and $7\ 4\ 1\ -2$.

【Constraints】

For $10\%$ of the testdata: $1 \le n \le 5$, $0 \le s \le 5$, $1 \le a, b \le 5$.

For $30\%$ of the testdata: $1 \le n \le 30$, $0 \le s \le 30$, $1 \le a, b \le 30$.

For $50\%$ of the testdata: $1 \le n \le 50$, $0 \le s \le 50$, $1 \le a, b \le 50$.

For $70\%$ of the testdata: $1 \le n \le 100$, $0 \le s \le 500$, $1 \le a, b \le 50$.

For $100\%$ of the testdata: $1 \le n \le 1000$, $-10^9 \le s \le 10^9$, $1 \le a, b \le 10^6$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2014, the 5th Provincial Contest.

Translated by ChatGPT 5