Wesley 创建了一个包含 $N$ 个顶点的图 $G$。对于每一对顶点 $\{u, v\}$，它们之间存在边的概率为 $\frac{p}{q}$。这些概率相互独立。

令 $\Delta(G)$ 表示图 $G$ 中三角形的数量。三角形是指由 3 条边连接的 3 个顶点的集合。

请帮助 Wesley 求出 $(\Delta(G))^2$ 的期望值。

输入格式

第 1 行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试用例的数量。

接下来 $T$ 行，第 $i$ 行包含三个整数 $N, p, q$ ($3 \le N \le 10^6, 1 \le p < q \le 10^6$)，用空格分隔。

输出格式

输出 $T$ 行，每行对应一个测试用例的答案。

假设第 $i$ 个测试用例的答案为最简分数 $\frac{P}{Q}$。请输出 $PQ^{-1} \pmod{10^9 + 7}$。即输出一个整数 $R$，满足 $0 \le R < 10^9 + 7$ 且 $P \equiv RQ \pmod{10^9 + 7}$。

样例

输入格式 1

1
3 1 2

输出格式 1

125000002

说明

当 $N=3$ 且概率为 $1/2$ 时，三角形存在的概率为 $(1/2)^3 = 1/8$。 $\Delta(G)$ 的取值为：若存在三角形则为 1，否则为 0。 $E[(\Delta(G))^2] = 1^2 \times (1/8) + 0^2 \times (7/8) = 1/8$。 $8^{-1} \pmod{10^9+7} = 125000001 \times 1 = 125000002$。