题目描述

伯利兰迪亚是一个庞大的国家，包含 $n$ 个城市。伯利兰迪亚的道路网络可以看作一棵有根树，总共有 $n - 1$ 条道路，从任意城市到另一城市有且仅有一条路径，且不会重复经过同一城市。为了便于描述国家结构，对于每个城市 $i$，固定了一个城市 $p_i$，表示从城市 $i$ 前往城市 $1$ 时需要首先到达的城市。换句话说，如果将树以城市 $1$ 为根，$p_i$ 即为城市 $i$ 的直接父节点。

伯利兰迪亚的每个城市都有一座加油站。这些加油站的定价方式很特别，每座加油站都有一个固定的价格范围，愿意在这个范围内销售汽油。城市 $i$ 的加油站愿意以任何价格从 $l_i$ 到 $r_i$（包含边界）出售汽油。

伯利兰迪亚的国王是个模范的家庭人，在 $m$ 年内，他每年都会有两个儿子出生。国王的孩子从小就参与国家事务，每年年底他们会检查汽油价格的公平性。从出生开始，在第 $i$ 年出生的国王孩子分别负责检查从城市 $a_i$ 到城市 $b_i$ 和从城市 $c_i$ 到城市 $d_i$ 的路径上的汽油价格。

检查过程如下：两个孩子同时分别从城市 $a_i$ 和 $c_i$ 开始他们的旅程。第 $i$ 年出生的第一个儿子沿着从城市 $a_i$ 到城市 $b_i$ 的路径前进，第二个儿子沿着从城市 $c_i$ 到城市 $d_i$ 的路径前进。他们会检查城市 $a_i$ 的汽油价格是否与城市 $c_i$ 的价格一致；接着检查从 $a_i$ 到 $b_i$ 路径上的第二个城市与从 $c_i$ 到 $d_i$ 路径上的第二个城市的汽油价格是否一致；以此类推，直到检查城市 $b_i$ 和 $d_i$ 的价格是否一致。保证从城市 $a_i$ 到 $b_i$ 的路径长度与从城市 $c_i$ 到 $d_i$ 的路径长度相等。

加油站必须严格遵守法律，因此所有汽油价格的检查都不能发现违规行为。请帮助伯利兰迪亚的加油站计算，在 $m$ 年内他们有多少种方式可以设定汽油价格。换句话说，对于从 $1$ 到 $m$ 的每个 $i$，计算在所有加油站设定汽油价格的方式数量，使得在第 $i$ 年及之前的孩子们进行检查时没有发现违规，并且每个加油站的价格都在其允许范围内。由于方式数量可能很大，请将答案对 $10^{9} + 7$ 取模。

输入格式

第一行包含一个整数 $n$ $(1 \le n \le 200000)$，表示伯利兰迪亚的城市数量。

第二行包含 $n - 1$ 个整数 $p_2, p_3, p_4, \ldots, p_n$ $(1 \le p_i \le n)$，其中 $p_i$ 表示从城市 $i$ 到城市 $1$ 路径上的下一个城市。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ $(1 \le l_i \le r_i < 10^{9}+7)$，定义第 $i$ 号加油站的允许价格范围。

接下来的一行包含一个整数 $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)$，定义第 $i$ 年出生的国王孩子将检查的两个路径。保证从城市 $a_i$ 到 $b_i$ 的路径长度等于从城市 $c_i$ 到 $d_i$ 的路径长度。

输出格式

输出 $m$ 行，每行一个数字。第 $i$ 行的数字应等于在所有城市设定汽油价格的方式数量，使得第 $i$ 年及之前出生的国王孩子在检查时未发现违规。答案请对 $10^{9} + 7$ 取模。

5
1 1 2 2
2 4
1 3
1 3
2 4
4 4
4
1 1 2 2
1 2 2 1
3 4 4 3
3 4 3 5

18
18
4
0

8
1 2 3 4 5 8 6
3 7
2 6
3 8
5 10
5 8
2 9
3 8
6 8
4
1 3 7 6
4 1 5 7
1 7 7 1
1 8 2 7

720
120
120
1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。