Farmer 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$ 取模。

样例

样例输入 1

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

样例输出 1

0
4
3
3
1

说明 1

在第 $1$ 个询问中，从节点 $1$ 到达节点 $1$ 的期望时间为 $0$。

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

样例输入 2

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

样例输出 2

0
3
500000011
500000011
6

说明 2

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

样例输入 3

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

样例输出 3

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

子任务

• 测试点 4-8：对于所有询问，$y=1$。
• 测试点 9-13：对于所有询问，$x=1$。
• 测试点 14-18：对于每个 $2 \le i \le N$，$p_i$ 在区间 $[1, i-1]$ 中均匀随机选择。
• 测试点 19-23：无附加限制。