종속 사건

$\mathbf{N}$개의 사건이 있으며, $1$부터 $\mathbf{N}$까지 번호가 매겨져 있다. 사건 $1$은 독립 사건이지만, 이를 제외한 각 사건의 발생 확률은 부모 사건이라고 하는 정확히 하나의 다른 사건의 발생 여부에 따라 달라진다. 다시 말해, $2$부터 $\mathbf{N}$까지의 각 사건에 대해 $3$개의 값이 주어진다. $\mathbf{P_{i}}$은 사건 $i$의 부모 사건을 나타내고, $\mathbf{A_{i}}$은 부모 사건이 발생했을 때 사건 $i$이 발생할 확률을 나타내며, $\mathbf{B_{i}}$은 부모 사건이 발생하지 않았을 때 사건 $i$이 발생할 확률을 나타낸다. 사건 $1$에 대해서는 발생 확률 $\mathbf{K}$가 주어진다. 답해야 할 쿼리가 $\mathbf{Q}$개 있다. 각 쿼리는 서로 다른 $2$개의 사건 $\mathbf{u_{j}}$와 $\mathbf{v_{j}}$로 이루어지며, 사건 $\mathbf{u_{j}}$와 $\mathbf{v_{j}}$가 모두 발생했을 확률을 구해야 한다.

제한

시간 제한: 60초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $2$부터 $\mathbf{N}$까지의 각 $i$에 대해 $1 \le \mathbf{P_{i}} \lt \mathbf{i}$. 모든 $j$에 대해 $1 \le \mathbf{u_{j}}, \mathbf{v_{j}} \le \mathbf{N}$ 및 $\mathbf{u_{j}} \neq \mathbf{v_{j}}$. $2$부터 $\mathbf{N}$까지의 각 $i$에 대해 $0 \le \mathbf{A_{i}} \le 10^6$. $2$부터 $\mathbf{N}$까지의 각 $i$에 대해 $0 \le \mathbf{B_{i}} \le 10^6$. $0 \le \mathbf{K} \le 10^6$.

테스트 세트 1

$2 \le \mathbf{N} \le 1000$. $1 \le \mathbf{Q} \le 1000$.

테스트 세트 2

최대 5개의 케이스에 대해: $2 \le \mathbf{N} \le 2 \times 10^{5}$. $1 \le \mathbf{Q} \le 2 \times 10^{5}$.

나머지 케이스에 대해: $2 \le \mathbf{N} \le 1000$. $1 \le \mathbf{Q} \le 1000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 각각 사건의 수와 쿼리의 수를 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{Q}$이 주어진다. 이어서 $\mathbf{N}$개의 줄이 주어진다. $i$번째 줄은 사건 $i$을 설명한다. 첫 번째 줄에는 사건 $1$의 발생 확률에 $10^6$을 곱한 값을 나타내는 정수 $\mathbf{K}$ 하나가 주어진다. 다음 $\mathbf{N}-1$개의 각 줄에는 세 정수 $\mathbf{P_{i}}$, $\mathbf{A_{i}}$, $\mathbf{B_{i}}$이 주어진다. 이들은 각각 사건 $i$의 부모 사건, 부모 사건이 발생했을 때 사건 $i$이 발생할 확률에 $10^6$을 곱한 값, 부모 사건이 발생하지 않았을 때 사건 $i$이 발생할 확률에 $10^6$을 곱한 값을 나타낸다. 그다음 쿼리를 설명하는 $\mathbf{Q}$개의 줄이 주어진다. 각 줄에는 서로 다른 두 정수 $\mathbf{u_{j}}$와 $\mathbf{v_{j}}$이 주어진다. 각 쿼리에 대해 사건 $\mathbf{u_{j}}$와 $\mathbf{v_{j}}$가 모두 발생했을 확률을 구한다.

각 테스트 케이스마다 Case #$x$: $R_{1} \ R_{2} \ R_{3} \ \dots \ R_{Q}$를 포함하는 한 줄을 출력한다. 여기서 $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$ 이상 $10^9+6$ 이하여야 한다. 이 문제의 제한 조건에서는 이러한 수 $R_{j}$가 항상 존재하고 유일하게 결정됨을 보일 수 있다.

예제 케이스 #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$이 발생할 확률은 $\mathbf{A_{2}}$이며, 이는 $0.1$이다. 따라서 사건 $1$와 $2$가 모두 발생했을 확률은 $0.3 \times 0.1$이다. 따라서 출력은 $3 \times 10^{-2} \bmod (10^9+7) = 710000005$가 된다. 두 번째 쿼리에서 사건 $2$와 $4$가 모두 발생할 확률은 $0.057$이다.