P16822 [Lanquiao Cup 2026 National Python B] Zero-Segment Integral.

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 $$ S = \sum_{i=1}^{k-1} l_i \times l_{i+1} $$ 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 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 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$.

### 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: | State | Zero-segment lengths | Value | |:-:|:-:|:-:| | $0010$ | $2, 1$ | $2$ | | $0100$ | $1, 2$ | $2$ | | $0101$ | $1, 1$ | $1$ | | $0110$ | $1, 1$ | $1$ | | $1010$ | $1, 1$ | $1$ | 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