19415번 - Forest Game 다국어

Consider the following boring game about removing nodes from a forest. Initially, the forest contains only one tree with $N$ nodes, and your initial score is $0$. The game then goes as follows:

1. If the forest is empty, the game is finished. Otherwise, you choose one node from the current forest uniformly at random.
2. Your score increases by the size of the tree which your chosen node belongs to.
3. Remove your chosen node and all edges connected to this node. Then proceed to step 1.

Please calculate the expected value of your final score multiplied by $N!$, modulo $10^9+7$.

The first line of input contains one integer $N$ indicating the number of nodes in the initial tree.

Each of the following $N-1$ lines contains two integers $x$ and $y$, indicating that $x$-th node and $y$-th node are connected by an edge in the given tree. The nodes are numbered from $1$ to $N$.

Output one number: the expected value of the final score of this boring game multiplied by $N!$, modulo $10^9+7$.

• $1 \le N \le 10^5$
• $1 \le x, y \le N$
• The given graph is a tree