Background

Since second grade, xtq has loved board games.

Problem Description

xtq has a chessboard with $1$ row and $n+1$ columns, numbered from $0$ to $n$ from left to right. At the initial moment, there is a piece at position $m$.

xtq will perform random operations over time. Specifically, if in a given second the piece is not at $n$, then with probability $prb$ he moves the piece one cell to the left, and with probability $1-prb$ he moves it one cell to the right; otherwise (when the piece is at $n$), he will definitely move the piece one cell to the left.

Now xtq wants to ask you: what is the expected number of seconds until the piece can reach $0$? Since the answer may be very large, and to avoid unnecessary precision errors, you only need to output the answer modulo $10^9+7$ (it can be proven that the answer must be a rational number).

Input Format

One line with four positive integers $n, m, p, q$.

Here, $p, q$ mean $prb = \frac{p}{q}$.

Output Format

One line with one positive integer, representing the expected number of moves modulo $10^9+7$.

3 1 1 3

13

Hint

For $20\%$ of the testdata, $n\le 4$, $1\le p\le q\le 4$, and it is guaranteed that the answer is an integer before taking modulo.

For $40\%$ of the testdata, $n\le 300$.

For $70\%$ of the testdata, $n\le 1000000$.

For $100\%$ of the testdata, $1\le m\le n\le 10^9$, $1\le p\le q\le 10^9$, and $p, q$ are coprime.

In addition, among all testdata points, $30\%$ of the testdata satisfies $prb = \frac{1}{2}$.

The modulo of a rational number with respect to a prime $p$ is defined as follows:

Let the result of $\frac{a}{b}$ modulo $p$ be $x$. Then it must satisfy $0\le x<p$ and $a \equiv bx (mod p)$.

It is guaranteed that for $100\%$ of the testdata, such an $x$ satisfying the requirements always exists.

Translated by ChatGPT 5