CF1801E.Gasoline prices

Berland — is a huge country consisting of $n$ cities. The road network of Berland can be represented as a root tree, that is, there is only $n - 1$ road in the country, and you can get from any city to any other exactly one way, if you do not visit any city twice. For the convenience of representing the country, for each city $i$, the city $p_i$ is fixed, equal to the first city to which you need to go from the city $i$ to get to the city $1$. In other words, the city $p_i$ is equal to the ancestor of the city $i$ if the tree is hung for the city $1$.

There is one gas station in each city of Berland. Gas stations have special pricing, and for each gas station there is a fixed range of prices for which they are ready to sell gasoline. A gas station in the city with the number $i$ is ready to sell gasoline at any price from $l_i$ to $r_i$ inclusive.

The King of Berland — is an exemplary family man, and for $m$ years, two sons were born to him every year. The king's children have been involved in public affairs since early childhood, and at the end of each year they check the honesty of gasoline prices. From birth, the king's children, who are born in the year $i$, are responsible for checking gasoline prices on the ways from the city of $a_i$ to the city of $b_i$ and from the city of $c_i$ to the city of $d_i$, respectively.

The check is as follows: both children simultaneously start their journey from the cities $a_i$ and $c_i$, respectively. The first son of the king, born in the year $i$, moves along the path from the city $a_i$ to the city $b_i$, and the second — from the city $c_i$ to the city $d_i$. Children check that the price of gasoline in the city of $a_i$ coincides with the price of gasoline in the city of $c_i$. Next, they check that the price of gasoline in the second city on the way from $a_i$ to $b_i$ coincides with the price in the second city on the way from $c_i$ to $d_i$. Then they repeat the same thing for a couple of third cities on their paths and so on. At the end, they check that the price of gasoline in the city of $b_i$ coincides with the price of gasoline in the city of $d_i$. It is guaranteed that the length of the path from the city $a_i$ to the city $b_i$ coincides with the length of the path from the city $c_i$ to the city $d_i$.

Gas stations must strictly obey the laws, and therefore all checks of gasoline prices should not reveal violations. Help Berland gas stations find out how many ways they can set gasoline prices for $m$ years. In other words, for each $i$ from $1$ to $m$, calculate how many ways you can set gasoline prices at all gas stations so that after the birth of the first $i$ pairs of the king's children, all their checks did not reveal violations, and at any gas station the price was in the acceptable price range. Since the number of such methods can be large, calculate the answer modulo $10^9 + 7$.

Berland 是一个由 $n$ 座城市组成的幅员辽阔的国家。Berland 的公路网络可表示为一棵有根树，即全国仅有 $n - 1$ 条道路，且任意两座城市之间存在唯一一条不重复经过任一城市的路径。为便于表示该国结构，对每座城市 $i$，定义其父节点 $p_i$ 为：从城市 $i$ 出发前往城市 $1$ 时所经过的第一个城市。换言之，若将整棵树以城市 $1$ 为根悬挂，则 $p_i$ 即为城市 $i$ 的父节点。

Berland 每座城市均设有一座加油站。这些加油站采用特殊的定价机制：每座加油站均有其固定的汽油售价区间，即仅接受在某一价格范围内出售汽油。编号为 $i$ 的城市的加油站，其可接受的汽油售价范围为闭区间 $[l_i, r_i]$（含端点）。

Berland 国王是一位模范家庭成员，连续 $m$ 年每年均诞下一对双胞胎儿子。国王的子女自幼便参与公共事务，每年年末均需核查汽油售价的合规性。自出生起，于第 $i$ 年出生的国王子女便分别负责核查两条路径上的汽油价格：第一条路径为从城市 $a_i$ 到城市 $b_i$，第二条路径为从城市 $c_i$ 到城市 $d_i$。

核查过程如下：两名子女分别同时从城市 $a_i$ 和 $c_i$ 出发。第 $i$ 年出生的国王长子沿路径 $a_i \to b_i$ 行进，次子则沿路径 $c_i \to d_i$ 行进。他们首先检查城市 $a_i$ 的汽油价格是否等于城市 $c_i$ 的汽油价格；接着检查从 $a_i$ 到 $b_i$ 路径上的第二座城市与从 $c_i$ 到 $d_i$ 路径上的第二座城市的汽油价格是否相等；随后依此类推，逐一对比两条路径上对应顺序位置的城市的汽油价格；最终检查城市 $b_i$ 的汽油价格是否等于城市 $d_i$ 的汽油价格。题目保证：路径 $a_i \to b_i$ 的长度恒等于路径 $c_i \to d_i$ 的长度。

加油站必须严格遵守法律，因此所有汽油价格核查均不得发现任何违规行为。请帮助 Berland 的加油站计算：在 $m$ 年内，共有多少种方式设定汽油价格？换言之，对每个 $i$（$1 \le i \le m$），需计算有多少种方式为所有加油站设定汽油价格，使得在前 $i$ 对国王子女出生后，他们所执行的所有核查均未发现违规，且每座加油站的汽油售价均落在其允许的价格区间内。由于方案总数可能极大，请将答案对 $10^9 + 7$ 取模。

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of cities in Berland.

The second line contains $(n - 1)$ numbers $p_2,\ p_3,\ p_4,\ \ldots,\ p_n$ ($1 \le p_i \le n$), where $p_i$ denotes the number of the next city on the way from city $i$ to city $1$.

In each of the following lines, two integers are given $l_i$ and $r_i$ ($1 \le l_i \le r_i \lt 10^9+7$), specifying the acceptable range of prices at the gas station number $i$.

The following line contains a single integer $m$ ($1 \le m \le 200\,000$) — the number of years during which two sons were born to the king.

In each of the following $m$ lines, four integers are given $a_i$, $b_i$, $c_i$ and $d_i$ ($1 \le a_i, b_i, c_i, d_i \le n$), specifying two paths on which the king's children will check gasoline prices, born in the year $i$. It is guaranteed that the length of the path between the cities $a_i$ and $b_i$ is equal to the length of the path between the cities $c_i$ and $d_i$.

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）—— 表示 Berland 国家的城市数量。

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

接下来的每一行给出两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \lt 10^9+7$），表示第 $i$ 个加油站价格的可接受范围。

随后一行包含一个整数 $m$（$1 \le m \le 200\,000$）—— 表示国王的两个儿子出生所经历的年份数。

接下来的 $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$ 之间的路径长度。

In $m$ lines, print one number each. The number in the $i$ line should be equal to the number of ways to set gasoline prices in all cities so that the king's children born in the years up to and including $i$ do not reveal violations in inspections. Output the numbers modulo $10^9 + 7$.

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

Consider the first example.

After the birth of the first two sons, the prices in the cities of $1$ and $2$ should be equal. In total, there are 2 ways to choose the same gasoline price for the cities of $1$ and $2$ so that it falls within the acceptable price range for these cities. So, there are only ways to set gasoline prices: $2 \cdot 3 \cdot 3 \cdot 1 = 18$.

The second pair of sons will check the prices on the paths $1 - 2$ and $2 - 1$. This means that gasoline prices in the cities of $1$ and $2$ must match, which is already being done. Therefore, after the birth of the second pair of sons, the answer did not change in any way.

The third pair of sons will check the prices on the tracks $3 - 1 - 2 - 4$ and $4 - 2 - 1 - 3$. Then the price of non-gasoline in the city of $3$ should be equal to the price in the city of $4$, and the price in the city of $1$ should be equal to the price in the city of $2$. Prices in the cities of $1$ and $2$ are already the same. For the cities of $3$ and $4$, there are 2 ways to choose the same price for gasoline so that it falls within the acceptable price range for these cities. So, there are only ways to set gasoline prices: $2 \cdot 2 \cdot 1 = 4$. The fourth pair of sons will check the prices on the tracks $3 - 1 - 2 - 4$ and $3 - 1 - 2 - 5$. This means that the prices in the cities of $4$ and $5$ should be equal, and since the prices in the cities of $3$ and $4$ already coincide, then in the cities of $3$, $4$ and $5$ there should be the same price for gasoline. The price of gasoline in the city of $3$ should be no more than 3, and the price of gasoline in the city of $5$ should be no less than 4. So, after the birth of the fourth pair of sons, there are no ways to set gasoline prices so that all checks are carried out and prices are in the required ranges.

考虑第一个例子。

在前两个儿子出生后，城市 $1$ 和 $2$ 的油价应相等。总共有 $2$ 种方式为城市 $1$ 和 $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 = 4$。

第四对儿子将检查路径 $3 - 1 - 2 - 4$ 和 $3 - 1 - 2 - 5$ 上的油价。这意味着城市 $4$ 和 $5$ 的油价应相等；又因城市 $3$ 和 $4$ 的油价已相等，故城市 $3$、$4$、$5$ 的油价必须全部相同。城市 $3$ 的油价不得超过 $3$，而城市 $5$ 的油价不得低于 $4$。因此，在第四对儿子出生后，不存在满足所有检查要求且油价均处于规定范围内的汽油价格设置方案。