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 ~\triangle (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 ~(\triangle (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 ~PQ^{-1} \pmod{10^9 + 7}~. That is, output a number ~R~ such that ~0 \le R < 10^9 + 7~ and ~P \equiv RQ \pmod{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.