Imperative Meeting

Problem Description

Some rumors about Zhang3 have been spread on the Internet. Zhang3 needs to dispel the rumors, but she's busy preparing her birthday party, so she asks her $m$ classmates for help. Her classmates decide to have a meeting for discussion. The $m$ classmates live in the same community. There are $n$ houses in the community, labeled $1, 2, \ldots, n$. There are $(n - 1)$ roads connecting the houses, the $i^\mathrm{th}$ of which connects house $(i + 1)$ and $f_{i + 1}$, forming a tree. Each road is 1 km long. The $m$ classmates live in $m$ different houses. They always choose such a house to have the meeting, that the total distance to travel for the $m$ classmates is minimized. The optimal total distance (in km) to travel is called the cost of the meeting. Zhang3 doesn't know which houses her classmates live in, so there are $\binom{n}{m}$ different cases of that. Zhang3 wants to know the sum of the cost in all cases. As the answer can be very large, please help her calculate the answer modulo $10^9 + 7$.

Input

The first line of the input gives the number of test cases, $T \; (1 \le T \le 1000)$. $T$ test cases follow. For each test case, the first line contains two integers $n, m \; (1 \le n \le 10^6, \; 1 \le m \le n)$, the number of houses in the community and the number of classmates. The second line contains $(n - 1)$ integers $f_2, \ldots, f_n \; (1 \le f_i < i)$, separated by spaces, describing the roads. The sum of $n$ in all test cases doesn't exceed $2 \times 10^6$.

Output

For each test case, print a line with an integer, representing the answer modulo $10^9 + 7$.

Sample Input

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

Sample Output

9
27

Source

2020 Multi-University Training Contest 4