- Look at all these impassable roads.
- Nothing is impassable. Even "impassable" says...
- Dude, what?

Limak is a little polar bear. He lives in Bearland, close to the North Pole. You can try to imagine how much snow falls there every day.

Limak is responsible for the system of roads in Bearland. It's a hard task because he must deal with snow falling on roads. Yeah, polar bears use normal cars and their roads must be free of snow. As Limak is a very little bear, he needs your help!

There are n cities in Bearland, numbered 1 through n. There is a road between every two cities. Unfortunately, some of them are impassable because they're covered with snow. All other roads are passable.

Currently, Bearland is connected. It's possible to travel directly or indirectly between every two cities, using passable roads only. Maintaining roads is expensive, so only $n - 1$ of them are passable right now.

Below, a path denotes a sequence of distinct roads $r_1, r_2, \ldots, r_k$ that there exists a sequence of $k + 1$ distinct cities $v_1, v_2, \ldots, v_{k+1}$ that a road $r_i$ connects city $v_i$ and city $v_{i+1}$, for $1 \le i \le k$.

Watch out because a huge snowstorm is coming. The weather forecast predicts that the snowstorm will move along a path of k passable roads, covering them with snow and thus making them impassable.

Bearland won't be connected anymore and Limak must fix it. He will rent a snowplow in one of the cities and drive along a path of k impassable roads, making them passable. Then Bearland should be connected again. Note that, in particular, Limak could choose the same path as a snowstorm did.

So, a set of k passable roads will be made impassable by the snowstorm. And then, a set of k impassable roads will be made passable by Limak. Note that some roads may belong to both sets.

Limak must consider all possible scenarios. We define a scenario as a pair of sets described in the previous paragraph. Two scenarios are the same only if the first set is the same in both scenarios and the second set is the same in both scenarios. Otherwise, scenarios are different.

You are given an integer k and the description of roads in Bearland. Find the number of different scenarios modulo $1\,000\,000\,007$ (i.e. $10^9 + 7$).

Input format

The first line of the input contains one integer T denoting the number of test cases.

The first line of each test case description contains two integers n and k denoting the number of cities in Bearland and the number of roads in a path.

The second line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le i-1$) describing the current system of roads. There is a passable road between cities i and $p_i$ for every $i \in \{2, 3, \ldots, n\}$. Under the given conditions Bearland is connected.

Output format

For each test case, output a single line containing the answer modulo $10^9 + 7$.

Constraints

• $1 \le T \le 5$
• $2 \le n \le 500\,000$
• $1 \le k \le n - 1$
• $1 \le p_i \le i-1$

Subtasks