As we all know, Matt is an outstanding contestant in ACM-ICPC. Graph problems are his favorite.

Once, he came up with a simple algorithm for finding the maximal independent set in trees by mistake.

A tree is a connected undirected graph without cycles, and an independent set is subset of the vertex set which contains no adjacent vertex pairs.

Suppose that the tree contains N vertices, conveniently numbered by 1,2, . . . , N. First, Matt picks a permutation p₁, p₂, . . . , p_N of {1, 2, 3, . . . , N } randomly and uniformly.

After picking the permutation, Matt does the following procedure.

1.Set S = .
2.Consider the vertex p₁, p₂, . . . , p_N accordingly. For vertex p_i, if and only if there is no vertex in S which is adjacent to p_i, add vertex p_i into S.
3.Output the set S.

Clearly the above algorithm does not always output the maximal independent set. Matt would like to know the expected size of set S instead.

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains an integer N (1 ≤ N ≤ 200), indicating the number of vertices in the graph.

Each of the following N - 1 lines contains two integers u, v (1 ≤ u, v ≤ N ) indicating an edge between u and v. You may assume that all the vertices are connected.

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y is the answer. To avoid rounding error, the answer you should output is:

(the expected size of independent set) × N! mod (10⁹ + 7)

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

Case #1: 60
Case #2: 10

2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）