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$.

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

9
27