#215523. [USACO26FEB] Random Tree Generation G

Suppose the function returns an integer independently and uniformly at random from the range .

Bessie generates a random labeled tree on vertices () using the following two-step process:

• Start with vertices labeled through . For each from to , add an edge between vertex and .
• Choose a permutation of uniformly at random. Relabel every vertex as .

Now, Farmer John is looking at the edge set of the final tree and wants to know the probability that the two-step process above produces a tree with exactly this edge set. Can you determine this probability modulo ?

The input consists of () independent inputs. Each input is specified as follows: The first line contains .

The next lines contain the edges of the tree specified by two space-separated integers and (). It is guaranteed that these edges induce a tree.

It is guaranteed that the sum of across all tests does not exceed .

For each test, output the probability modulo on a new line (note that the output probability is a ratio of integers, so you will want to print the result of this division when working modulo ).

样例输入 1

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

样例输出 1

1
333333336
83333334
55555556

The probabilities are , , , .

First test: There is only one tree on vertices, so the probability of generating it is just .

Second test: there are three trees on vertices, and each of them is equally likely to have been generated by the process above. And .

SCORING:

• Input 2-3:
• Inputs 4-9:
• Inputs 10-21: No additional constraints.

Problem credits: Benjamin Qi