Random Tree Generation

Suppose the function $\text{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 \le N \le 2\cdot10^5$) 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 $\text{randint}(1, i-1)$.
2. Choose a permutation $p_1,p_2,\dots,p_N$ of $\{1, 2, \ldots, N\}$ uniformly at random. Relabel every vertex $v$ as $p_v$.

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 $10^9+7$?

The input consists of $T$ ($1\le T\le 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\le u, v\le 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\cdot 10^5$.

• Input 2-3: $N\le 8$
• Inputs 4-9: $N\le 2000$
• Inputs 10-21: No additional constraints.

For each test, output the probability modulo $10^9+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 $10^9+7$).

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\equiv 333333336\pmod{10^9+7}$.