Counting Districts

A country has $n$ cities joined by $n-1$ two-way roads, and between any two cities there is exactly one route - the road map is a tree.

The government is drawing up districts. A district is a non-empty group of cities that hangs together: standing in any city of the group, you can reach any other city of the group without ever leaving it. Small districts are easier to govern, so a district may hold at most $K$ cities.

Two districts are different if they are made of different cities. Count how many districts the government could draw. The number gets enormous, so print it modulo $10^9+7$.

Input

First line of input will be a single integer $t$ - the number of testcases.
The first line of each testcase contains two integers $n$ and $K$ - the number of cities and the largest a district may be.
Each of the next $n-1$ lines contains two integers $u$ and $v$ - a two-way road between city $u$ and city $v$.

Cities are numbered $1$ to $n$. The roads always join all the cities without closing a loop, so they form a tree.

Output

For every testcase print a single line with the number of districts, modulo $10^9+7$.

Example

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

13
11
1

The first testcase is this map:

    1
   / \
  2   3
 / \
4   5

It has $5$ districts of one city, $4$ of two cities - one for each road - and $4$ of three cities: $1,2,3$ then $1,2,4$ then $1,2,5$ and $2,4,5$. Groups like $1,4$ or $3,4,5$ do not hang together, and nothing bigger than three cities is allowed. In the second testcase all four cities meet at city $1$, and $K$ is large enough to allow every district: $4+3+3+1=11$. In the third there is a single city and a single district.

Constraints

$1\le t\le 100$
$1\le n\le 1000$
$1\le K\le 100$
$1\le u,v\le n$ and $u\ne v$
The sum of $n$ over all testcases does not exceed $5000$