Round H - D(Dependent Events)

#include <bits/stdc++.h>
#define ull long long
using namespace std;
void dfs(int here, vector<bool>& visited, vector<vector<int>>& vt,  vector<vector<int>>& parent, vector<vector<ull>>& pyp, vector<vector<ull>>& pnp, vector<ull>& p, vector<int>& depth) {
	visited[here] = true;

	for(int i : vt[here]) {
		if(visited[i]) continue;
		depth[i] = depth[parent[i][0]]+1;
		for(int j = 1; j < 20; j++) {
			parent[i].push_back(parent[parent[i][j-1]][j-1]);
			
			pyp[i].push_back((pyp[i][j-1]*pyp[parent[i][j-1]][j-1]+pnp[i][j-1]*(1-pyp[parent[i][j-1]][j-1]))%1000000007);
			pnp[i].push_back((pyp[i][j-1]*pnp[parent[i][j-1]][j-1]+pnp[i][j-1]*(1-pnp[parent[i][j-1]][j-1]))%1000000007);
		}
		p[i] = (pyp[i][0]*p[parent[i][0]]+pnp[i][0]*(1-p[parent[i][0]]))%1000000007;
		dfs(i, visited, vt, parent, pyp, pnp, p, depth);
	}
}
//Pr[a|c] = Pr[a|d]*Pr[d|c] + Pr[a|!d]*Pr[!d|c]
//Pr[a|!c] = Pr[a|d]*Pr[d|!c] + Pr[a|!d]*Pr[!d|!c]
//Pr[a&b] = Pr[a|c]*Pr[b|c]*Pr[c] + Pr[a|!c]*Pr[b|!c]*Pr[!c]
void lca(int x, int y, vector<vector<int>>& parent, vector<int>& depth, vector<vector<ull>>& pyp, vector<vector<ull>>& pnp, vector<ull>& p) {
	if(depth[x] < depth[y]) {
		int temp = x;
		x = y;
		y = temp;
	}
	ull prxyp = 1;
	ull prxnp = 0;
	ull pryyp = 1;
	ull prynp = 0;
	for(int i = 19; i >= 0; i--) {
		if(depth[x]-depth[y] >= (1<<i)) {
			ull temp1 = prxyp;
			ull temp2 = prxnp;
			prxyp = (temp1*pyp[x][i]+temp2*(1-pyp[x][i]))%1000000007;
			prxnp = (temp1*pnp[x][i]+temp2*(1-pnp[x][i]))%1000000007;
			x = parent[x][i];
		}
	}
	if(x == y) {
		prxyp = (prxyp*p[y])%1000000007;
		if(prxyp < 0) prxyp += 1000000007;
		printf("%llu ", prxyp);
		return;
	}
	ull temp1, temp2;
	for(int i = 19; i >= 0; i--) {
		if(parent[x][i] != parent[y][i]) {
			temp1 = prxyp;
			temp2 = prxnp;
			prxyp = (temp1*pyp[x][i]+temp2*(1-pyp[x][i]))%1000000007;
			prxnp = (temp1*pnp[x][i]+temp2*(1-pnp[x][i]))%1000000007;
			
			temp1 = pryyp;
			temp2 = prynp;
			pryyp = (temp1*pyp[y][i]+temp2*(1-pyp[y][i]))%1000000007;
			prynp = (temp1*pnp[y][i]+temp2*(1-pnp[y][i]))%1000000007;
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	temp1 = prxyp;
	temp2 = prxnp;
	prxyp = (temp1*pyp[x][0]+temp2*(1-pyp[x][0]))%1000000007;
	prxnp = (temp1*pnp[x][0]+temp2*(1-pnp[x][0]))%1000000007;

	temp1 = pryyp;
	temp2 = prynp;
	pryyp = (temp1*pyp[y][0]+temp2*(1-pyp[y][0]))%1000000007;
	prynp = (temp1*pnp[y][0]+temp2*(1-pnp[y][0]))%1000000007;
	
	temp1 = (prxyp*pryyp)%1000000007;
	temp2 = (prxnp*prynp)%1000000007;
	temp1 = (temp1*p[parent[x][0]] + temp2*(1-p[parent[x][0]]))%1000000007;
	if(temp1 < 0) temp1 += 1000000007;
	printf("%llu ", temp1);
}
int main() {
	int T;
	scanf("%d", &T);
	
	for(int tc = 1; tc <= T; tc++) {
		int N, Q;
		scanf("%d %d", &N, &Q);
		ull K;
		scanf("%llu", &K);
		
		vector<bool> visited; for(int i = 0; i < N; i++) visited.push_back(false);// visited[0] = true;
		vector<vector<int>> vt(N);
		vector<vector<int>> parent(N); for(int i = 0; i < 20; i++) parent[0].push_back(0);
		vector<vector<ull>> pyp(N); for(int i = 0; i < 20; i++) pyp[0].push_back(1);
		vector<vector<ull>> pnp(N); for(int i = 0; i < 20; i++) pnp[0].push_back(0);
		vector<ull> p(N); p[0] = (K*142857001)%1000000007;
		vector<int> depth(N); depth[0] = 0;
		for(int i = 1; i < N; i++) {
			int P;
			ull A, B;
			scanf("%d %llu %llu", &P, &A, &B);
			P--;
			parent[i].push_back(P);
			vt[i].push_back(P);
			vt[P].push_back(i);
			pyp[i].push_back((A*142857001)%1000000007);
			pnp[i].push_back((B*142857001)%1000000007);
		}
		
		vector<pair<int, int>> queries;
		for(int i = 0; i < Q; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			queries.push_back(make_pair(u-1,v-1));
		}
		dfs(0, visited, vt, parent, pyp, pnp, p, depth);
		
		printf("Case #%d: ", tc);
		for(int i = 0; i < Q; i++)
			lca(queries[i].first, queries[i].second, parent, depth, pyp, pnp, p);
		printf("\n");
	}
}