Farmer Nhoj has trapped Bessie on a rooted tree with N (2≤N≤2⋅105) 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≤x,y≤N). For Q (1≤Q≤2⋅105) 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 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and Q.
The next line contains N−1 integers p2,…pN describing the tree (1≤pi<i). For each 2≤i≤N, there is an edge between nodes i and pi.
Each of the next Q lines contains integers x and y representing the nodes for that query.
OUTPUT FORMAT (print output to the terminal / stdout):
For each query, output the expected number of seconds for Bessie to reach node y for the first time starting at node x, modulo 109+7.
SAMPLE INPUT:
5 5
1 2 2 1
1 1
2 1
3 1
4 1
5 1
SAMPLE OUTPUT:
0
4
3
3
1
In the 1st query, the expected time to reach node 1 from itself is 0.
In the 3rd query, after 1 second, Bessie will be at node 1 with probability 12 and at node 2 with probability 12. 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+12⋅0+12⋅4=3.
SAMPLE INPUT:
5 5
1 2 2 1
1 1
1 2
1 3
1 4
1 5
SAMPLE OUTPUT:
0
3
500000011
500000011
6
In the 3rd query, the expected time to reach node 3 from node 1 is 152.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018
SCORING:
Inputs 4-8: For all queries, y=1.
Inputs 9-13: For all queries, x=1.
Inputs 14-18: For each 2≤i≤N, pi is uniformly randomly chosen from the range [1,i−1].
Inputs 19-23: No additional constraints.
Problem credits: Avnith Vijayram