Forest Game

Time limit4sMemory limit512 MB

Summary

Given a tree, nodes are removed in random order and each removal adds its component size to the score. Output the expected total times N! mod 1e9+7.

Level: Hard8 of 10
Topics: Tree, Divide and conquer, Combinatorics
Solved: No attempts yet

Problem

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:

If the forest is empty, the game is finished. Otherwise, you choose one node from the current forest uniformly at random.
Your score increases by the size of the tree which your chosen node belongs to.
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$ .

Input

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

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

Output

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

Constraints

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

Examples2

Example 1
Input
```
2
1 2
```
Expected output
```
6
```
Example 2
Input
```
3
1 2
2 3
```
Expected output
```
34
```