Dependent Events

There are $N$ events, numbered $1$ through $N$. The probability that each event occurs depends on whether exactly one other event, called its parent event, occurs. Event $1$ is the exception: it is an independent event. That is, for each event $i$ from $2$ to $N$, three values are given: $P_i$, the parent event of event $i$; $A_i$, the probability that event $i$ occurs if its parent event occurs; and $B_i$, the probability that event $i$ occurs if its parent event does not occur. For event $1$, its probability of occurrence $K$ is given. There are $Q$ queries to answer. Each query consists of two distinct events $u_j$ and $v_j$, and you need to find the probability that both events $u_j$ and $v_j$ have occurred.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integers $N$ and $Q$, the number of events and the number of queries. $N$ lines follow. The $i$-th line describes event $i$. The first line contains a single integer $K$, the probability of occurrence of event $1$ multiplied by $10^6$. Each of the next $N-1$ lines consists of three integers $P_i$, $A_i$, and $B_i$: the parent event of event $i$, the probability of occurrence of event $i$ if its parent event occurs multiplied by $10^6$, and the probability of occurrence of event $i$ if its parent event does not occur multiplied by $10^6$. Then $Q$ lines follow, describing the queries. Each of these lines contains two distinct integers $u_j$ and $v_j$. For each query, find the probability that both events $u_j$ and $v_j$ occurred.

For each test case, output one line containing Case #x: R1 R2 R3 … RQ, where $x$ is the test case number (starting from 1) and $R_j$ is the sought probability computed for the $j$-th query modulo $10^9+7$, defined precisely as follows. Represent the answer of the $j$-th query as an irreducible fraction $\frac{p}{q}$. The number $R_j$ then must satisfy the modular equation $R_j × q ≡ p \pmod{10^9+7}$ and be between $0$ and $10^9+6$, inclusive. Under the constraints of this problem such a number $R_j$ always exists and is uniquely determined.

• $1 ≤ T ≤ 100$.
• $1 ≤ P_i$.
• $1 ≤ u_j, v_j ≤ N$ and $u_j ≠ v_j$, for all $j$.
• $0 ≤ A_i ≤ 10^6$, for each $i$ from $2$ to $N$.
• $0 ≤ B_i ≤ 10^6$, for each $i$ from $2$ to $N$.
• $0 ≤ K ≤ 10^6$.