说明

农夫 Nhoj 将 Bessie 困在了一棵有 $N$（$2 \le N \le 2 \cdot 10^5$）个结点的有根树上，其中结点 $1$ 是根结点。惊慌失措且孤身一人的 Bessie 每秒会进行如下移动：

• 如果 Bessie 当前结点没有子结点，那么她会移动到当前结点的一个随机祖先结点（不包括该结点自身）。
• 否则，Bessie 会移动到当前结点的一个随机子结点。

初始时，Bessie 位于结点 $x$，而她唯一的出路是位于结点 $y$（$1\le x,y\le N$）的出口。对于 $Q$（$1 \le Q \le 2 \cdot 10^5$）个独立的询问 $(x, y)$，计算如果 Bessie 从结点 $x$ 出发，首次到达结点 $y$ 所需的期望秒数，结果对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

第二行包含 $N-1$ 个整数 $p_2, \ldots, p_N$，描述这棵树（$1\le p_i<i$）。对于每个 $2 \le i \le N$，结点 $i$ 和 $p_i$ 之间有一条边。

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $y$，表示一个询问的起始结点和目标结点。

输出格式

对于每个询问，输出 Bessie 从结点 $x$ 出发首次到达结点 $y$ 所需的期望秒数，结果对 $10^9+7$ 取模。

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

0
4
3
3
1

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

0
3
500000011
500000011
6

13 10
1 2 2 4 3 1 5 6 4 7 8 10
1 12
10 6
5 12
1 13
13 10
6 4
7 12
3 1
12 8
2 1

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

提示

样例 1 解释

• 在第 $1$ 个询问中，从结点 $1$ 到自身的期望时间为 $0$。
• 在第 $3$ 个询问中，$1$ 秒后，Bessie 有 $\frac{1}{2}$ 的概率位于结点 $1$，有 $\frac{1}{2}$ 的概率位于结点 $2$。由于从结点 $2$ 到达结点 $1$ 的期望时间为 $4$，因此从结点 $3$ 出发到达结点 $1$ 的期望时间为 $1 + \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 4 = 3$。

样例 2 解释

在第 $3$ 个询问中，从结点 $1$ 到达结点 $3$ 的期望时间为 $\frac{15}{2}$。

评分

• 输入 4-8：对于所有询问，$y=1$。
• 输入 9-13：对于所有询问，$x=1$。
• 输入 14-18：对于每个 $2 \le i \le N$，$p_i$ 在范围 $[1, i-1]$ 内均匀随机选择。
• 输入 19-23：无额外约束。

翻译由 DeepSeek 完成