有 N 个事件，编号为 1 到 N。每个事件的发生概率依赖于恰好另一个事件（称为父事件）的发生，但事件 1 除外，它是一个独立事件。换句话说，对于每个事件 i（2 \le i \le N），给定三个值：P_i 表示事件 i 的父事件，A_i 表示当父事件发生时事件 i 发生的概率，B_i 表示当父事件不发生时事件 i 发生的概率。对于事件 1，其发生概率 K 已给出。我们需要回答 Q 个查询。每个查询包含两个不同的事件 u_j 和 v_j，你需要求出事件 u_j 和 v_j 同时发生的概率。
输入的第一行给出测试用例的数量 T。接下来有 T 个测试用例。
每个测试用例的第一行包含两个整数 N 和 Q，分别表示事件的数量和查询的数量。接下来 N 行描述每个事件。第一行包含一个整数 K，表示事件 1 的发生概率乘以 10^6。接下来的 N-1 行，每行包含三个整数 P_i、A_i 和 B_i，分别表示事件 i 的父事件、当父事件发生时事件 i 的发生概率乘以 10^6，以及当父事件不发生时事件 i 的发生概率乘以 10^6。然后，有 Q 行描述查询，每行包含两个不同的整数 u_j 和 v_j。对于每个查询，求出事件 u_j 和 v_j 同时发生的概率。
对于每个测试用例，输出一行，格式为 Case #x: R1 R2 R3 ... RQ，其中 x 是测试用例编号（从 1 开始），R_j 是为第 j 个查询计算出的概率对 10^9 + 7 取模的结果，其精确定义如下。将第 j 个查询的答案表示为最简分数 \frac{p}{q}，则 R_j 必须满足模方程 R_j \times q \equiv p \pmod{10^9 + 7}，且 0 \le R_j \le 10^9 + 6。可以证明，在本问题的限制下，这样的 R_j 总是存在且唯一确定。
2 5 2 200000 1 400000 300000 2 500000 200000 1 800000 100000 4 200000 400000 1 5 3 5 4 2 300000 1 100000 100000 2 300000 400000 3 500000 600000 1 2 2 4
Case #1: 136000001 556640004 Case #2: 710000005 849000006
对于样例 #1，第一个查询：事件 1 和 5 同时发生的概率为（事件 1 发生的概率）\times（在事件 1 发生的条件下事件 5 发生的概率）。事件 1 发生的概率为 0.2。已知事件 1 发生，事件 4 发生的概率为 0.8。因此，在事件 1 发生的条件下事件 5 发生的概率为 0.2 \times 0.8 + 0.4 \times 0.2 = 0.24（事件 4 发生时事件 5 发生的概率加上事件 4 不发生时事件 5 发生的概率）。事件 1 和 5 同时发生的概率为 0.2 \times 0.24 = 0.048。答案 0.048 可化为分数 \frac{6}{125}，可以验证 136000001 满足输出部分所述的条件：136000001 \times 125 \equiv 6 \pmod{10^9 + 7}，且唯一确定。第二个查询：事件 5 和 3 同时发生的概率为 0.10352。
对于样例 #2，第一个查询：事件 1 和 2 同时发生的概率为（事件 1 发生的概率）\times（在事件 1 发生的条件下事件 2 发生的概率）。由于 1 是事件 2 的父事件，给定事件 1 发生时事件 2 发生的概率即为 A_2 = 0.1。因此，事件 1 和 2 同时发生的概率为 0.3 \times 0.1 = 0.03。输出为 3 \times 10^{-2} \bmod (10^9 + 7) = 710000005。第二个查询：事件 2 和 4 同时发生的概率为 0.057。