25929번 - Squaring the Triangle 다국어

문제

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

Let $∆(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 $(∆(G))^2$.

입력

Line 1ドル$ contains integer $T$ (1ドル ≤ T ≤ 10^6$), the number of cases. $T$ lines follow. The $i$^th line contains integers $N,ドル $p,ドル $q$ (3ドル ≤ N ≤ 10^6,ドル 1ドル ≤ p < q ≤ 10^6$), separated by spaces.

출력

Output $T$ lines, one line for each case. Suppose the answer to the $i$^th case is $\dfrac{P}{Q},ドル in lowest terms. Output $PQ^{-1} \pmod {10^9 + 7}$. That is, output a number $R$ such that 0ドル ≤ R < 10^9 + 7$ and $P ≡ RQ \pmod {10^9 + 7}$.

제한

힌트