Problem Description

There are $N$ events, numbered $1$ through $N$. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event $1$, which is an independent event. In other words, for each event from $2$ to $N$, $3$ values are given: $P_i$ denoting the parent event of event $i$, $A_i$ denoting the probability of occurrence of event $i$ if its parent event occurs, and $B_i$ denoting the probability of occurrence of event $i$ if its parent event does not occur. For event $1$, its probability of occurrence $K$ is given. There are $Q$ queries that we want to answer. Each query consists of $2$ distinct events, $u_j$ and $v_j$, and you need to find the probability that both events $u_j$ and $v_j$ have occurred.

Input Format

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$ denoting the number of events and number of queries, respectively. $N$ lines follow. The $i$-th line describes event $i$. The first line contains a single integer $K$ denoting 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$ denoting 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$, respectively. 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.

Output Format

For each test case, output one line containing Case #$x$: $R_1$ $R_2$ $R_3$ $\cdots$ $R_Q$, where $x$ is the test case number (starting from $1$) and $R_j$ is the sought probability computed for $j$-th query modulo $10^9 + 7$, which is defined precisely as follows. Represent the answer of $j$-th query as an irreducible fraction $\frac{p}{q}$. The number $R_j$ then must satisfy the modular equation $R_j \times q \equiv p \pmod{(10^9 + 7)}$, and be between $0$ and $10^9 + 6$, inclusive. It can be shown that under the constraints of this problem such a number $R_j$ always exists and is uniquely determined.

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

Hint

For Sample Case #$1$, for the first query, the probability that both events $1$ and $5$ occurred is given by (the probability that event $1$ occurred) $\times$ (probability that event $5$ occurs given event $1$ occurred). Event $1$ would occur with probability $0.2$. Given that event $1$ occurred, the probability that event $4$ occurs is $0.8$. Therefore, the probability of occurrence of event $5$ given that event $1$ occurred is $0.2 \times 0.8 + 0.4 \times 0.2 = 0.24$ (probability of event $5$ occurring given than event $4$ occurred + probability of event $5$ occurring given that event $4$ did not occur). The probability that both events $1$ and $5$ occurred is $0.2 \times 0.24 = 0.048$. The answer $0.048$ can be converted into fraction of $\frac{6}{125}$, and one can confirm that the $136000001$ satisfies the conditions mentioned in the output section as $136000001 \times 125 \equiv 6 \pmod{(10^9 + 7)}$ and is uniquely determined. For the second query, the probability that both events $5$ and $3$ occurred is $0.10352$.

For Sample Case #$2$, for the first query, the probability that both events $1$ and $2$ occurred is given by (the probability that event $1$ occurred) $\times$ (probability that event $2$ occurs given event $1$ occurred). As $1$ is the parent event of event $2$, the probability of event $2$ occurring given event $1$ occurred is $A_2$ which is $0.1$. Hence, the probability that both events $1$ and $2$ occurred is $0.3 \times 0.1$. Hence, the output will be $3 \times 10^{-2} \bmod (10^9 + 7) = 710000005$. For the second query, the probability of occurrence of both events $2$ and $4$ is $0.057$.

Limits

$1 \le T \le 100$.

$1 \le P_i < i$, for each $i$ from $2$ to $N$.

$1 \le u_j, v_j \le N$ and $u_j \ne v_j$, for all $j$.

$0 \le A_i \le 10^6$, for each $i$ from $2$ to $N$.

$0 \le B_i \le 10^6$, for each $i$ from $2$ to $N$.

$0 \le K \le 10^6$.

Test Set $1$

$2 \le N \le 1000$.

$1 \le Q \le 1000$.

Test Set $2$

For at most $5$ cases:

$2 \le N \le 2 \times 10^5$.

$1 \le Q \le 2 \times 10^5$.

For the remaining cases:

$2 \le N \le 1000$.

$1 \le Q \le 1000$.