Bajtazar 为他的女朋友 Algolina 买了一棵巨大的树作为圣诞礼物。这虽然是一份不同寻常的礼物，但 Bajtazar 是一位算法工程师，Algolina 已经习惯了这样的惊喜。

正如你所料，这棵树并不是植物，而是一个连通的无环图。它非常巨大，但可以用一种结构化的方式来描述。它的顶点被分为 $n$ 层。第一层仅包含一个顶点——树的根。每个顶点仅在下一层有子节点，最后一层的顶点除外，它们是叶子节点。对于区间 $[1, n - 1]$ 中的每个 $i$，第 $i$ 层的每个顶点都有 $a_i$ 个子节点。

Algolina 为了向 Bajtazar 展示她有多喜欢这份礼物，决定和他玩一个游戏。她选择了树中的某个顶点 $A$，而 Bajtazar 选择了顶点 $B$（可能与 Algolina 选择的相同）。现在两人轮流行动，从 Algolina 开始，给树的顶点涂色——Algolina 涂红色，Bajtazar 涂蓝色。游戏开始时，所有顶点都是白色的。每个顶点将被涂色恰好一次——由 Algolina 或 Bajtazar 涂色。在任何时候，轮到行动的玩家都可以将任意一个白色顶点涂成自己的颜色，包括顶点 $A$ 和 $B$。

当所有顶点都被涂色后，两人计算各自的得分。Algolina 的得分（记为 $S_A$）是所有红色顶点到顶点 $A$ 的距离之和，而 Bajtazar 的得分（记为 $S_B$）是所有蓝色顶点到顶点 $B$ 的距离之和。两个顶点之间的距离定义为它们之间最短路径上的边数。Algolina 的目标是使她相对于 Bajtazar 的优势最大化，即最大化 $S_A - S_B$，而 Bajtazar 的目标是将其最小化。

Bajtazar 很快注意到，这是一个完全信息有限博弈，假设双方都采取最优策略，可以计算出最终的差值。他希望你能帮他计算出这个差值。由于结果可能非常大，你只需要输出其对 $10^9 + 7$ 取模后的结果。此外，由于在一次游戏后忘记礼物是不礼貌的，你必须计算多种 $A$ 和 $B$ 选择方案下的最终得分差。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 300\,000, 1 \le q \le 300\,000$)，分别表示树的层数和游戏方案的数量。

第二行包含一个由 $n - 1$ 个整数组成的序列 $a_1, a_2, \dots, a_{n-1}$ ($2 \le a_i \le 300\,000$)，含义如题所述。

接下来的 $q$ 行包含后续游戏方案中顶点 $A$ 和 $B$ 的描述。可以证明，最终结果仅取决于顶点 $A$ 所在的层、顶点 $B$ 所在的层以及 $A$ 和 $B$ 的最低公共祖先所在的层。因此，输入中仅给出了这些层的编号，依次为 $W_A, W_B$ 和 $W_{LCA(A,B)}$ ($1 \le W_{LCA(A,B)} \le W_A, W_B \le n$)。

输出格式

输出应包含 $q$ 行，其中第 $i$ 行应包含第 $i$ 种游戏方案的最终得分差，结果对 $10^9 + 7$ 取模。

样例

输入 1

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

输出 1

4
1
1000000003

说明

样例中的树由三层组成，第一层有一个顶点，第二层有三个，第三层有六个。

在第二个游戏方案中，Algolina 和 Bajtazar 都选择了根节点。在最优策略下，他们应该按照层号非递增的顺序选择顶点，最终结果为 $(2 + 2 + 2 + 1 + 1) - (2 + 2 + 2 + 1 + 0) = 1$。

第三个游戏方案的结果为 $-4$，但请注意，在这种情况下应输出 $-4 \pmod{10^9 + 7} = 10^9 + 3$。

子任务

• 在某些测试组中，树最多有 $300\,000$ 个顶点，且 $q \le 100$。
• 在其他测试组中，$q \le 100$。

对于上述每种情况，至少存在一个对应的测试组。