종속 사건

$N$개의 사건이 있고, 각각 $1$번부터 $N$번까지 번호가 붙어 있다. 각 사건이 일어날 확률은 정확히 하나의 다른 사건, 즉 부모 사건의 발생 여부에 따라 달라진다. 단, 사건 $1$은 독립 사건이다. 다시 말해 $2$번부터 $N$번까지의 각 사건 $i$에 대해 세 값이 주어진다. $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$개의 줄이 주어지며, $i$번째 줄은 사건 $i$를 나타낸다. 첫 줄에는 사건 $1$의 발생 확률에 $10^6$을 곱한 정수 $K$가 하나 주어진다. 그다음 $N-1$개의 줄에는 각각 세 정수 $P_i$, $A_i$, $B_i$가 주어진다. $P_i$는 사건 $i$의 부모 사건, $A_i$는 부모 사건이 일어났을 때 사건 $i$가 일어날 확률에 $10^6$을 곱한 값, $B_i$는 부모 사건이 일어나지 않았을 때 사건 $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 × q ≡ p \pmod{10^9+7}$을 만족하고 $0$ 이상 $10^9+6$ 이하인 값이다. 이 문제의 제약 조건에서 이러한 $R_j$는 항상 존재하고 유일하게 정해진다.

• $1 ≤ T ≤ 100$.
• $1 ≤ P_i$.
• 모든 $j$에 대해 $1 ≤ u_j, v_j ≤ N$이고 $u_j ≠ v_j$.
• $2$번부터 $N$번까지의 각 $i$에 대해 $0 ≤ A_i ≤ 10^6$.
• $2$번부터 $N$번까지의 각 $i$에 대해 $0 ≤ B_i ≤ 10^6$.
• $0 ≤ K ≤ 10^6$.