Tree land has $n$ cities, connected by $n-1$ roads. You can go to any city from any city. In other words, this land is a tree. The city numbered one is the root of this tree.
There are $n$ ministers numbered from $1$ to $n$. You will send them to $n$ cities, one city with one minister.
Since this is a rooted tree, each city is a root of a subtree and there are $n$ subtrees. The leader of a subtree is the minister with maximal number in this subtree. As you can see, one minister can be the leader of several subtrees.
One day all the leaders attend a meet, you find that there are exactly $k$ ministers. You want to know how many ways to send $n$ ministers to each city so that there are $ k$ ministers attend the meet.
Give your answer mod $1000000007$.
Multiple test cases. In the first line there is an integer $T$, indicating the number of test cases. For each test case, first line contains two numbers $n, k$. Next $n-1$ line describe the roads of tree land.
$T=10,1\leq n\leq 1000,1\leq k\leq n$
For each test case, output one line. The output format is Case #$x$: $ans$, $x$ is the case number,starting from $1$.