2022 Fall Waterloo Local Contest, Problem C

Wesley creates a graph $G$ that contains $N$ vertices. For each pair of vertices $\{u,v\}$, there is a probability of $\frac{p}{q}$ that an edge exists between $u$ and $v$. The probabilities are independent of each other.

Let $\mathrm{△}(G)$ denote the number of triangles in $G$. A triangle is a set of $3$ vertices that are connected by $3$ edges.

Please help Wesley find the expected value of $(\mathrm{△}(G){)}^2$.

Input Specification

Line $1$ contains integer $T$ $(1\le T\le {10}^6)$, the number of cases.

$T$ lines follow. The $i^{\text{th}}$ line contains integers $N,p,q$ $(3\le N\le {10}^6,1\le p<q\le {10}^6)$, separated by spaces.

Output Specification

Output $T$ lines, one line for each case.

Suppose the answer to the $i^{\text{th}}$ case is $\frac{P}{Q}$, in lowest terms. Output $P{Q}^{-1}(\mathrm{mod}{10}^9+7)$. That is, output a number $R$ such that $0\le R<{10}^9+7$ and $P\equiv RQ(\mathrm{mod}{10}^9+7)$.

Sample Input

2
3 1 2
4 1 2

Sample Output

125000001
875000007

Note

The original problem did not have a sample.