「PA 2020」Ogromne drzewo

题目描述

Byteasar 为他的女朋友 Algolina 买了一棵巨大的圣诞树。这是一份十分不寻常的礼物，但 Byteasar 是一位算法师，Algolina 已经习惯了这种惊喜。

正如你所猜到的，这棵树不是植物，而是一个无环连通图。它非常大，但可以用一种有组织的方式来描述。它的节点有 $n$ 层。第一层只包含一个节点，表示树的根。每个节点的子节点都只在其下一层，最后一层的节点除外，它们是叶子。对于区间 $[1, n - 1]$ 中的每一个 $i$，第 $i$ 层的每个节点都有 $a_i$ 个子节点。

Algolina 想让 Byteasar 知道她对他的礼物有多满意，因此决定和他玩一个游戏。Algolina 选择了树上的某个节点 $A$，Byteasar 选择了节点 $B$（可能与 Algolina 相同）。现在从 Algolina 开始，他们俩将轮流重新对树的节点涂色——Algolina 用红色，Byteasar 用蓝色。在游戏开始时，所有节点都是白色的。每个节点将恰好被重新涂色一次——由 Algolina 或由 Byteasar 涂色。在任何时候，涂色的人都可以用自己使用的颜色对任何白色节点涂色，包括节点 $A$ 和 $B$。

一旦所有顶点都被重新涂色了，这两人将计算出他们的分数。Algolina 获得的分数（用 $S_A$ 表示）将是所有红色节点到节点 $A$ 的距离之和，而 Byteasar 获得的分数（用 $S_B$ 表示）将是所有蓝色节点到节点 $B$ 的距离之和。我们所说的两个节点之间的距离，是指它们之间最短路径上的边的数量。Algolina 的目标是得分以最大可能比 Byteasar 的大，即最大化 $S_A-S_B$ 的值，而 Byteasar 的目标是最小化它。

Byteasar 很快指出，这是一个完全信息有限游戏，假设他们都以最优策略进行游戏，就可以计算出最终得分的差值有多大。他希望你能帮他计算出这个值。由于这个值可能非常大，你需要计算它对 $10^9+7$ 取模后的值。

此外，由于在一次比赛后忘记礼物是不愉快的，你需要计算多次选择节点 $A$ 和 $B$ 的情况下两人最终得分之差。

输入格式

第一行两个整数 $n, q$ ($2 \leq n \leq 3 \times 10^5, 1 \leq q \leq 3 \cdot 10^5$)，分别表示树的层数和询问次数。

第二行 $n-1$ 个整数 $a_1, a_2, \ldots, a_{n-1}$ ($2 \leq a_i \leq 3 \cdot 10^5$)，意义如题目描述。

接下来 $q$ 行，每行描述 $A, B$。可以发现最终结果只取决于节点 $A, B$ 和它们的最近公共祖先都在哪一层，因此每行给出三个整数 $W_A, W_B, W_{\text{LCA}(A,B)}$ ($1 \leq W_{\text{LCA}(A,B)} \leq W_A, W_B \leq n$)。

输出格式

输出 $q$ 行，第 $i$ 行包含对第 $i$ 个询问的回答，对 $10^9+7$ 取模。

样例

输入

3 3
3 2
3 2 1
1 1 1
2 3 2

输出

4
1
1000000003

样例中的树有三层，第一层一个节点，第二层三个节点，第三层六个节点。

对于第二个询问，Algolina 和 Byteasar 都选择了根节点。对于最优决策，他们应该按照非递增的层数顺序选择顶点，最后的结果是 $(2 + 2 + 2 + 1 + 1) - (2 + 2 + 2 + 1 + 0) = 1$。

对于第三个询问，答案是 $-4$，但你应该输出 $-4 \bmod (10^9+7) = 10^9+3$。

数据范围与提示

对于一些子任务，满足树最多有 $3 \cdot 10^5$ 个节点，且 $q \leq 100$； 对于另一些子任务，满足 $q \leq 100$。 对于上述每种情况，至少有一个这样的子任务。