题目描述

题目译自 PA 2020 Runda 3 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\le n\le 3\times 10^5,1\le q\le 3\cdot 10^5)$，分别表示树的层数和询问次数。

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

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

输出格式

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

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

4
1
1000000003

数据范围与提示

• 对于一些子任务，满足树最多有 $3\cdot 10^5$ 个节点，且 $q\le 100$；
• 对于另一些子任务，满足 $q\le 100$。

对于上述每种情况，至少有一个这样的子任务。