Problem Description

Xiao Lan is doing a random string experiment. She has a sequence of length $N$, and initially all positions are $0$. After the experiment starts, each position in the sequence independently turns into $1$ with probability $\frac{P}{Q}$, and all other positions remain $0$.

After the experiment ends, all consecutive $0$'s are separated by $1$'s into several segments.

Let the lengths of the non-empty consecutive zero segments from left to right be $l_1, l_2, \dots, l_k$.

Xiao Lan defines the value of the sequence as

That is, the value is the sum of the products of the lengths of all adjacent zero segments. If the number of zero segments is less than $2$, then the value is $0$.

Now, please compute the expected value of $S$, and output the result modulo $10^9 + 7$.

Input Format

Input one line containing three integers $N, P, Q$, representing the length of the sequence, and the numerator and denominator of the probability that each position turns into $1$.

It is guaranteed that $0 \le P \le Q$, $Q > 0$, and $\gcd(P, Q) = 1$.

Output Format

Output one line with one integer, representing the expected value of $S$ modulo $10^9 + 7$.

If the expected value is a fraction $\frac{a}{b}$, output $a \times b^{-1} \bmod (10^9 + 7)$, where $b^{-1}$ denotes the multiplicative inverse of $b$ modulo $10^9 + 7$.

4 1 2

937500007

Hint

Sample Explanation

When $N=4$ and each position turns into $1$ with probability $\frac{1}{2}$, all $2^4$ states occur with equal probability, but only the following states have a non-zero value:

Therefore, $E[S] = \frac{2+2+1+1+1}{16} = \frac{7}{16}$. Modulo $10^9 + 7$, $\frac{7}{16}$ equals $937500007$.

Constraints and Conventions for Test Cases

For $30\%$ of the test cases, $1 \le N \le 20$.

For all test cases, $1 \le N \le 10^6$, $0 \le P \le Q \le 10^9$, and $\gcd(P, Q) = 1$.

Translated by ChatGPT 5