Description

Farmer Nhoj has trapped Bessie on a rooted tree with $N$ ($2 \le N \le 2 \cdot 10^5$) nodes, where node $1$ is the root. Scared and alone, Bessie makes the following move each second:

• If Bessie's current node has no children, then she will move to a random ancestor of the current node (excluding the node itself).
• Otherwise, Bessie will move to a random child of the current node.

Initially, Bessie is at node $x$, and her only way out is the exit located at node $y$ ($1\le x,y\le N$). For $Q$ ($1 \le Q \le 2 \cdot 10^5$) independent queries of $x$ and $y$, compute the expected number of seconds it would take Bessie to reach node $y$ for the first time if she started at node $x$, modulo $10^9+7$.

Input Format

The first line contains $N$ and $Q$.

The next line contains $N-1$ integers $p_2, \ldots p_N$ describing the tree ($1\le p_i<i$). For each $2 \le i \le N$, there is an edge between nodes $i$ and $p_i$.

Each of the next $Q$ lines contains integers $x$ and $y$ representing the nodes for that query.

Output Format

For each query, output the expected number of seconds for Bessie to reach node $y$ for the first time starting at node $x$, modulo $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

Hint

Sample 1 Explanation

• In the $1$st query, the expected time to reach node $1$ from itself is $0$.
• In the $3$rd query, after $1$ second, Bessie will be at node $1$ with probability $\frac{1}{2}$ and at node $2$ with probability $\frac{1}{2}$. Since the expected time to reach node $1$ from node $2$ is $4$, the expected time for Bessie to reach node $1$ starting at node $3$ is $1 + \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 4 = 3$.

Sample 2 Explanation

In the $3$rd query, the expected time to reach node $3$ from node $1$ is $\frac{15}{2}$.

SCORING:

• Inputs 4-8: For all queries, $y=1$.
• Inputs 9-13: For all queries, $x=1$.
• Inputs 14-18: For each $2 \le i \le N$, $p_i$ is uniformly randomly chosen from the range $[1, i-1]$.
• Inputs 19-23: No additional constraints.