Suppose the function randint(l,r) returns an integer independently and uniformly at random from the range [l,r].
Bessie generates a random labeled tree on N vertices (2≤N≤2⋅105) using the following two-step process:
1.Start with vertices labeled 1 through N. For each i from 2 to N, add an edge between vertex i and randint(1,i−1).
2.Choose a permutation p1,p2,…,pN of {1,2,…,N} uniformly at random. Relabel every vertex v as pv.
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 109+7?
INPUT FORMAT (input arrives from the terminal / stdin):
The input consists of T(1≤T≤10) independent inputs. Each input is specified as follows:
The first line contains N.
The next N−1 lines contain the edges of the tree specified by two space-separated integers u and v (1≤u,v≤N). It is guaranteed that these edges induce a tree.
It is guaranteed that the sum of N across all tests does not exceed 5⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test, output the probability modulo 109+7 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 109+7).
SAMPLE INPUT:
4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 4
SAMPLE OUTPUT:
1
333333336
83333334
55555556
The probabilities are 1, 1/3, 1/12, 1/18.
First test: There is only one tree on N=2 vertices, so the probability of generating it is just 1.
Second test: there are three trees on N=3 vertices, and each of them is equally likely to have been generated by the process above. And 1/3≡333333336(mod 109+7).
SCORING:
Input 2-3: N≤8
Inputs 4-9: N≤2000
Inputs 10-21: No additional constraints.
Problem credits: Benjamin Qi