휘발유 가격

베를란디야는 $n$개의 도시로 이루어진 거대한 나라다. 도로망은 뿌리가 있는 트리 모양이며, 나라 전체 도로는 $n - 1$개다. 두 도시를 잇는 길은 도시를 두 번 방문하지 않는 한 정확히 하나뿐이다. 각 도시 $i$마다 도시 1로 가려면 도시 $i$에서 처음으로 가야 하는 도시 $p_i$가 정해져 있다. 즉, 도시 1을 루트로 하여 트리를 매달았을 때 $p_i$는 도시 $i$의 부모다. 각 도시에는 주유소가 하나씩 있다. 주유소 $i$는 $l_i$ 이상 $r_i$ 이하의 어떤 가격으로든 휘발유를 팔 수 있다. 왕에게는 $m$년 동안 해마다 아들 둘이 태어난다. 아들들은 어릴 때부터 국정에 참여하며, 매년 말에 휘발유 가격이 공정한지 점검한다. $i$년에 태어난 아들들은 $a_i$에서 $b_i$까지 가는 길과 $c_i$에서 $d_i$까지 가는 길의 가격을 점검한다. 점검은 다음과 같이 진행된다. 두 아들은 동시에 $a_i$와 $c_i$에서 출발한다. 첫째 아들은 $a_i$에서 $b_i$까지, 둘째 아들은 $c_i$에서 $d_i$까지 걷는다. 먼저 $a_i$의 가격과 $c_i$의 가격이 같은지 확인한다. 다음으로 두 경로의 두 번째 도시 가격이 같은지 확인한다. 세 번째, 네 번째 도시도 같은 방식으로 짝지어 확인하고, 마지막으로 $b_i$의 가격과 $d_i$의 가격이 같은지 확인한다. 두 경로의 길이는 항상 같다고 보장된다. 주유소는 법을 엄격히 지켜야 하므로 어떤 점검에서도 위반이 나오면 안 된다. 주유소들이 $m$년 동안 가격을 정하는 방법의 수를 구한다. 즉, 각 $i$ ($1 \le i \le m$)에 대해, 처음 $i$쌍의 아들이 태어난 뒤 모든 점검을 통과하고 모든 주유소의 가격이 허용 범위 안에 있도록 가격을 정하는 방법의 수를 구한다. 답은 $10^9+7$로 나눈 나머지로 출력한다.

첫 줄에 도시의 수 $n$ ($1 \le n \le 200000$)이 주어진다. 둘째 줄에는 $n-1$개의 정수 $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le n$)이 주어진다. 이어지는 $n$개의 줄에는 주유소 $i$의 허용 가격 범위 $l_i$, $r_i$ ($1 \le l_i \le r_i < 10^9+7$)가 주어진다. 다음 줄에는 $m$ ($1 \le m \le 200000$)이 주어진다. 이어지는 $m$개의 줄에는 $a_i$, $b_i$, $c_i$, $d_i$ ($1 \le a_i, b_i, c_i, d_i \le n$)가 주어진다. $a_i$에서 $b_i$까지의 길이와 $c_i$에서 $d_i$까지의 길이는 같다고 보장된다.

$m$개의 줄에 각각 정수 하나를 출력한다. $i$번째 줄에는 $i$년까지 태어난 아들들이 위반을 찾지 못하는 가격 설정 방법의 수를 $10^9+7$로 나눈 나머지로 출력한다.

첫 번째 예시를 살펴보자. 처음 두 아들이 태어난 뒤 도시 1과 2의 가격은 같아야 한다. 두 도시의 허용 범위에 모두 들어가는 공통 가격을 고르는 방법은 2가지다. 따라서 전체 방법 수는 $2 \cdot 3 \cdot 3 \cdot 1 = 18$이다. 두 번째 쌍은 경로 $1 - 2$와 $2 - 1$을 점검한다. 도시 1과 2의 가격은 이미 같으므로 두 번째 쌍이 태어나도 답은 바뀌지 않는다. 세 번째 쌍은 경로 $3 - 1 - 2 - 4$와 $4 - 2 - 1 - 3$을 점검한다. 그러면 도시 3과 4의 가격이 같아야 하고, 도시 1과 2의 가격도 같아야 한다. 도시 1과 2는 이미 일치한다. 도시 3과 4가 각자의 범위 안에서 공통 가격을 고르는 방법은 2가지다. 따라서 전체 방법 수는 $2 \cdot 2 \cdot 1 = 6$이다. 네 번째 쌍은 경로 $3 - 1 - 2 - 4$와 $3 - 1 - 2 - 5$를 점검한다. 그러면 도시 4와 5의 가격이 같아야 한다. 도시 3과 4는 이미 일치하므로, 도시 3, 4, 5의 가격은 모두 같아야 한다. 도시 3의 가격은 3 이하여야 하고, 도시 5의 가격은 4 이상이어야 한다. 따라서 네 번째 쌍이 태어난 뒤에는 모든 점검을 통과하면서 가격을 허용 범위 안에 두는 방법이 없다.